前言
Redis的双端链表是基于双向链表实现的,但传统双向链表存在一些问题,比如获取链表长度需要遍历整个链表,时间复杂度是O(n),影响性能,所以Redis在内部自己实现了一套双端链表。
何谓双向链表
双向链表也叫双链表。
双向链表中不仅有指向后一个节点的指针,还有指向前一个节点的指针。
这样可以从任何一个节点访问前一个节点,当然也可以访问后一个节点,以至整个链表。
一般是在需要大批量的另外储存数据在链表中的位置的时候用。
其结构如下图:
来自维基百科-链表.png
Redis版本的双端链表
Redis 为了更方便的操作链表,在链表之上封装了一个链表结构 list:
typedef struct list {
// 表头结点
listNode *head;
// 表尾节点
listNode *tail;
// 链表所包含的节点数量
unsigned long len;
// 其他函数
...
}list;
list 结构为链表提供了表头指针 head, 表尾指针 tail, 以及链表长度的计数器 len. 来方便的对链表进行一个双端的遍历,或者查看链表长度。
list的head和tail分别指向真实链表节点的头尾,链表节点的结构如下:
链表节点的定义:
typedef struct listNode{
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
}listNode
通过这两个结构,我们就可以构造出来一个Redis的链表了,如下图:
《Redis 的设计与实现(第二版)》
Redis 双端链表结构的主要特点:
头尾指向null,所以是无环链表;
封装了 list 结构,保存了链表的头尾指针以及链表长度,可以快速的执行正向或反向遍历;
带有长度计数器,因此对链表长度的统计时间复杂度是 O(1);
____________________感谢阅读____________________
网友评论