双端链表

Nginx, Redis 项目中,均使用上了双链表。

  • 列表类型的键进行操作(RPUSH, LPOP)时,程序底层操作用的是双端链表。 源码

  • Nginx 典型应用是在连接池中。Nginx 会处理大量的 socket 连接,为提高并发处理链接的能力,引入了连接池,其实现这个连接池用到了双链表。源码.

对于双端链表,教科书上曾有提及,但如今映像并不深刻,再度理解并实践一次。

结构定义与初始化

1
2
3
4
5
6
7
8
9
10
typedef struct Node {
int num;
struct Node * next; //前继指针
struct Node * pre; //后继指针
} Node;

typedef struct dlist {
Node * head; //双链表的指向头结点的元素
Node * tail; //双链表指向尾部节点的元素,方便从后检索
} dlist;

初始化的双链表,head,tail 均为空。

插入操作

插入操作,是按照递增的顺序插入,涉及到双链表的更改,因此传参是指向链表的指针,分三种情况

  • 空链表插入头元素,head 与 tail 节点均要修改
  • 在链表尾部插入节点,要变动 tail 指针
  • 中间插入节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
static int insertDlist(dlist **list, int num) {
Node * head = (*list) -> head;
Node * tail = (*list) -> tail;

if (list == NULL) return -1;

Node * node = initNode(num);
if (node == NULL) return -1;

// empty dlist
if ((*list) -> head == NULL && (*list) -> tail == NULL) {
(*list)-> head = node;
(*list)-> tail = node;
return 0;
}

while (head -> next && head -> num < num) {
head = head -> next;
}

// at the end
if (head->next == NULL) {
head -> next = node;
node -> pre = head;
tail -> pre = node;
return 0;
} else {
// in the middle
node-> next = head -> next;
head -> next -> pre = node;
node -> pre = head;
head -> next = node;
return 0;
}
}

删除操作

删除操作,要涉及到双链表的更改,因此传参是指向链表的指针,分三种情况

  • 删除头结点,
  • 删除尾节点
  • 删除中间节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static int deleteDlist(dlist ** list, int location) {
Node * head = (*list) -> head;
Node * now = NULL;
Node * last = NULL;

if (head == NULL)
return -1;
if (location <= 0 || location > numOfDlist(*list))
return -1;

if (location == 1) {
now = head;
(*list) -> head = now ->next;
head -> next ->pre = NULL;
if (now) {
free(now);
now = NULL;
}
return 0;
}
int num = 0;
while (head && num++ < location) {
head = head -> next;
}

if (head -> next == NULL) {
now = (*list) -> tail;
head -> pre -> next = NULL;
now -> pre = head->pre;
if (head) {
free(head);
head = NULL;
}
} else {
now = head -> next;
last = head -> pre;
now ->pre = head -> pre;
last -> next = head ->next;
if (head) {
free(head);
head = NULL;
}
}
return 0;
}

本文所述是 C 语言实现的,源码
在 Go 语言之中, container/list 包实现了双链表,直接引入就可以使用了。