list 简介

redis 的链表没有什么特别之处，就是普通的双向链表 adlist.c/listNode。

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

多个 listNode 可以通过 prev 和 next 组成双端链表，如下所示：

说明：头节点和尾节点的 prev, next 分别指向 null。

可以通过 listNode 结构来组成链表，但使用 adlist.c/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;

一个 list 结构和三个 listNode 结构的链表

链表特征

• 双端：链表节点带有 prev 和 next 指针， 获取某个节点的前置节点和后置节点的复杂度都是 O(1).

• 无环：头节点的 prev 指针和表尾 next 指针都指向 null, 对链表的访问 null 为终点。

• 带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O(1).

• 带链表长度计数器：程序使用 list 结构的 len 属性来对 list 持有的链表节点说开那个进行计数，程序获取链表中节点数量的负载度为 O(1).

• 多态：链表节点使用 void* 指针来保存节点值，并且可以使用 list 结构中的 dup、free、match 三个属性为节点值来设置类型特定函数。所以链表可以用于保存各种不同类型的值。

迭代器

这里链表的迭代和数据是分配开的，采用的是类似迭代器模式，这个思想就是很多场景用到的 leveldb 中，大家可以搜索一下迭代器模式。

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;
listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;
    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

运用场景

• 链表广泛用韵用实现 Redis 的各种功能，比如列表键、发布订阅、满查询、监视器等。

• 通过为链表设置不同的类型特定函数，Redis 链表可以用于保存各种不同类型的值。

参考资料

• redis.io

• 《Redis 设计与实现》黄健宏