title: 链表list
categories:
- C++ Backend
- Redis
- Redis command
- Data structure
tags:
- Redis
date: 2025-04-03 00:00:00
cover: /images/Redis.png

列表

列表操作

注意：list内部的编码方式，并非是一个简单的数组，而是更接近于双端队列。

列表特点

1. 列表中的元素是有序的，这意味着可以通过索引下标获取某个元素或者某个范围的元素列表。
2. 区分获取和删除的区别。lindex能获取到元素的值，lrem也能返回被删除元素的值。
3. 列表的元素是可以重复的。hash类型，field是不能重复的。

因为当前的List，头和尾都可以高效的插入和删除元素，就可以把这个list当做一个栈/队列来使用了。

相关指令

非阻塞版本命令

LPUSH

• 功能：将一个或者多个元素从头插到list中。
• 时间复杂度：$O(1)$。
• 返回值：插入list1之后的长度。
• 注意：如果key已经存在，并且key对应的value类型，不是list，此时lpush就要报错。

LPUSH key element [element...]

127.0.0.1:6379> lpush key 1 2 3 4
(integer) 4
127.0.0.1:6379> lpush key 5 6 7 8
(integer) 8

LRANGE

• 功能：查看list中start到end区间的元素。
• 注意：redis打印出的序号是结果集专用的序号。

LRANGE key start stop

27.0.0.1:6379> lrange key 0 -1
1) "8"
2) "7"
3) "6"
4) "5"
5) "4"
6) "3"
7) "2"
8) "1"

在Redis中如果出现越界访问的情况，是直接尽可能的获取到给定区间的元素，如果给定区间的元素，如果给定区间非法，比如超出下标，就会尽可能的获取对应的内容。此处越界下标的处理方式，更接近于python的处理方式。

缺点：程序员不一定能在第一时间发现问题。
优点：效率是最高的。

127.0.0.1:6379> lrange key 0 100
1) "8"
2) "7"
3) "6"
4) "5"
5) "4"
6) "3"
7) "2"
8) "1"

LPUSHX

功能：在key存在时，将一个或者多个元素头插到list中，不存在，直接返回。
时间复杂度：$O(1)$。
返回值：插入后list的长度。

LPUSHX key element [element ...]

127.0.0.1:6379> lpushx key1 1 2 3 4
(integer) 0
127.0.0.1:6379> lrange key1 0 -1
(empty list or set)

RPUSH

功能：将一个或者多个元素尾插到list中
时间复杂度：$O(1)$

RPUSH key element [element ...]

127.0.0.1:6379> rpush key 1 2 3 4
(integer) 4
127.0.0.1:6379> rpush key 5 6 7 8
(integer) 8
127.0.0.1:6379> lrange key 0 -1
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"
7) "7"
8) "8"

RPUSHX

功能：将一个或者多个元素尾插到list中，不存在，直接返回。
时间复杂度：$O(1)$

127.0.0.1:6379> keys *
1) "key"
127.0.0.1:6379> rpushx key 9 10 11 12
(integer) 12
127.0.0.1:6379> rpushx key1 9 10 11 12
(integer) 0

LPOP

功能：list头删
时间复杂度：O(1)
返回值：取出的元素或者nil

LPOP key

127.0.0.1:6379> lpop key
"1"
127.0.0.1:6379> lpop key
"2"
127.0.0.1:6379> lrange key 0 -1
 1) "3"
 2) "4"
 3) "5"
 4) "6"
 5) "7"
 6) "8"
 7) "9"
 8) "10"
 9) "11"
10) "12"

RPOP

功能：list尾删
时间复杂度：O(1)
返回值：取出的元素或者nil

RPOP key [count]

127.0.0.1:6379> rpop key
"12"
127.0.0.1:6379> rpop key
"11"
127.0.0.1:6379> lrange key 0 -1
1) "5"
2) "6"
3) "7"
4) "8"
5) "9"
6) "10"

LINDEX

功能：获取从左数第index个位置的元素，如果下标非法，返回的是空值

LINDEX key index

127.0.0.1:6379> lindex key 1
"6"
127.0.0.1:6379> lindex key -1
"10"

LINSERT

功能：在第一个特定元素的位置插入元素
返回值：返回插入之后链表的长度，选择插入的位置不存在时，返回-1。
时间复杂度：$O(N)$

LINSERT key <BEFORE | AFTER> pivot element

127.0.0.1:6379> linsert key before 4 100
(integer) -1
127.0.0.1:6379> lrange key 0 -1
1) "5"
2) "6"
3) "7"
4) "8"
5) "9"
6) "10"
127.0.0.1:6379> linsert key before 5 100
(integer) 7
127.0.0.1:6379> lrange key 0 -1
1) "100"
2) "5"
3) "6"
4) "7"
5) "8"
6) "9"

LLEN

功能：返回list长度。
时间复杂度：$O(N)$

127.0.0.1:6379> lrange key 0 -1
1) "100"
2) "5"
3) "6"
4) "7"
5) "8"
6) "9"
7) "10"
127.0.0.1:6379> llen key
(integer) 7

LREM

功能：删除list中的key
时间复杂度：$O(N + M)$

LREM key count element

count > 0：从左往右删除2个
count < 0：从右往左删除2个
count = 0：全部删除

