简述

链表是我们经常能看到的一种数据结构，在Redis中也是多处出现的。之前我们介绍的SDS，ziplist，skiplist，quicklist，dict和inset都作为了Redis值存储的数据结构，其中skiplist，quicklist和dict也用到了链表。慢查询，发布订阅，监视器等功能都用到了链表，链表在Redis中运用很广泛。今天我们来分析下Redis中的链表。

Redis链表

Redis链表使用的是双向无环链表。我们可以先看看链表的结构体，从数据结构上研究下Redis链表。

• listNode

typedef struct listNode {
    // 前驱结点，指向前面一个结点的指针
    struct listNode *prev;
    // 后继结点，指向下一个结点的指针
    struct listNode *next;
    // 指向结点的值的指针
    void *value;
} listNode;

可以看到，Redis链表结点结构体中，是包含了前驱结点指针，后继结点指针和指向结点值的指针，是一个双向链表。如下图所示，Redis双向链表结构图：

• 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;

可以看到，Redis链表结构也包含了头结点的指针和尾结点的指针，获取表头和表尾结点的时间复杂度都为O(1)，这也方便从头遍历和从尾遍历链表。
listNode是双向的，索引从尾遍历也是成立的。list中记录了链表的长度，所以链表获取结点数量的事件复杂度为O(1)。
list中还保存了指向复制函数的指针、指向释放内存函数的指针和指向比较函数的指针，所以链表可以用来保存各种不同类型的值，做不同的处理。

Redis链表整体结构图

Redis链表整体结构如下图所示：

从Redis链表的整体结构，我们可以看到Redis链表具有如下特性：

1. 双向 链表结点带有前驱结点和后继结点，是双向的。
2. 无环 链表头结点的前驱结点指针和表尾结点的后继结点指针都指向了NULL，所以Redis链表是无环的。
3. 带表头指针和表尾指针 list中包含了指向表头结点的指针和指向表尾结点的指针，获取表头和表尾节点的时间复杂度都为O(1)。
4. 带有链表长度计数器 list中带有链表长度计数器，所以获取链表长度不需要遍历链表，获取链表结点数量的时间复杂度为O(1)。
5. 多态 list中用了指针指向了结点的值，并且复制函数dup、释放内存函数free和比较函数match都是用指针指向的，使用了宏定义，所以链表中可以保存各种不同类型的值。

Redis中的宏

在adlist.h中可以看到Redis针对list结构和listNode结构的赋值和查询操作使用了宏定义进行封装，操作的复杂度均为O(1)。下面是Redis链表中的宏定义。

#define listLength(l) ((l)->len)                    //返回链表l节点数量
#define listFirst(l) ((l)->head)                    //返回链表l的头结点地址
#define listLast(l) ((l)->tail)                     //返回链表l的尾结点地址
#define listPrevNode(n) ((n)->prev)                 //返回节点n的前驱节点地址
#define listNextNode(n) ((n)->next)                 //返回节点n的后继节点地址
#define listNodeValue(n) ((n)->value)               //返回节点n的节点值

#define listSetDupMethod(l,m) ((l)->dup = (m))      //设置链表l的复制函数为m方法
#define listSetFreeMethod(l,m) ((l)->free = (m))    //设置链表l的释放函数为m方法
#define listSetMatchMethod(l,m) ((l)->match = (m))  //设置链表l的比较函数为m方法

#define listGetDupMethod(l) ((l)->dup)              //返回链表l的赋值函数
#define listGetFree(l) ((l)->free)                  //返回链表l的释放函数
#define listGetMatchMethod(l) ((l)->match)          //返回链表l的比较函数

总结

Redis链表是无环双向链表，Redis中使用了指针使得整条链表可以存储不同类型的值。双向链表用了额外的空间保存了前驱结点指针和后继结点指针，但是如果从表尾遍历等操作，则不需要从表头开始遍历到表尾处理，大大降低了时间复杂度，是一种空间换时间的思想。

参考

Redis数据结构-链表
redis当中的链表处理