015.双向链表

C 语言本身没有链表，Redis 自己设计了一个链表数据结构

双向链表结构设计 §

链表节点结构设计：

// 链表节点
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;

list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数

链表的优势与缺陷 §

优势：

• 不必开辟连续大空间
• 获取某个节点的前置节点或后置节点时间复杂度只需 O(1)
  • 因为 listNode 的结构有 prev 和 next 指针
  • 这两个指针都可以指向 NULL，所以链表是无环链表
• 获取链表的表头节点和表尾节点的时间复杂度只需 O(1)
  • 因为 list 结构有表头指针 head 和表尾节点 tail
• 获取链表中的节点数量的时间复杂度只需 O(1)
  • 因为 list 结构有链表节点数量 len
• 链表节点可以保存各种不同类型的值
  • 因为 listNode 使用 void* 指针保存节点值
  • 并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数

缺陷：

• 链表每个节点之间的内存是不连续的，意味着无法很好利用 CPU 缓存加速访问
• 每保存一个值都需要一个链表节点结构的内存分配，需要频繁分配内存且内存开销较大