LRTIM

功能：保留start和stop之间区间内的元素（区间外面两边的元素就直接被删除了）
时间复杂度：$O(N)$

LTRIM key start stop

127.0.0.1:6379> rpush key 1 2 3 4 5 6 7 8
(integer) 8
127.0.0.1:6379> ltrim key 2 5
OK
127.0.0.1:6379> lrange key 0 -1
1) "3"
2) "4"
3) "5"
4) "6"

LSET

功能：根据下标修改元素。注意，LSET越界会报错。
时间复杂度：$O(N)$

LSET key index element

127.0.0.1:6379> lset key 2 100
OK
127.0.0.1:6379> lrange key 0 -1
1) "3"
2) "4"
3) "100"
4) "6" 
127.0.0.1:6379> lset key 10 100
(error) ERR index out of range

阻塞版本命令

blpop和brpop是lpop和rpop的阻塞版本，和对应非阻塞版本的作用基本一致。

• 列表中有元素的情况下，阻塞和非阻塞表现是一致的。如果列表中没有元素，非阻塞版本就会理解返回nil，但阻塞版本会根据timeout，阻塞一段时间，期间redis可以执行其他命令，但要求执行该命令的客户端会表现为阻塞态。
• 命令中如果设置了多个键，那么会从左往右进行遍历键，一旦有一个键对应的列表中可以弹出元素，命令立即返回。
• 如果对个客户端同时多一个键执行pop，则最先执行命令的客户端会弹出的元素。

1. 如果list中存在元素，blpop和brpop就和lpop以及rpop作用完全相同。
2. 如果list中不存在元素，blpop和brpop就会产生阻塞，一直阻塞到队列不空为止。

BLPOP

此处可以指定一个或者多个key，每个key都对应一个list。

• 如果这些list中有任何一个非空，blpop都能够把这里的元素立刻获取到，立刻返回。
• 如果这些list1都为空，此时就需要阻塞等待，等待其他客户端往这些list中插入元素了。

BLPOP key [key....] timeout

1. 针对一个非空的列表进行操作：

返回的结果相当于一个pair(二元组)

• 一方面告诉我们当前的数据来自哪个key
• 一方面告诉我们取到的数据是什么。

127.0.0.1:6379> blpop key 0
1) "key"
2) "3"

2. 针对一个空的列表进行操作：

127.0.0.1:6379> blpop key 100
1) "key"
2) "1"
(10.06s)
127.0.0.1:6379> rpush key 1 2 3 4
(integer) 4

命令总结

内部编码

对于redis以前版本：

• ziplist（压缩列表）：当列表的元素个数小于list-max-ziplist-entries配置（默认512字节），同时每个列表的长度都小于list-max-ziplist-entries配置（默认64字节）时，Redis会选用ziplist来作为列表的内部编码来减少内存消耗。
• linkedlist（链表）：当列表类型无法满足ziplist条件时，Redis会选用linkedlist作为列表的内部实现。

对于Redis现在的版本：

• quicklist：quicklist相对于是链表和压缩列表的结合。整体还是一个链表，链表的节点，是一个压缩列表。

# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.   
# For a fixed maximum size, use -5 through -1, meaning:      
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2

应用场景

用list作为数组这样的结构，来存储多个元素。

消息队列

消费者通过brpop从队列中取任务。当list为空时，brpop就会阻塞等待，一直等到其他客户端想list中push了元素。

假设消费者执行顺序是：1 2 3

1. 当新元素到达之后，首先是消费者1拿到元素。
2. 消费之1拿到元素之后，也就从brpop返回了。如果消费者1还想继续消费，就需要重新执行brpop。
3. 此时再来一个新元素过来，就是消费者2拿到该元素也从brpop中返回。如果消费者2还想继续消费，也需要重新执行brpop。

分频道的消息队列

对于抖音来说：有一个通道来传输短视频数据，还可以有一个通道来传输弹幕，还可以有一个通道来传输点赞，转发，收藏数据。还可以有通道来传输评论数据。

微博Timeline

每个用户都有属于自己的Timeline（微博列表），现在需要分页展示文章列表。此时可以考虑使用列表，因为列表不但是有序的，同时支持按照索引范围获取元素。

1. 每篇微博使用哈希存储，例如微博中3个属性：title、timestamp、content

hmset mblog:1 title xx timestamp ... content xxx
...
hmset mblog:n title xx timestamp ... content xxx

2. 向用户timeline1添加微博，user::mblogs作为微博的jian键

lpush user:1:mblogs mblogs:1 mblog:3
...
lpush user:k:mblogs mblog:9

3. 分页获取用户的Timeline，例如用户的前10篇微博

keylist = lrange user:1:mblogs 0 9
for key in keylist
    hgetallkey

此方案在实际中存在问题：

1. 1 + n问题。即如果每次分页获取的微博个数较多，需要执行多次hgetall操作，此时可以考虑使用pipline流水线（将多个命令合并成一个网络请求进行通信）模式批量提交命令。或者微博不采用哈希类型，而是使用序列化的字符串类型，使用mget获取。
2. 分裂获取文章时，lrange在列表两端表现较好，获取列表中间的元素表现较差，此时可以考虑将列表做拆分。