本文转载自微信公众号《Java极客技术》，作者鸭血范。转载本文请联系Java极客技术公众号。大家好，我是阿粉~上次我们分享了Redis字符串的底层原理，今天我们就来看看RedisList列表的底层原理。RedisList命令RedisList列表支持很多相关命令，比如单个元素的增删操作，也支持多个元素范围操作。RedisList列表支持列表头元素（“LPUSH/LPOP”）的插入/出栈，也支持列表尾元素（“RPUSH/RPOP”）的插入/出栈。此外，RedisList列表还支持根据下标获取元素（“LINDEX”），也支持根据下标覆盖相应元素（“LSET”）。此外，RedisList列表还支持范围操作，例如获取指定范围内的所有元素（“LRANGE”）和移除指定范围内的所有元素（“LTRIM”）。了解了Redis的相关说明后，我们来看一下RedisList列表的底层实现，使用了两种数据结构：压缩列表（ziplist）双向列表（linkedlist）ps：本文开始讲解双向列表（linkedlist）)基于Redis3.2上面我们知道List列表支持插入/弹出header/tail元素。这种操作在使用链表时效率很高，时间复杂度为O(1)。Redis双向链表（linkedlist）由两种结构组成：listlistnode结构如下：list结构存储头节点、尾节点和链表中包含节点的个数，正因如此，header/tail的插入elements/popup，链表长度的计算会非常高效，时间复杂度为“O(1)”。listnode结构除了保存节点的值外，还保存了前后节点的指针，这样如果需要获取一个节点的前节点和后节点，效率会很高，而时间复杂度是“O(1)”。另外，如果需要在指定位置插入/删除元素，只需要改变当前位置节点前后的指针即可。这个插入/删除操作的复杂度是“O(1)”。但是需要注意的是，我们需要找到指定位置作为插入/删除动作的前提。这个查找动作我们只能遍历链表，复杂度是“O(N)”，所以插入/删除的复杂度是“O(N)”。.链表除了用作链表键外，还广泛用于发布/订阅、慢查询等内部操作。既然双向链表（linkedlist）可以满足链表键的操作，为什么Redis链表要用其他数据结构呢？其实主要是内存占用问题。双向链表使用了两个结构体，两个结构体都需要保存。一些必要的信息，必然会占用一部分内存。而且当元素不多的时候，如果直接使用双向链表，内存还是比较浪费的。所以Redis引入了压缩列表。压缩列表压缩列表是Redis为了节省内存而开发的。它是由一系列经过特殊编码的“连续内存块”组成的顺序数据结构。整体结构如下：从上面的结构可以看出，压缩列表其实类似于我们使用的数组，数组中的每个元素都保存着一条数据。不过与数组不同的是，压缩列表的头部有3个字段：zlbytes表示列表的长度，zltail表示列表末尾节点到压缩列表起始地址的偏移量，zllen表示个数ofnodesinthecompressedlist,andthetailofthecompressedlist还有一个字段，zlend持有一个特殊的值，OXFE，用来标记压缩列表的结束。压缩列表可以由多个节点组成，每个节点可以存储一个整数值或一个字节数组。字段长度可以直接点击，查找速度非常快，复杂度为O(1)。压缩列表的最后一个元素也很容易找到。我们可以使用压缩列表的起始地址加上zltail中包含的长度来直接点击。查找也很快，复杂度为O(1)。至于列表中的其他元素，我们就没那么幸运了。我们只能从第一个元素或最后一个元素开始搜索列表。此时的复杂度为O(N)。另外，压缩列表中元素的增删改查会导致内存重新分配，效率不高。平均复杂度为O(N)，最差复杂度为O(N^2)。编码转换当我们创建Redis列表键时，如果同时满足以下两个条件，列表对象将使用压缩列表作为底层数据结构。列表对象中存储的所有字符串元素的长度都小于64字节。列表对象存储的元素个数如果小于512，如果不能同时满足这两个条件，那么默认会使用双向列表作为底层数据结构。总结Redis链表底层使用了压缩链表和双向链表两种数据结构。因为压缩列表使用连续的内存块，所以占用内存少，内存利用率高。但是增删改查涉及重新分配内存，效率不高。至于双向链表，增删元素很方便，但是由于每个节点都有独立的内存，所以内存占用比较高，内存碎片比较严重。这两种数据结构在表头/表尾插入和删除元素的效率很高。但其他操作可能效率较低。所以，我们在使用Redis列表的时候，一定要因地制宜。可以看做是一个FIFO队列，这样只用POP/PUSH，效率会很高。参考资料Redis设计与实现
