本文共 1070 字,大约阅读时间需要 3 分钟。
链表提供高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点调整链表的长度。
在Redis中,当一个列表键包含数量比较多的元素或元素都是比较长的字符串时,Redis就会使用链表作为列表键的底层实现。链表节点:
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) //节点值对比函数 int (*match)(void *ptr,void *key) }
图:
Redis链表实现特性总结:
1.双端:链表节点带prev,next指针。 2.无环:表头节点的prev指针和表位节点的next指针都指向NULL 3.长度计数器:len属性记录链表节点数量 4.多态:节点使用void*指针保存节点值,通过list的dup、free、match属性为节点值设定类型特殊函数,因此可保存不同类型的值。函数 | 作用 | 时间复杂度 |
---|---|---|
listLength | 获取链表的长度 | O(1) |
listFirst | 获取链表表头节点 | O(1) |
listLast | 获取链表表尾节点 | O(1) |
listPrevNode | 返回给定节点的前置节点 | O(1) |
listNextNode | 返回给定节点的后置节点 | O(1) |
listNodeValue | 返回给定节点的值 | O(1) |
listCreate | 创建一个新的链表 | O(1) |
listAddNodeHead | 添加一个给定的新节点到表头 | O(1) |
listAddNodeTail | 添加一个给定的新节点到表尾 | O(1) |
listSearchKey | 查找并返回链表中包含给定值的节点 | O(1) |
转载地址:http://hykai.baihongyu.com/