第 3 章 链表

listNode

typedef struct listNode{
  struct listNode *prev;
  struct listNode *next;
  void *value;
}listNode;

void 指针可以指向任意类型的数据，如：

void main(){
  int num = 100;
  void *p = #
  printf("%d",*(int *)p);
}

可见，Redis 中的链接采用了双端链表。

list

typedef struct list{
  listNode *head;
  listNode *tail;
  unsigned long len;
  void *(*dup) (void *ptr);
  void (*free) (void *ptr);
  int (*match) (void *ptr, void *key);
}

Redis 的链表实现特性：

• 双端：获取某节点的前、后置节点的复杂度为 O(1).
• 无环
• 多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。
  链表被广泛用于实现 Redis 的各种功能，比如列表键、发布与订阅、慢查询、监视器等。