共计 2185 个字符，预计需要花费 6 分钟才能阅读完成。
上次咱们分享 Redis 字符串的底层原理，明天咱们再来看下 Redis List 列表的底层原理。
Redis List 命令
Redis List 列表反对的相干指令比拟多，比方单个元素减少、删除操作，也反对多个元素范畴操作。
Redis List 列表反对列表表头元素插入 / 弹出(LPUSH/LPOP )，也反对表尾元素插入 / 弹出(RPUSH/RPOP )。
另外 Redis List 列表还反对依据下标 (LINDEX ) 获取元素，也反对依据依据下标笼罩相应的元素(LSET )。
除此之外，Redis List 列表还反对的范畴操作，比方获取指定范畴内全副元素(LRANGE )，移除指定范畴内的全副元素(LTRIM )。
理解完的 Redis 相干指令，咱们来看下 Redis List 列表底层实现形式，应用两种数据结构：
- 压缩列表(ziplist)
- 双向列表(linkedlist)
ps: 本篇文章基于 Redis 3.2 开始进行解说
双向列表(linkedlist)
下面咱们晓得了 List 列表反对表头 / 表尾元素的插入 / 弹出，这类操作应用链表那就十分高效，工夫复杂度为 O(1)。
Redis 双向列表(linkedlist) 由两个构造形成：
- list
- listnode
构造如下：
list 构造体中保留了表头节点，表尾节点以及链表蕴含的节点的数量，正因为如此操作表头 / 表尾元素的插入 / 弹出，链表长度的计算将会十分高效，工夫复杂度为 O(1)。
listnode 构造体中除了保留节点的值以外，还会保留前后节点的指针，这样如果须要获取某个节点的前置节点与后置节点也会十分高效，工夫复杂度为 O(1)。
另外如果须要指定地位插入 / 删除元素，那么只须要变动以后地位节点前后指针即可，这个插入 / 删除操作复杂度为 O(1)。
不过须要留神了，插入 / 删除动作前提咱们须要找到这个指定地位，这个查找动作咱们只能遍历链表，复杂度为 O(N)，所以插入 / 删除的复杂度为 O(N)。
双向列表 (linkedlist) 除了用作在列表键以外，还宽泛用于公布 / 订阅，慢查问等外部操作。
既然双向列表 (linkedlist) 能够满足列表键的操作，那为什么 Redis 列表还采纳其余的数据结构？
其实次要是因为内存占用问题，双向链表因为应用两个构造体，而这两个构造体都须要保留一些必要信息，这必然将会占用局部内存。
而当元素很少的时候，如果间接应用双向链表，内存还是比拟节约的。所以 Redis 引入压缩列表。
压缩列表
压缩列表是 Redis 为了节约内存而开发，它由一系列的非凡编码的的 间断内存块 组成的程序型数据结构，整体构造如下：
从下面构造能够看进去，压缩列表实际上相似与咱们应用的数组，数组中每一个元素保留一个数据。
不过与数组不同的是，压缩列表的表头存在三个字段
zlbytes
zltail
zllen
另外压缩列表的表尾还有一个字段，zlend 外面保留一个非凡的值，OXFE，用于标记压缩列表的末端。
一个压缩列表能够由多个节点形成，每个节点能够保留整数值或字节数组，构造如下：
应用压缩列表，如果查找定位表头元素，咱们只须要应用压缩列表起始地址加上表头三个字段长度就能够间接点位，查找十分快，复杂度是 O(1)。
而压缩列表的最初一个元素，查找起来也十分轻松，咱们应用压缩列表起始地址加上 zltail 蕴含的长度就能够间接点位，查找也十分快，复杂度是 O(1)。
至于列表中的其余元素，就没有这么好运了，咱们只能从第一个元素或者最初一个元素，遍历列表查找，此时的复杂度就是 O(N) 了。
另外压缩列表的新增、删除元素，都将会导致从新分配内存，效率不高，均匀复杂度为 O(N)，最坏福复杂度为 O(N^2)。
编码转换
当咱们创立一个 Redis 列表键，如果同时满足以下两个条件，列表对象将会应用压缩列表作为底层数据结构
- 列表对象保留的所有字符串元素的长度都小于 64 字节
- 列表对象中保留的元素数量小于 512 个
如果不能同时满足这两个条件，那么默认将会应用双向列表作为底层数据结构。
小结
Redis 列表底层应用两种数据结构，压缩列表与双向链表。
压缩列表因为应用了间断内存块，内存占用少，并且内存利用率高，然而新增、删除因为波及从新分配内存，效率不高。
双向列表呢，新增、删除元素十分不便，然而因为每个节点都是独立的内存快，内存占用比拟高，且内存碎片化重大。
这两种数据结构在表头 / 表尾插入与删除元素，都非常高效。然而其余操作，可能就效率较低。
所以咱们应用 Redis 列表，肯定要就地取材，能够将其当做 FIFO 队列，这样仅应用 POP/PUSH，效率将会很高。
原文：www.tuicool.com/articles/N7nQ73r
参考资料
- Redis 设计与实现
举荐浏览
=====
** 从事开发一年的程序员能拿到多少钱？
**
字节跳动总结的设计模式 PDF 火了，完整版凋谢下载
刷 Github 时发现了一本阿里大神的算法笔记！标星 70.5K
** 程序员 50W 年薪的常识体系与成长路线。
**
对于【暴力递归算法】你所不晓得的思路
开拓鸿蒙，谁做零碎，聊聊华为微内核
=
看完三件事❤️
如果你感觉这篇内容对你还蛮有帮忙，我想邀请你帮我三个小忙：
点赞，转发，有你们的『点赞和评论』，才是我发明的能源。
关注公众号『Java 斗帝』，不定期分享原创常识。
同时能够期待后续文章 ing????
