概念

链表作为常用的数据结构，在很多系统中都会用到，Redis 底层实现了一个可以双向遍历的链表结构，Redis 上层数据类型的 List 键就会用到链表作为底层实现之一。

定义

Redis 中的链表结构分为 listNode (链表节点) 和 list （链表主体），链表节点定义如下：

typedef struct listNode {
    // 前置节点
    struct listNode * prev;
    // 后置节点
    struct listNode * next;
    //节点的值
    void * value;
}listNode;

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);
} list;

特点

• 双向遍历：通过节点持有的 prev 和 next 两个指针实现；

• 无环：表头节点 prev 和 表位节点的 next 指针都指向 NULL，便于判断遍历终点；

• 快速获取表头和表尾：list 结构体通过分别持有表头和表尾的两个指针，O(1) 复杂度即可取得表头或者表尾的元素；

• 快速获取表长：无需遍历所有节点，通过 list->len 可以在 O(1) 复杂度内获取表长度；

• 多态性：listNode->value 类型为 void* ，允许节点保存任意类型的数据

源码

源码中列表节点和链表主体的定义都在 https://github.com/redis/redis/blob/7.2.4/src/adlist.h#L36

链表节点：

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

链表主体：

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;

此外，还定义了一个专门用于遍历链表的结构体 listIter ：

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

再看一下 Redis 是怎么通过 listIter 来遍历列表：

// 从链表 list 中搜索某个 key
listNode *listSearchKey(list *list, void *key)
{
    listIter iter;
    listNode *node;

    // 初始化，将遍历器指向表头
    listRewind(list, &iter);
    // 开始遍历
    while((node = listNext(&iter)) != NULL) {
        // 这里会用到了链表自带的 match 方法
        // 如果有自定义的match方法就调用，否则就手动比较
        if (list->match) {
            if (list->match(node->value, key)) {
                return node;
            }
        } else {
            if (key == node->value) {
                return node;
            }
        }
    }
    return NULL;
}

可以看出，Redis 的链表结构实现的比较经典，经过这么多版本的迭代，也没有做过大的改动，可见这个结构是足够健壮的。