面试题42：介绍一下Redis中list类型的实现方式是什么？

【概述】

• 适用场景：消息队列。
• 它的特点：内部元素有序、重复，并且插入和删除很快O(1)，但是查找却很慢O(n)。功能支持队列和栈操作。

【内部实现】

• 列表对象的编码支持ziplist和linkedlist两种。

【ziplist】

• ziplist编码列表对象，采用压缩列表实现。每个列表节点保存一个列表中的元素。比如我们插入a、b、c三个元素到列表中：

127.0.0.1:6379> RPUSH testlist a b c
(integer) 3

那么它的存储结构是这样的：

【linkedlist】

• linkedlist编码列表对象，采用双向链表作为底层实现，每个列表节点保存一个列表中的元素。
• 数据结构如下：

【编码转换规则】

• 同时满足一下两个条件时，是ziplist类型，否则为linkedlist类型：
  • 条件1：列表中所有元素长度都小于66字节。
  • 条件2：列表中元素的个数小于512个。
• 示例如下所示：

127.0.0.1:6379> RPUSH testlist a b c
(integer) 3
127.0.0.1:6379> OBJECT encoding testlist
"ziplist"
127.0.0.1:6379> RPUSH testlist 12345678901234567890123456789012345678901234567890123456789012345
(integer) 5
127.0.0.1:6379> OBJECT encoding testlist
"linkedlist"