Redis的数据结构(二)：链表

链表在redis的应用

由于redis的c语言没有内置链表结构类型，因此redis自身实现了一套链表结构。链表主要应用在几个方面：

• 应用于较长的list结构中
• 发布与订阅
• 监视器
• 保存多个客户端状态信息等等

链表在redis中的实现

我们翻到源码src/adlist.h中的listNode结构体，这个结构体也就是链表节点的实现：

/*
 * 双端链表节点
 */
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

可以看到，如果画成图，那么多个listNode就会变成这样的一个链表：

image.png
为了操作更方便，redis还实现了一个链表list，源码位于src/adlist.h的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;

其中，比较难看懂的应该就是dup、free、match三个字段，我们分别解释一下这三个字段的作用：

• dup：主要是用来复制链表节点所保存的值
• free：主要是用来释放链表节点的内存空间
• match：用来比对节点值，通常用来查找某个值是否在链表中
  那么，为什么要抽出这三个成独立的字段呢？答案就是为了多态，我们都知道void*在C语言是表示任意类型的指针，加上链表节点的value也是用void*保存的，因此通过dup、free、match三个字段函数就可以操作各种类型的值，也让链表节点能够保存任何类型的值了。

redis中链表的特性总结

总体来说，redis的链表结构非常简单高效，主要体现以下几方面：

1. 双端链表。每个链表节点listNode都包含了prev和next字段，用来指向该节点前一个节点和后一个节点，这样可以使得节点查找前一个和后一个节点的计算复杂度变为O(1)。
2. 无环。listNode的prev和next字段都是指向NULL，因此链表是无环的。
3. 带表头的表尾指针。链表list带有head和tail指针，使得查找链表的表头和表尾节点的计算复杂度变为O(1)。
4. 链表长度计算器。链表list有一个字段len，使得计算链表长度的复杂度变为O(1)，而不用通过遍历链表来获取总长度。

文章参考自：<<Redis设计与实现>> 第二版