2、Redis数据结构——链表-linkedlist

链表简介：

因为C语言没有内置链表这种数据结构，所以Redis构建了自己的链表实现。列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

1、链表实现：

链表节点数据结构：

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

虽然使用多个listNode结构就可以组成链表，但使用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; 

list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match成员则是用于实现多态链表所需的类型特定函数：

• dup函数用于复制链表结点所保存的值；
• free函数用于释放链表结点所保存的值；
• match函数则用于对比链表结点所保存的值和另一个输入值是否相等；

2、特性：

1. 双端：链表结点带有prev和next指针，获取某个节点前置节点和后置节点复制度都是O(1)
2. 无环：表头结点的prev指针和表尾结点的next指针都指向NULL，对链表的访问以NULL为终点。
3. 带表头指针和表尾指针：获取表头节点和表尾节点复制度O(1)
4. 带链表长度计数器：len属性对list持有的链表节点进行计数，获取节点数量复制度O(1)
5. 多态：使用void* 指针保存节点值，通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

重点回顾

• 链表被广泛用于实现Redis各种功能，如列表键、发布订阅、慢查询等
• 每个链表结点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以Redis的链表实现是双端链表。
• 每个链表用一个list结构表示，这个结构带有表头节点指针、表尾节点指针以及链表长度等信息。
• 因为链表表头前置节点和表尾后置节点都指向NULL，所以Redis的链表实现是无环链表。
• 通过为链表设置不同类型特定函数，Redis的链表可以用于保存各种不同类型的值。

联系我

最后，欢迎关注我的个人公众号 CodingCode，会不定期更新学习笔记，也欢迎公众号私信，一定知无不言，言无不尽。

公众号