Nginx, Redis 项目中,均使用上了双链表。
列表类型的键进行操作(RPUSH, LPOP)时,程序底层操作用的是双端链表。 源码
Nginx 典型应用是在连接池中。Nginx 会处理大量的 socket 连接,为提高并发处理链接的能力,引入了连接池,其实现这个连接池用到了双链表。源码.
对于双端链表,教科书上曾有提及,但如今映像并不深刻,再度理解并实践一次。
结构定义与初始化
1 | typedef struct Node { |
初始化的双链表,head
,tail
均为空。
插入操作
插入操作,是按照递增的顺序插入,涉及到双链表的更改,因此传参是指向链表的指针,分三种情况
- 空链表插入头元素,head 与 tail 节点均要修改
- 在链表尾部插入节点,要变动 tail 指针
- 中间插入节点

1 | static int insertDlist(dlist **list, int num) { |
删除操作
删除操作,要涉及到双链表的更改,因此传参是指向链表的指针,分三种情况
- 删除头结点,
- 删除尾节点
- 删除中间节点

1 | static int deleteDlist(dlist ** list, int location) { |
本文所述是 C 语言实现的,源码
在 Go 语言之中, container/list
包实现了双链表,直接引入就可以使用了。