redis链表结构

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵魂的调整链表长度。

链表和链表节点的实现

节点：

typedef struct listNode{
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
}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结构为链表提供了表头指针head，表尾指针tail，以及链表长度计数器len。
dup函数：用于赋值链表节点所保存的值。
free函数：用于释放链表节点所保存的值。
match：用于对比链表节点所保存的值和另一个输入的值是否相等。

redis链表实现的特性：
双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O（1）；
无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。
带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。
带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量复杂度

总结

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