双端链表

双端链表的应用¶

双端链表作为一种通用的数据结构， 在 Redis 内部使用得非常多： 既是 Redis 列表结构的底层实现之一， 同时为大量 Redis 模块所用， 用于构建 Redis 的其他功能。

redis> RPUSH brands Apple Microsoft Google
(integer) 3

redis> LPOP brands
"Apple"

redis> LLEN brands
(integer) 2

redis> LRANGE brands 0 -1
1) "Microsoft"
2) "Google"

双端链表的实现¶

双端链表的实现由 listNode 和 list 两个数据结构构成， 下图展示了由这两个结构组成的一个双端链表实例：

其中， listNode 是双端链表的节点：

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;

注意， listNode 的 value 属性的类型是 void * ，说明这个双端链表对节点所保存的值的类型不做限制。

对于不同类型的值，有时候需要不同的函数来处理这些值，因此， list 类型保留了三个函数指针 —— dup 、 free 和 match ，分别用于处理值的复制、释放和对比匹配。在对节点的值进行处理时，如果有给定这些函数，就会调用这些函数。

举个例子：当删除一个 listNode 时，如果包含这个节点的 list 的 list->free 函数不为空，就会先调用删除函数 list->free(listNode->value) 来清空节点的值，再执行余下的删除操作（比如说，释放节点）。

另外，从这两个数据结构的定义上，也可以了解到一些行为和性能特征：

• listNode 带有 prev 和 next 两个指针，因此，遍历可以双向进行：从表头到表尾，表尾到表头。
• list 保存了 head 和 tail 两个指针，因此，对链表的表头和表尾进行插入的复杂度都为 \(\theta(1)\) —— 这是高效实现 LPUSH 、 RPOP 、 RPOPLPUSH 等命令的关键。
• list 带有保存节点数量的 len 属性，所以计算链表长度的复杂度仅为 \(\theta(1)\) ，这也保证了 LLEN 命令不会成为性能瓶颈。

以下是用于操作双端链表的 API ，它们的作用以及算法复杂度：

迭代器¶

Redis 为双端链表实现了一个迭代器 ， 这个迭代器可以从两个方向对双端链表进行迭代：

• 沿着节点的 next 指针前进，从表头向表尾迭代；
• 沿着节点的 prev 指针前进，从表尾向表头迭代；

以下是迭代器的数据结构定义：

typedef struct listIter {

    // 下一节点
    listNode *next;

    // 迭代方向
    int direction;

} listIter;

direction 记录迭代应该从那里开始：

• 如果值为 adlist.h/AL_START_HEAD ，那么迭代器执行从表头到表尾的迭代；
• 如果值为 adlist.h/AL_START_TAIL ，那么迭代器执行从表尾到表头的迭代；

以下是迭代器的操作 API ，API 的作用以及算法复杂度：

小结¶

• Redis 实现了自己的双端链表结构。
• 双端链表主要有两个作用：
  • 作为 Redis 列表类型的底层实现之一；
  • 作为通用数据结构，被其他功能模块所使用；
• 双端链表及其节点的性能特性如下：
  • 节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为 \(O(1)\) ，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行；
  • 链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为 \(O(1)\) ；
  • 链表带有记录节点数量的属性，所以可以在 \(O(1)\) 复杂度内返回链表的节点数量（长度）；