链表提供了高效的节点重排能力，以及顺序性的节点访问方式，可以通过增删节点来灵活地调整链表的长度。
链表在Redis中应用：
- 列表键的底层实现：当一个列表键包含数量比较多的元素，或者列表中包含的元素都是比较长的字符串时；
- 发布与订阅
- 慢查询
- 监视器
- Redis服务器使用链表保存多个客户端的状态信息
- 使用链表构建客户端输出缓冲区
链表和链表节点实现
链表节点结构
typedef struct listNode{
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
}listNode；
多个listNode可以通过prev和next指针组成双端链表
WechatIMG53.jpeg
使用adlist.h/list来持有链表的话，操作起来会更方便
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;
WechatIMG54.jpeg
Redis 链表实现的特性总结：
- 双端：链表节点带有prev和next指针，获取前置节点和后置节点的复杂度都是0(1);
- 无环：表头节点的prev指针和表尾节点的next指针都指向null，对链表的访问以null为终点；
- 带表头指针和表尾指针：通过list结构的head指针和tail指针，获取链表的表头节点和表尾节点的复杂度为O(1).
- 带链表长度计数器：使用list结构中len属性，对list持有的链表节点进行计数，获取链表中节点数量复杂度为O(1);
- 多态：使用void* 指针保存节点的值，可以通过list结构的dup，free，match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。
链表和链表节点的API
| 函数：作用 | 时间复杂度 |
|---|---|
| listSetDupMethod:将给定的函数设置为链表的节点值复制函数 | O(1) |
| listGetDupMethod:返回链表当前正在使用的节点值复制函数 | O(1) |
| listSetFreeMethod:将给定的函数设置为链表的节点值释放函数 | O(1) |
| listGetFree:返回链表当前正在使用的节点值释放函数 | O(1) |
| listSetMatchMethod:将给定的函数设置为链表的节点值对比函数 | O(1) |
| listGetMatchMethod:返回链表当前正在使用的节点值对比函数 | O(1) |
| listLength:返回链表的长度 | O(1) |
| listFirst:返回链表的表头节点 | O(1) |
| listLast:返回链表的表尾节点 | O(1) |
| listPrevNote:返回给定节点的前置节点 | O(1) |
| listNextNode:返回给定节点的后置节点 | O(1) |
| listNodeValue:返回给定节点目前正在保存的值 | O(1) |
| listCreate:创建一个不包含任何节点的新链表 | O(1) |
| listAddNodeHead:将一个包含给定值的新节点添加到给定链表的表头 | O(1) |
| listAddNodeTail:将一个包含给定值的新节点添加到给定链表的表尾 | O(1) |
| listInsertNode:将一个包含给定值的新节点添加到给定节点的之前或者之后 | O(1) |
| listSearchKey:查找并返回链表中包含给定值的节点 | O(n) |
| listIndex:返回链表在给定索引上节点 | O(n) |
| listDelNode:从链表中删除给定的节点 | O(n) |
| listRotate:将链表的表尾节点弹出，然后将被弹出的节点插入到链表的表头，称为新的表头节点 | O(1) |
| listDup:复制一个给定链表的副本 | O(n) |
| listRelease:释放给定链表，以及链表中所有的节点 | O(n) |
网友评论