Redis（八）-Redis的list列表的数据结构-快速链表

链表回顾

链表和数组

数组时需要一块连续的内存空间来存储的，而链表值需要零散的内存碎片，数组的插入和删除的时间复杂度是0(n)，查询的某个元素的时间复杂度是O(1)。而链表插入和删除的时间复杂度是O(1)，查询某个节点的时间复杂度是O(n)通过指针相连即可。如下图所示：

单链表

单链表是最简单的链表，链表中的每一个内存块称之为“结点”，每个结点Node包含两个部分，数据域data和后继指针next。单链表的第一个结点称为头结点，头结点记录了链表的基地址。其next指针指向下一个结点，通过头结点可以遍历整个链表，最后一个结点称为尾结点，尾结点的next指针指向空地址NULL。更多关于单链表的知识可以参考第八篇：链表的学习：链表的头插法和尾插法以及HashMap中链表结点的插入方式

双端链表

与单链表不同的是双向链表多了一个前驱指针prev。需要额外的空间存储前驱结点的地址，因此存储同样的数据，双端链表占用比单链表更多的空间，但是其优点是支持双向遍历。体现在如下两个方面：

1.在有序链表中查找某个元素，单链表由于只有后继指针，因此只能从前往后遍历查找时间复杂度为O(N)。双端链表可以双向遍历。

2.删除给定指针指向的结点，假设已经找到要删除的结点，要删除就必须知道其前驱节点和后继结点。单链表想要知道其前驱节点，就必须从头开始遍历。而双端链表由于保存了其前驱节点，因此时间复杂度是O(1)。

循环链表

循环链表与单链表和双链表的不同之处是其呈环装。单循环链表中其尾节点并非指向NULL而是指向头节点。双循环链表其头节点的前驱指针指向尾节点。尾节点的后继指针指向头节点。循环链表的优势在于链尾到链头，链头到链尾比较方便。适合处理具有环形结构的数据。

Redis的链表

Redis链表使用的是双端无环链表。如下列表命令从左边添加元素：lpush lists 1 2 3。就是通过链表左边设置了三个元素。

链表的结构

Redis使用一个listNode结构来表示链表的结点。

typedef struct listNode
  { 
    // 前置节点 
    struct listNode *prev; 
    // 后置节点 
    struct listNode *next; 
    // 节点的值 
    void *value; 
  } listNode;

用结构图表示就是：

同时Redis为了方便操作链表，提供了一个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;

其中：

1.head记录了表头指针；

2.tail记录了表尾指针

3.len记录了链表长度，是链表长度计数器

dup、free和match成员则是用于实现多态链表所需的类型特定函数；

4.dup函数用于复制表节点所保存的值

5.free函数用于释放链表节点所保存的值

6.match函数则是用于对比链表节点所保存的值和另一个输入值是否相等。

下图就是由一个list结构和三个listNode结构组成的链表

链表的特性

1.双端：链表节点带有前驱、后继指针；获取某个节点的前驱、后继节点的时间复杂度是O(1)。

2.无环：链表为非循环链表表头节点和前驱指针和表尾的后继指针指向NULL,对链表的访问以NULL为终点。

3.带表头指针和表尾指针：通过list结构中的head和tail指针，获取表头和表尾节点的时间复杂度都是O(1)。

4.多态：链表节点使用void* 指针保存节点的值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用来保存不同的类型的值。

双端无环链表在Redis中的使用

链表在Redis中的应用非常广泛，列表对象的底层实现之一就是链表，此外如发布订阅、慢查询、监视器等功能也用到了链表，我们现在简单想一想为什么使用双端无环链表，而不是数组、单向链表等。既然列表对象的底层实现之一是链表，那么我们可以通过一个表格来分析一下列表对象的常用操作命令，如果分别使用数组、单链表和双端链表实现列表对象的时间复杂度对照如下：

但是双向链表因为使用两个额外的空间存储前驱和后继指针，因此在数据流较小的情况下会造成空间上的浪费（因为数据流小的时候速度上差别不大，但空间上差别很大）。这是一个时间换空间还是空间换时间的思想问题。Redis在列表对象中小数据量的时候使用压缩列表来作为底层实现，而大数据量的时候才会使用双向无环链表。

总结

本文首先对链表的相关知识点做了一个回顾，简单的介绍了单链表，双端链表，循环链表。接着就是着重介绍了Redis中的链表结构，Redis的链表采用的是双端无环链表。通过list结构来操作链表。