链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。

定义

1
2
3
4
5
6
7
8
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

多个这样的 listNode 节点形成一个双向链表，并且在Redis中使用了 list 结构来管理这个双向两边，使得操作更加方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;

特性

  • 无环双向链表，获取头节点和尾节点的时间复杂度为 O(1)
  • 使用len属性计数，获取链表长度的时间复杂度为 O(1)
  • 多态，listNode 的 value 属性类型是 void*，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以Redis的链表可以用于保存各种不同类型的值。

实现相对较为简单

参考 《Redis设计与实现》