Redis 入门-第二篇-数据结构与对象-链表

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

链表和链表节点的实现：

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

typedef struct list {
listNode * head;                     // 表头结点
listNode * tail;                     // 表尾节点
unsigned long len;                   // 节点数量
void *(*dup)(void *ptr);             // 节点复制函数
void (*free)(void *ptr);             // 节点释放函数
void (*match)(void *ptr, void *key); // 节点值对比函数
}list;

Redis 的链表实现可以总结为：

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