1. 作用
Redis中链表被广泛运用在很多地方,例如
列表键,发布订阅,慢查询,监视器,Redis服务器本身还是要链表保存多个客户端状态信息,以及运用链表构建客户端输出缓冲区
2. 数据结构
typedef struct listNode{
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
}
typedef struct list{
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表所包含的节点数量
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void *(*free)(void *ptr);
//节点值对比函数
void *(*match)(void *ptr,void *key)
}
3. Redis链表特点
3.1. 双端
链表节点带有prev和next指针,获取某个节点的前置节点和后置节点的复杂度都是O(1)
3.2. 无环
表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以NULL为终点
3.3. 带表头指针和表尾指针
通过list结构的head指针和tail指针,获取链表头尾的负责度是O(1)
3.4. 带链表长度计数器
程序使用list结构的len属性来对list持有的节点数量计数,获取长度时间复杂度为O(1)
3.5. 多态
链表节点使用void* 指针来保存节点值,并且可以通过list结构的dup,free,match三个属性为解ID那设置特定类型的函数,所以链表可以存放不同类型值