列表（list）类型是用来存储多个有序的字符串，列表中的每个字符串称为元素(element)，一个列表最多可以存储232-1个元素。在Redis中，可以对列表两端插入（push）和弹出（pop），还可以获取指定范围的元素列表、获取指定索引下标的元素等。列表是一种比较灵活的数据结构，它可以充当栈和队列的角色，在实际开发上有很多应用场景

Redis list 数据类型 - 图1

列表类型有两个特点：

  1. 列表中的元素是有序的，这就意味着可以通过索引下标获取某个元素或者某个范围内的元素列表
  2. 列表中的元素可以是重复的

Redis list 内部实现

在Redis3.2版本以前列表类型的内部编码有两种。

  • ziplist（压缩列表）：当列表的元素个数小于list-max-ziplist-entries配置（默认512个），同时列表中每个元素的值都小于list-max-ziplist-value配置时（默认64字节），Redis会选用ziplist来作为列表的内部实现来减少内存的使用。
  • linkedlist（链表）：当列表类型无法满足ziplist的条件时，Redis会使用linkedlist作为列表的内部实现。

注意：而在Redis3.2版本开始对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist

Redis数据结构链表

Redis链表为双向无环链表！

链表是一种非常常见的数据结构，在Redis中使用非常广泛，列表对象的底层实现之一就是链表。其它如慢查询，发布订阅，监视器等功能也用到了链表

数组与链表

数组需要一块连续的内存来存储，这个特性有利也有弊。好处是其支持根据索引下标”随机访问”(时间复杂度为O(1))，但是其插入与删除操作为了保证在内存中的连续性将会变得非常低效(时间复杂度为O(N))，并且其一经声明就要占用整块连续内存空间，如果声明过大，系统可能内存不足，声明过小又可能导致不够用，而当数组的空间不足的时候需要对其进行扩容(申请一个更大的空间，将原数组拷贝过去,消耗性能)。

而链表恰恰相反，其不需要一块连续的内存空间，其通过”指针”将一组零散的内存连接起来使用。其优点在于本身没有大小限制，天然支持扩容，插入删除操作高效(时间复杂度为O(1))，但缺点是随机访问低效(时间复杂度为O(N))。并且由于需要额外的空间存储指针

Redis list 数据类型 - 图2

链表的实现方式有很多种，常见的主要有：

  • 单向链表
  • 双向链表
  • 循环链表

单向链表

Redis list 数据类型 - 图3

PS：

  • 单链表中每个节点除了包含数据之外还包含一个指针，叫后继指针，因此需要额外的空间来存储后继节点的地址。
  • 有两个特殊的节点：
    • 头结点：头节点用来记录链表的基地址，有了它就可以遍历整个链表
    • 尾节点：尾节点的后继指针不是指向下一个节点，而是指向一个空地址NULL表示这是链表上最后一个节点
  • 与数组一样，单链表也支持数据的查找、插入和删除操作，其中插入和删除操作只需要考虑相邻节点指针的变化，因此为常数级时间复杂度**O(1)**。要想随机访问第 k个元素，就没有数组那么高效了【插入删除效率高】。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点，因此时间复杂度为**O(N)**。

Redis list 数据类型 - 图4

双向链表

Redis list 数据类型 - 图5

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

  • 在有序链表中查找某个元素，单链表由于只有后继指针，因此只能从前往后遍历查找时间复杂度为O(N)，而双向链表可以双向遍历，因此可以采用二分的思想进行查找，时间复杂度为O(logn)
  • 删除给定指针指向的结点。假设已经找到要删除的节点，要删除就必须知道其前驱节点和后继节点，单链表想要知道其前驱节点只能从头开始遍历，时间复杂度为0(n)，而双向链表由于保存了其前驱节点的地址，因此时间复杂度为0(1)

循环链表

Redis list 数据类型 - 图6

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

Redis 双向无环链表

Redis list 数据类型 - 图7

