redis 链表

链表的实现方式有很多种，常见的主要有三个，单向链表、双向链表、循环链表。

1、单链表

1-1

• 结构：第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
• 优点：链表特性 插入和删除方便，只需要考虑相邻节点指针的变化，因此为常数级时间复杂度O(1)
• 缺点：查找慢，需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点，因此时间复杂度为O(N)。

2、双向链表

1-2

• 结构：每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
• 优点：链表特性 插入和删除方便

• 在有序链表中查找某个元素，单链表由于只有后继指针，因此只能从前往后遍历查找时间复杂度为O(N)，而双向链表可以双向遍历。
• 删除给定指针指向的结点。假设已经找到要删除的节点，要删除就必须知道其前驱节点和后继节点，单链表想要知道其前驱节点只能从头开始遍历，时间复杂度为0(n)，而双向链表由于保存了其前驱节点的地址，因此时间复杂度为0(1)。

• 缺点：查找慢，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。

3、循环链表

1-3

• 结构：一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
• 优点：在于链尾到链头，链头到链尾比较方便适合处理的数据具有环型结构特点。获取第一个节点时间复杂度为O(1)，那么获取最后一个节点也为O(1) 如 获取栈顶、栈底、队头、队尾等操作
• 缺点：和其他链表差不多

redis 的链表结构（adlist.h）

//节点
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
//迭代器
typedef struct listIter {
    listNode *next;
    int direction;
} listIter;
//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 链表是双向链表

/* Add a new node to the list, to head, containing the specified 'value'
 * pointer as value.
 *
 * On error, NULL is returned and no operation is performed (i.e. the
 * list remains unaltered).
 * On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
       // 将头节点的prev赋值为NULL
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;
    return list;
}
/* Add a new node to the list, to tail, containing the specified 'value'
 * pointer as value.
 *
 * On error, NULL is returned and no operation is performed (i.e. the
 * list remains unaltered).
 * On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        // 将头节点的next赋值为NULL
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
    return list;
}

从listAddNodeTail 和listAddNodeHead 可以看出redis 双向链表是无环的。

结构特性如下：（网上都这么说）

• 双端： 链表节点带有 prev 和 next 指针， 获取某个节点的前置节点和后置节点的复杂度都是 O(1)
• 无环： 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ， 对链表的访问以 NULL 为终点。
• 带表头指针和表尾指针： 通过 list 结构的 head 指针和 tail 指针， 程序获取链表的表头节点和表尾节点的复杂度为O(1)。
• 带链表长度计数器： 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 O(1)。
• 多态： 链表节点使用 void*（“无类型指针”，可以指向任何数据类型） 指针来保存节点值， 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值。

总结

• 采用双向无环链表而没有采用其他链表 很显然是一种权衡的策略，那空间来减少链表的查询慢的缺点，典型空间换时间。
• 这种结构跟我们在Java中使用的LinkedList 类似。（链表不都这样吗？）

应用

除了实现列表类型以外， 双端链表还被很多 Redis 内部模块所应用：

• 事务模块使用双端链表依序保存输入的命令；
• 服务器模块使用双端链表来保存多个客户端；
• 订阅/发送模块使用双端链表来保存订阅模式的多个客户端；
• 事件模块使用双端链表来保存时间事件（time event）；