《Redis 设计与实践》读书笔记系列三：链表

要注意，这里的链表介绍不等同于Redis基础类型的List。链表在Redis中应用非常广泛，而C语言没有内置的链表结构，所以Redis用C实现了链表结构。

如List中的键的底层实现之一就是链表，当List元素较多，或List元素值为较长字符串时，就会使用链表来存储List中的键。

127.0.0.1:6379> lrange demo 0 -1#这里的1，2，3，4是上述中所指的List中的键
1) "java"
2) "php"
3) "python"
4) "ruby"
127.0.0.1:6379> 

在Redis中还有很多地方使用到了链表结构，如发布与订阅，慢查询，监视器等。后续其他章节会介绍到。

Redis中的链表底层结构是双向链表，即每个节点拥有上一个节点和下一个节点的指针，每个节点的结构名为：listNode。在此链表结构基础之上，Redis封装了一层，结构名称为：list。如下：

该结构相当于上一章节的简单动态字符串SDS，是一种Redis的基础结构，拥有自己的API。

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相当于持有了该链表。

简而言之，双向链表的优秀特性，list均拥有，list拥有的特性双向链表没有，因为list直接有个属性指向双向链表的头指针。

本作品采用《CC 协议》，转载必须注明作者和本文链接