redis数据结构之链表

1.1简介

作为一种常用的数据结构，链表提供了高效的节点重排能力，以及搞笑的书序访问能力，同时可以通过增删节点调整长度。

1.2链表构成

redis中每个链表节点使用一个adlist.h/listNode结构表示；

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

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

redis对链表属性做了优化，通过adlist.h/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结构提供了表头表尾指针、链表长度计数器，以及dup/free/match用于实现多态链表的函数。

1.3链表特性总结

1.3.1双端：

因为next和prev指针的存在，获取节点的前置和后置节点复杂度皆为O(1)；

1.3.2无环：

表头prev指针和表尾next指针都指向NULL，访问链表时NULL为终点；

1.3.3表头和表尾指针：

通过list结构可以O(1)负责度的获取表头和表尾指针；

1.3.4长度计数器:

O(1)复杂度的获取表的长度；

1.3.5多态：

链表使用*void指针保存节点值，可以兼容各种不同类型的值的存储；