Redis 数据结构之链表

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

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

每个链表节点用一个 listNode 结构来表示：

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

链表结构：

Redis 链表特性总结如下：

• 双端
• 无环
• 带表头指针和表尾指针
• 带链表长度计数器：使得程序获取链表中节点数量的复杂度为 O(1)
• 多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数