双向链表实现原理

双向链表（Doubly Linked List）是一种常见的数据结构，它由节点组成，每个节点包含数据以及指向前一个节点和后一个节点的指针。

源码位置

• adlist.c
• adlist.h

源码及原理

数据结构

每个双向链表的节点

// 定义一个双向链表节点结构体
typedef struct listNode {
    struct listNode *prev; // 指向前一个节点的指针
    struct listNode *next; // 指向下一个节点的指针
    void *value;           // 节点存储的值
} listNode;

双向链表结构体：

// 定义一个双向链表结构体
typedef struct list {
    listNode *head; // 指向链表头节点的指针
    listNode *tail; // 指向链表尾节点的指针
    void *(*dup)(void *ptr); // 节点值复制函数指针
    void (*free)(void *ptr); // 节点值释放函数指针
    int (*match)(void *ptr, void *key); // 节点值匹配函数指针
    unsigned long len; // 链表长度
} list;

优点与缺点

优点：

• 有prev和next指针，前后遍历速度快
• 获取头和尾节点为$O(1)$
• 可以保存各种类型数据结构

缺点：

• 链表元素不连续，无法利用CPU缓存。相对于数组，数组内存连续，可以用CPU缓存加速
• 需要保存头节点分配，内存开销大

参考资料

小林Coding 链表