《Redis 设计与实现》笔记之链表

一、链表的定义

1.1 listNode 结构体

typedef struct listNode {
  // 前置节点
  struct listNode *prev;

  // 后置节点
  struct listNode *next;

  // 节点的值
  void *value;
}listNode;

虽然使用多个 listNode 就可以表示双向链表，但是功能还不够，Redis 添加了一个 list结构体，功能更多。

1.2 list 结构体

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;

1.2.1 基本结构

list 结构有表头指针 head、表尾指针 tail，以及链表长度计数器 len三个变量。 list 还有三个函数：

• dup 函数用于复制链表节点所保存的值
• free 函数用于释放链表节点所保存的值
• match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。

1.2.2 特性

• 链表节点有 prev和 next节点，获取某个节点的前置和后继复杂度为 。
• 表头的 prev和表尾的 next都指向 null，以 null 为终点。
• list 有表头指针 head、表尾指针 tail，获取链表的表头节点和表尾节点复杂度为 。
• 链表拥有 len 变量，因此获取链表长度复杂度为 。
• 链表节点使用 void* 指针来保存节点值，并且 list 结构的 dup、free、match 的形参也是 void*，所以链表可以用于保存各种不同类型的值，实现多态。

二、链表的功能

• 链表键
• 发布与订阅
• 慢查询
• 监视器
• 保存多个客户端的状态信息
• 构建输出缓冲区。