织网

身体和灵魂,总有一个在路上

双端链表

| Comments

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 包实现了双链表,直接引入就可以使用了。

Comments