- 链表提供了高效的节点重排的能力
- 顺序访问的能力 发布订阅,慢查询,监视器等都用到了链表
链表结构
typedef struct listNode {
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
}
多个listNode可以通过prev和next链接为双向链表
typdef struct list {
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表包含的节点数量
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void *(*free)(void *ptr);
//节点值对比函数
void *(*match)(void *ptr, void *key);
}
redis链表实现的特性:
- 双端:每个节点都存在prev和next指针,获取某个节点前后指针为O(1)
- 无环:头节点和尾节点的prev和next为null,对链表的访问以null终止
- 带有表头和表尾指针,自带表头和表尾指针,查找表头和表尾指针为O(1)
- 待链表长度计数器:获取链表长度为O(1)
- 多态:链表的值为*void,而且可以通过绑定不同的dup,free,match函数,可以保存不同类型的值