前面文章讲解了Redis知识框架和String原理，文章链接如下：
《每个程序员都应该知道的Redis知识》、《每个程序员都应该知道的Redis知识 - String底层原理》

**本文将继续讲解Reids知识之List类型的实现原理。**我们知道Redis的list类型给我们提供了很多操作数据的命令（详细命令见文章末尾），比如 LPUSH 可以将一个或多个值插入到列表头部，LRANGE 可以获取指定范围内的元素。由此我们产生了一个疑问，这些在底层是如何实现的？

我将从以下两个方面介绍List类型：

• List类型的实现原理
• List中各个命令的查询原理
• 
  

一、List类型实现原理

List的底层是实现是链表，说到链表不得不提的就是数组。那么链表和数组两种数据结构有什么不同呢？

数组是顺序存储的，在内存中的存储方式是连续的；链表是链式存储，在内存中是非连续性存储

访问数组中的数据的时间复杂度是O(1)，而链表必须从表头顺序去访问，时间复杂度是O(n)

链表上任意节点删除效率比数组高

Redis的List类型底层是通过list和listNode两个结构体实现，代码见下图：

从上图可以看出，listNode是一个双向链表的节点，多个listNode通过prev和next指针组成双端链表。

为了更加方便的操作，使用list结构体来持有链表。list结构为链表提供了表头指针head、表尾指针tail，以及链表节点数量len，dup、free、match成员则是为了实现链表功能而提供的接口。

dup函数用于复制链表节点所保存的值
free函数用于释放链表节点所保存的值
match函数用于对比链表节点所保存的值和另一个输入值是否相等由list结构和listNode组成的链表如下图所示，这就是Redis中list类型的实现。

通过上图我们可以发现：

链表是双端结构，listNode结构体中带有prev和next指针，因此获取某个节点的前置节点和后继节点的时间复杂度都是O(1)

这个链表无环：表头节点的prev和表尾节点的next指针都指向了NULL，对链表的访问以NULL为终点

带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链接的表头节点和表尾节点的时间复杂度为O(1)

带有链表长度计数器：程序使用list结构体的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O(1)

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

二、List中各个命令是如何实现的？

以上就是list类型的实现，下面我们用具体的命令来验证一下，底层是如何实现数据增删改查的。

**BLPOP key1：**这个命令是从链表的头部移出并获取返回移出的值。从上图可以看出，list结构体持有整个链表，通过head指针用O(1)的时间复杂度就可以找到链表第一个节点，然后通过链表删除某个节点的操作就可以移除节点。BRPOP key 的操作也类似，通过list链表的tail指针就可以使用O(1)的时间复杂度找到节点，剩下的操作类似

**LLEN key：**这个命令是获取链表的长度，因为list结构体中已经存储了链表长度len，多以查询的时间复杂度是O(1)

**LPUSH key value：**这个命令是将一个或多个值插入到链表头部。同样也是通过list链表中的head指针来实现链表的插入

从上面的几个例子可以看出，Redis中对list类型的增删改成都是通过对双向链表的增删改查来实现的。关于链表的增删改查后面会专门写文章来介绍。

除此之外，我们看到list结构体中设置了len属性，查询链表长度就不需要遍历整个链表，这也是一种空间换时间的思想。

这篇文章就为大家介绍到这里，如有不足，还请见谅！

为方便大家查找命令，下面列出了Redis命令列表：