链表提供了高效的节点重排能力,以及程序性的节点拜访形式,并且能够通过增删节点来灵便调整链表的长度。
因为 Redis 应用的 C 语言并没有内置这种数据结构,所以 Redis 构建了本人的链表实现。
链表在 Redis 中的利用十分宽泛,比方 列表键(list
)的底层实现之一就是链表。当一个列表键蕴含了数据比拟多的元素,又或者列表中蕴含的元素都是比拟长的字符串时,Redis 就会应用链表作为列表键的底层实现。
当一个列表键只蕴含大量列表项,并且每个列表项是小整数值,或者长度比拟短的字符串,Redis 应用压缩列表来作为列表键的底层实现。
除了列表键之外,公布订阅 、 慢查问 、 监视器 等性能也用到了链表,Redis 服务器自身还应用链表来 保留多个客户端的状态信息 ,曾经应用链表来 构建客户端输入缓冲区。
链表节点(listNode)的实现
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
}
其中:
prev
:代表以后节点的前置节点next
:代表以后节点多个的后置节点value
:代表以后节点的值
链表(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);
}
其中:
head
: 表头节点的指针tail
: 表尾节点的指针len
: 链表长度计数器dup
: 用于复制链表节点所保留的值free
: 用于开释链表节点所保留的值match
: 用于比拟链表节点所保留的值和另一个值是否相等
个性
Redis 的链表实现中,节点都带有 prev
和 next
指针,且链表中也存储了 head
(表头节点指针)和 tail
(表尾节点指针),为 双向链表,在获取某个节点的前置节点和后置节点的工夫复杂度都是 O(1),获取链表的表头节点和表尾节点工夫复杂度同样也是 O(1);
但并非是循环链表,因为表头节点的 prev
和表尾节点的 next
指针都指向 null
;
链表节点中应用 void*
来存储了节点值的指针,并未限度存储类型,能够保留各种不同类型的值。