Redis底层数据结构--链表

1.简介

当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

除了链表键之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区。

2.链表和链表节点的定义和实现

链表节点的结构如下：

typedef struct listNode{
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

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

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;

在Redis中，我们使用list结构来持有链表，如下图是一个list和三个listNode节点组成的链表：

Redis链表特性：

• 双端：链表节点有prev和next指针，获取前置节点和下一节点实践复杂度都是O(1);
• 无环：表头节点的prev和表尾节点的next都指向NULL，对链表的访问以NULL终止；
• 带表头指针和表尾指针；
• 带节点计数器；
• 多态：使用void*指针来保存节点的值。

参考书籍：Redis设计与实现