如图所示，Redis使用一个listNode结构来表示

  1. typedef struct listNode
  2. { 
  3.     // 前置节点 
  4.     struct listNode *prev; 
  5.     // 后置节点 
  6.     struct listNode *next; 
  7.     // 节点的值 
  8.     void *value; 
  9. } listNode;

Redis List 数据结构

Redis list 数据类型 - 图8

  1. typedef struct list{
  2.     //表头节点
  3.     listNode *head;
  4.     //表尾节点
  5.     listNode *tail;
  6.     //链表所包含的节点数量
  7.     unsigned long len;
  8.     //节点值复制函数
  9.     void *(*dup)(void *ptr);
  10.     //节点值释放函数
  11.     void *(*free)(void *ptr);
  12.     //节点值对比函数
  13.     int (*match)(void *ptr,void *key);
  14. }list;

Redis链表结构其主要特性如下:

  • 双向：链表节点带有前驱、后继指针获取某个节点的前驱、后继节点的时间复杂度为0(1)
  • 无环： 链表为非循环链表表头节点的前驱指针和表尾节点的后继指针都指向NULL，对链表的访问以NULL为终点
  • 表头指针和表尾指针：通过list结构中的head和tail指针，获取表头和表尾节点的时间复杂度都为O(1)
  • 链表长度计数器：通过list结构的len属性获取节点数量的时间复杂度为O(1)
  • 多态：链表节点使用void*指针保存节点的值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用来保存各种不同类型的值。

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

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

操作\时间复杂度 数组 单链表 双向链表
rpush(从右边添加元素) O(1) O(1) O(1)
lpush(从左边添加元素) 0(N) O(1) O(1)
lpop (从右边删除元素) O(1) O(1) O(1)
rpop (从左边删除元素) O(N) O(1) O(1)
lindex(获取指定索引下标的元素) O(1) O(N) O(N)
len (获取长度) O(N) O(N) O(1)
linsert(向某个元素前或后插入元素) O(N) O(N) O(1)
lrem (删除指定元素) O(N) O(N) O(N)
lset (修改指定索引下标元素) O(N) O(N) O(N)

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

Redis 数据结构压缩列表

在Redis hash数据类型的时候了解过压缩列表，详看Redis hash 哈希数据类型
当列表的元素个数小于list-max-ziplist-entries配置（默认512个），同时列表中每个元素的值都小于list-max-ziplist-value配置时（默认64字节），Redis会选用ziplist来作为列表的内部实现来减少内存的使用。

Redis数据结构quicklist

