Redis中的链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。作为一种常用数据结构，链表内置在很多高级的编程语言里面， 因为Redis使用的C语言并没有内置这种数据结构，所以Redis构建了自己的链表实现。

References:

• 《Redis设计与实现》
• https://github.com/redis/redis/blob/e2641e09cc/src/redis.h
• https://github.com/redis/redis/blob/e2641e09cc/src/t_list.c

链表在Redis中的应用非常广泛，比如list的底层实现之一就是链表： 当一个list包含了数量比较多的元素， 又或者list中包含的元素都是比较长的字符串时，Redis就会使用链表作为list的底层实现。但是list类型不全是链表实现的：

• ziplist(压缩列表): 列表元素较少(可配置)时用ziplist减少内存使用
• linkedlist(链表): 不满足ziplist条件时用linkedlist
• quicklist(3.2版本之后): 结合ziplist和linkedlist的优势

这里只关注链表的方式，以下展示的 integers 列表键包含了从 1 到 1024 共一千零二十四个整数：

redis> LLEN integers
(integer) 1024

redis> LRANGE integers 0 10
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"
7) "7"
8) "8"
9) "9"
10) "10"
11) "11"

integers 列表键的底层实现就是一个链表， 链表中的每个节点都保存了一个整数值。除了链表键之外， 发布与订阅、慢查询、监视器等功能也用到了链表。

每个链表节点使用一个 adlist.h/listNode 结构来表示：

typedef struct listNode {
    struct listNode *prev; // 前一个节点
    struct listNode *next; // 下一个节点
    void *value;           // 当前节点的值
} listNode;

多个listNode可以通过prev和next指针组成双端链表:

虽然仅仅使用多个listNode结构就可以组成链表， 但使用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 int len;                    // 链表长度
} list;

list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，这些数据可以作为list的元数据，让list的操作更为方便。

redis/adlist.c的第一句很好的描述了Redis的list结构：A generic doubly linked list implementation。
Redis的链表和一般的双向链表差不多，节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)。
表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以 NULL为终点。
由于有len属性对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O(1)。

再给出Java中的LinkedList作为对比:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first; // 链表头

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last; // 链表尾

    ...

    // 链表的节点
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    ...

怎么样，是不是一摸一样:)