Redis 设计与实现之链表 -- 阅读笔记

前言

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，链表在 Redis 中的应用很广泛，比如列表键的底层实现之一就是链表，除此之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis 服务器本身使用链表保存多个客户端的状态信息，使用链表构建客户端输出缓冲区。

链表的底层实现

学习过算法的同学都知道数据结构中的链表的相关概念了，这里简单介绍一下链表的数据结构：

链表是常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，比另一种线性表 顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间，而顺序表相应的时间复杂度分别是 O(logn)和 O(1)。（来源于维基百科）

先来看看一个链表节点的数据结构：

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

多个 listNode （链表节点）通过 prev 和 next 指针组成双向链表

下面使用 list 数据结构来管理链表：

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;

list 结构为链表提供了表头指针 head, 表尾指针 tail,以及链表长度计数器 len, 而 dup、free 和 match 函数的作用如下：

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

list 结构与 listNode 结构组成的链表

Redis 链表特点总结

• 双向： 链表节点都有 prev 和 next 指针，可以获取某个节点的前置节点和后置节点，复杂度为 O(1)
• 无环：上面图片显示，表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL
• 带表头指针和表尾指针： 通过 list 结构的 head 和 tail 指针，获取表头节点和表尾节点的复杂度为 O(1)
• 带链表长度计数器：通过 list 结构的 len 字段记录了 链表中的链表节点(listNode)数，获取链表长度的复杂度为 O(1)
• 多态：链表节点使用 void * 指针来保存节点值，可以通过 list 结构的 dup、free 和 match 属性为节点值设置类型特定函数，所有链表可用于保存不同类型的值

这章内容比较少，基本就是 Redis 设计与实现 原样搬过来的，很容易了解，讲的特别好，主要是做个记录，以后可以翻阅。