Redis数据结构——链表list

链表是一种常用的数据结构，提供了顺序访问的方式，而且高效地增删操作。
Redis中广泛使用了链表，例如：列表的底层实现之一就是链表。

在Redis中，链表分为两部分：链表信息 + 链表节点。

• 链表节点用来表示链表中的一个节点，基础的值和指向前和后的指针
• 链表信息，用来保存整个链表的信息，例如首尾节点、节点数量

先来说链表节点，就是我们最常见的链表节点的结构：

typeof struct listNode{// 前驱节点struct listNode *prev;// 后继节点struct listNode *next;// 节点的值void *value; 
}listNode; 

通过链表节点中的prev和next组成双向链表。

而链表这个结构体中保存了整个链表的信息

typeof struct list{listNode *head; // 表头节点listNode *tail; // 表尾节点unsigned long len; // 链表节点数量// 接下来就是一些链表操作的API // 节点复制 ...// 节点释放 ...// 节点比较 ... 
}list; 

Redis中的链表并没有什么特殊之处，总结一下特点：

• 双端操作，链表信息list中保存了首尾节点
• 无环，head的prev始终为null，tail的next始终为null
• O(1)获取链表节点数量
• 多态：链表节点中通过void*来保存节点值，节点值可以是任意类型。

参考文章

• Redis数据结构——链表 - 随心所于 - 博客园
• 《Redis设计与实现》