链表和压缩列表是Redis List(列表)对象的底层实现方式。但是考虑到链表的附加空间相对太高，**prev** 和 **next** 指针就要占去 16 个字节 (**64bit** 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。因此**Redis3.2**版本开始对列表数据结构进行了改造，使用 **quicklist** 代替了 **ziplist** 和 **linkedlist**.

Redis list 数据类型 - 图9

quicklist结构

quicklist 实际上是 zipList 和 linkedList 的混合体，它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来

Redis list 数据类型 - 图10

  1. typedef struct quicklistNode {
  2.     struct quicklistNode *prev; //上一个node节点
  3.     struct quicklistNode *next; //下一个node
  4.     unsigned char *zl;            //保存的数据 压缩前ziplist 压缩后压缩的数据
  5.     unsigned int sz;             /* ziplist size in bytes */
  6.     unsigned int count : 16;     /* count of items in ziplist */
  7.     unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
  8.     unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
  9.     unsigned int recompress : 1; /* was this node previous compressed? */
  10.     unsigned int attempted_compress : 1; /* node can't compress; too small */
  11.     unsigned int extra : 10; /* more bits to steal for future usage */
  12. } quicklistNode;
  • prev： 指向链表前一个节点的指针。
  • next：指向链表后一个节点的指针。
  • zl： 数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF结构。
  • sz：表示zl指向的ziplist的总大小（包括zlbytes, zltail, zllen, zlend和各个数据项）。需要注意的是：如果ziplist被压缩了，那么这个sz的值仍然是压缩前的ziplist大小。
  • count： 表示ziplist里面包含的数据项个数。这个字段只有16bit。稍后我们会一起计算一下这16bit是否够用。
  • encoding：表示ziplist是否压缩了（以及用了哪个压缩算法）。目前只有两种取值：2表示被压缩了（而且用的是LZF压缩算法），1表示没有压缩。
  • container：是一个预留字段。本来设计是用来表明一个quicklist节点下面是直接存数据，还是使用ziplist存数据，或者用其它的结构来存数据（用作一个数据容器，所以叫container）。但是，在目前的实现中，这个值是一个固定的值2，表示使用ziplist作为数据容器。
  • recompress：当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩。
  • attempted_compress： 这个值只对Redis的自动化测试程序有用
  • extra： 其它扩展字段。目前Redis的实现里也没用上。
  1. typedef struct quicklistLZF {
  2.     unsigned int sz; /* LZF size in bytes*/
  3.     char compressed[];
  4. } quicklistLZF;

quicklistLZF结构表示一个被压缩过的ziplist其中：

  • sz ：表示压缩后的ziplist大小
  • compressed： 是个柔性数组（flexible array member），存放压缩后的ziplist字节数组

quicklist操作

1. 插入操作

quicklist可以选择在头部或者尾部进行插入(quicklistPushHead和quicklistPushTail)，而不管是在头部还是尾部插入数据，都包含两种情况：

  • 如果头节点（或尾节点）上ziplist大小没有超过限制（即_quicklistNodeAllowInsert返回1），那么新数据被直接插入到ziplist中（调用ziplistPush）。
  • 如果头节点（或尾节点）上ziplist太大了，那么新创建一个quicklistNode节点（对应地也会新创建一个ziplist），然后把这个新创建的节点插入到quicklist双向链表中。

Redis list 数据类型 - 图11

也可以从任意指定的位置插入quicklistInsertAfter和quicklistInsertBefore就是分别在指定位置后面和前面插入数据项。这种在任意指定位置插入数据的操作，要比在头部和尾部的进行插入要复杂

  • 当插入位置所在的ziplist大小没有超过限制时，直接插入到ziplist中就好了；
  • 当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小没有超过限制，那么就转而插入到相邻的那个quicklist链表节点的ziplist中；
  • 当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小也超过限制，这时需要新创建一个quicklist链表节点插入
  • 对于插入位置所在的ziplist大小超过了限制的其它情况（主要对应于在ziplist中间插入数据的情况），则需要把当前ziplist分裂为两个节点，然后再其中一个节点上插入数据

2. 查找操作

list的查找操作主要是对index的我们的quicklist的节点是由一个一个的ziplist构成的每个ziplist都有大小。所以我们就只需要先根据我们每个node的个数，从而找到对应的ziplist，调用ziplist的index就能成功找到

3. 删除操作
  • 区间元素删除的函数是 quicklistDelRange
  • quicklist 在区间删除时，会先找到 start 所在的 quicklistNode，计算删除的元素是否小于要删除的 count，如果不满足删除的个数，则会移动至下一个 quicklistNode 继续删除，依次循环直到删除完成为止。
  • quicklistDelRange 函数的返回值为 int 类型，当返回 1 时表示成功的删除了指定区间的元素，返回 0 时表示没有删除任何元素。

4. 其它操作

除了上面介绍的基本操作之外还有一些其它操作，大家可以尝试着根据链表和压缩列表的数据结构来分析一些quicklist这些操作的时间复杂度

操作 时间复杂度
quicklistCreate:创建 quicklist ？
quicklistInsertAfter：在某个元素的后面添加数据 ？
quicklistInsertBefore：在某个元素的前面添加数据 ？
quicklistReplaceAtIndex：替换某个元素 ？
quicklistDelEntry：删除单个元素 ？
quicklistDelRange：删除区间元素 ？
quicklistPushHead:头部插入元素 ？
quicklistPushTail:尾部插入元素 ？