Redis（链表数据结构）

链表提供了高效的节点重排，链表可以通过新增、删除节点来控制链表的长度。Redis中也广泛引用了列表，比如列表键底层的数据结构就是使用的链表，除了列表键外还有一些发布订阅、慢查询、监视器等功能也使用到了链表。作为常用的数据结构Redis也重写了链表结构。下面我们看下Redis内部链表的属性。

LinkNode:

typedef struct listNode {
    // 前置节点
    struct listNode * prev;
    // 后置节点
    struct listNode * next;
    //节点的值
    void * value;
}listNode;
1
2
3
4
5
6
7
8

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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

示例

Redis链表的特性

1. 双端：listNode 有前置节点和后置节点指针，可以根据指针直接O(1)时间复杂度找到上一个节点和下一个节点。
2. 无环：列表有头结点和尾节点，在没有数据的时候都是null。没有头尾相连。
3. 维护链表长度字段。这样在查询该链表长度时不需要再从头结点数到尾节点了这样时间复杂度就由O(n) 变为O(1)。
4. 带头尾节点这样获取头结点或者尾节点都是O(1)。
5. 多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

总结

  Redis自己实现的链表存储了一些额外的信息，比如头尾节点、长度字段、节点使用的类型。这些都对链表的查询速度进行了优化，设计思想就是以空间换时间

参考：《Redis开发与实现》