Redis是一组连接起来的字符串集合。

旧版本的List最大元素数量是2^32 – 1个，新版本的最大元素数量是2^64 – 1。

用于存储一批任务、或一批消息等。

一、List的语法

1、LPUSH

语法：LPUSH key value [value …]

​功能：从头部增加元素，返回值为List中元素的总数。

127.0.0.1:6379> LPUSH list s1 s2 s3​
(integer) 3

​​127.0.0.1:6379> LPUSH list s4​
(integer) 4

s4是第二个命令插入的，插入之后它就在List头部，此时List结构如下：

2、RPUSH

语法：RPUSH key value [value …]​

功能：从尾部增加元素，返回值为List中元素的总数。

127.0.0.1:6379> RPUSH list s5​
(integer) 5

s5是用RPUSH命令插入的，插入之后它就在List尾部，此时List结构如下：

3、LPOP

语法：LPOP key​

功能：移出并获取列表的第一个元素。

127.0.0.1:6379> LPOP list
"s4"

s4从List中移除，此时List结构如下：

4、RPOP

语法：RPOP key​

功能：移出并获取列表的最后一个元素。

127.0.0.1:6379> RPOP list
"s5"

s5从List中移除，此时List结构如下：

5、LREM

语法：LREM key count value​

功能：移除值等于value的元素。当count=0，则移除所有等于value的元素。当count>0，则从左到右开始移除count个。当count<0则从右到左移除count个。返回值为被移除元素的数量。

127.0.0.1:6379> LREM list 0 s2​
(integer) 1

6、DEL

语法：DEL key [key …]​

功能：删除对象，返回值为删除成功了几个键。

127.0.0.1:6379> DEL list
(integer) 1

7、UNLINK

语法：UNLINK key [key …]​

功能：删除对象，返回值为删除成功了几个键。和DEL主要有如下不同：

del 命令同步删除命令，会阻塞客户端，直到删除完成。 unlink 命令是异步删除命令，只是取消Key在键空间的关联，让其不再能查到，删除是异步进行，所以不会阻塞客户端。

构造list如下，用于以下读操作

8、LLEN

查看元素个数

127.0.0.1:6379> LLEN list
(integer) 3

9、LRANGE

语法：LRANGE key start stop

​功能：查看start到stop为角标的元素。

127.0.0.1:6379> LRANGE list 0 1
​1) "s3"​
2) "s2"

start、stop如果为负数，表示倒数第几个元素：

127.0.0.1:6379> LRANGE list -2 -1​
1) "s2"​
2) "s1"

二、List的底层实现

List在旧版本底层实现有两种：ZIPLIST和LINKEDLIST

ZIPLIST对内存友好，因为元素节凑排列，省去了指针的内存空间，适合元素比较小，且数量少的场景，因为内存紧凑排列，所以元素修改的时候，可能会发生复制，性能会差一些，所以不适合元素多的场景。

LINKEDLIST相当于是链表，需要指针来将元素相连，所以适合元素多，或者占用空间大的场景，因为增删改元素，不用大面积复制。

新版本用QUICKLIST，相当于是ZIPLIST的链表，所以有结合两者的优点。面试常问的仍然是ZIPLIST。

ZIPLIST：

ZIPLIST中有下面几个字段需要留意：

1、zlbytes：记录ziplist占用的空间大小

2、zltail：记录最后一个元素偏移的字节数，用于快速定位到最后一个元素（最后一个entry，不存在定位到zlend）

3、zllen：记录有多少个数据节点，但是zllen只有两个字节，所以当元素数量大于65535的时候，就存不下了，必须要遍历所有节点，才能得到节点数量，但ziplist本身设计就是适用于节点数量少的场景。

4、中间是元素entry

5、zlend：特殊节点，标记ziplist结束。

entry的结构：

1、prevlen：上一个节点的数据长度，通过这个可以定位到上一个节点的起始地址，从而实现倒序遍历。但也是因为这个字段，会引起连锁更新反应。连锁更新反应是这样的，后面一个节点，记录了前面一个节点的大小，但是如果前面一个节点的大小变化很大，导致后一个节点的prevlen原本1个字节不够用，需要扩容，那么后一个节点的下一个节点的prevlen也要更新，触发连锁更新。

2、encoding：

encoding一般分为两个部分，前面几个bit用来记录是什么类型的数据，后面几个bit用来记录数据的长度。

3、entrydata：真实数据

ZIPLIST查询数据

通常是O(1)，可能是O(n)，因为zllen只有2个字节

查询一个指定的数据是O(n)，因为要遍历数据

ZIPLIST更新数据

更新数据的复杂度是O(n)，因为在头部插入节点，所有节点都要往后移动

包括前面提到，会触发连锁更新问题

LISTPACK

LISTPACK通过element-tot-len字段来解决连锁更新的问题。连锁更新问题的根源在于prevlen，LISTPACK用element-tot-len来代替prevlen，用来记录前一个entry节点的长度。

记录前一个节点的长度，是为了从后向前遍历。于是element-tot-len里面每一个字节用第一个bit来标记element-tot-len是否结束，1代表继续，0代表结束。每个字节后面的7个bit用来记录真实的长度数据。

这样前一个entry节点的长度就不用记录在后一个节点中，从而也就不会触发连锁更新。

三、List面试题

1、List是完全先入先出吗？

List是双端操作对象，可以先进先出，也可以先进后出

2、List如何获取指定范围内的数据

用LRANGE，可以指定start end

3、List如何移除特定值的数据？时间复杂度是多少

LREM key count value，移除这个key对应的List里面值为value的数据，移除count个，count>0时，从左往右数count个，count<0时，从右往左数count个。由于需要遍历整个List，所以复杂度是O(n)

4、List对象底层编码方式是什么？

我用的是5.0.5版本，List对象的编码全部由QUICKLIST实现。QUICKLIST是一个由ZIPLIST和LINKEDLIST组成的双向链表，结合了ZIPLIST和LINKEDLIST两者的优点。

旧的版本里面，对于数据少的时候，用的ZIPLIST，元素紧凑排列，节约内存（节省链表指针的内存）。数据多的时候，用的LINKEDLIST，性能更好一些。QUICKLIST结合了这两者的优点，它是由ZIPLIST组成的LINKEDLIST，兼顾了性能和内存。

5、LINKEDLIST编码下，查询节点个数的复杂度是多少？

LINKEDLIST的表头结构里面，有个len字段，代表链表的节点个数，所以查询节点个数的复杂度是O(1)。

// from Redis 5.0.5​
typedef struct list {
​    listNode *head;​
    listNode *tail;
​    void *(*dup)(void *ptr);​
    void (*free)(void *ptr);
​    int (*match)(void *ptr, void *key);
​    unsigned long len;​
} list;