Redis底层数据结构之双端链表

前言

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)；

____________________感谢阅读____________________