【Redis从入门到精通】第12篇：链表——Redis列表的底层支撑（含源码解析）

上一篇【第11篇】SDS实战——Redis字符串操作背后的黑科技
下一篇【第13篇】哈希表——Redis字典的核心数据结构

摘要

链表是最基础的数据结构之一，但Redis把它实现了相当漂亮。本文从源码层面对Redis链表的listNode和list结构体做逐字段拆解，配合ASCII内存布局图帮你建立直观印象。我们会详细分析链表的四大特性（双端/无环/带头尾指针/带长度计数），掌握链表迭代器的正向/逆向遍历机制。然后讨论为什么Redis 3.2之后用quicklist替代了纯链表，以及如何用Redis List命令模拟栈、队列和双端队列。读完这篇，你会理解Redis List那些看似简单的命令，背后隐藏的数据结构智慧。

一、listNode：链表的最小单元

1.1 结构体定义

Redis的链表节点定义在adlist.h中，非常简洁——只有三个字段：

typedefstructlistNode{structlistNode*prev;// 指向前一个节点structlistNode*next;// 指向后一个节点void*value;// 节点值（万能void*指针）}listNode;

三个字段，各司其职：

• prev：前驱指针，让你能往回走
• next：后继指针，让你能往前走
• value：万能void*，指向实际数据。这意味着一个链表里可以同时存字符串、整数、甚至你的自定义结构体——虽然实际业务中不会这么干，但这个设计给底层实现带来了极大的灵活性

1.2 内存布局ASCII图

单个listNode在内存中长这样（64位系统）：

listNode +-------------+ | prev (8B) | ────指向左边那个listNode +-------------+ | next (8B) | ────指向右边那个listNode +-------------+ | value (8B) | ────指向实际数据（字符串/整数/复杂对象） +-------------+ 共计 24 字节/节点

三个节点的链表连起来是这样的：

listNode #1 listNode #2 listNode #3 +-------------+ +-------------+ +-------------+ | prev: NULL | | prev ───────────────>| prev ───────+ +-------------+ +-------------+ +-------------+ | next ───────┼──────>| next ────────┼──────>| next: NULL | +-------------+ <────+-------------+ <────+-------------+ | value ───┐ | | value ───┐ | | value ───┐ | +----------|--+ +----------|--+ +----------|--+ | | | v v v "apple" "banana" "cherry"

二、list：链表的"大管家"

listNode只是节点本身，真正管理整个链表的是list结构体。它承担了元数据存储和多态函数指针的角色。

2.1 结构体定义

typedefstructlist{listNode*head;// 头节点指针listNode*tail;// 尾节点指针void*(*dup)(void*ptr);// 节点值复制函数void(*free)(void*ptr);// 节点值释放函数int(*match)(void*ptr,void*key);// 节点值匹配函数unsignedlonglen;// 链表长度}list;

六字段详解：

2.2 三个函数指针的设计智慧

这三个函数指针实现了多态——同一个list结构，不同类型的值有不同行为：

// 假设我们定义一个存字符串的listlist*strList=listCreate();strList->dup=strDup;// 复制时用strdupstrList->free=strFree;// 释放时用freestrList->match=strMatch;// 匹配时用strcmp// 另一个存自定义对象的listlist*objList=listCreate();objList->dup=myObjDup;// 用自己的复制逻辑objList->free=myObjFree;// 用自己的释放逻辑objList->match=myObjMatch;// 用自己的比较逻辑

这种设计的好处是：链表操作代码（listAddNodeHead/listDelNode等）完全不用关心值类型，只管操作指针就行。要知道这在纯C里实现多态，全靠函数指针——Redis作者把这招玩得炉火纯青。

2.3 list + listNode的完整内存图

list 结构体 +--------------------+ | head ──────────────┼────────────────┐ +--------------------+ | | tail ──────────────┼──────────┐ | +--------------------+ | | | dup ──> strDup | | | +--------------------+ | | | free ──> strFree | | | +--------------------+ | | | match ──> strMatch | | | +--------------------+ | | | len: 3 | | | +--------------------+ | | v v +-----------+ +-----------+ +-----------+ | prev:NULL | | prev ─────┼──┐ | prev ─────┼──┐ | next ─────┼──┐ | next ─────┼──┼──>| next:NULL | | | value ───┐| | | value ───┐| | | value ───┐| | +----------|+ | +----------|+ | +----------|+ | | | | | | | v | v | v | "A"<───┘ "B"<──┘ "C"<──┘ ^ ^ | | +──────────────────────────────────────+ (head) (tail)

三、Redis链表的四大特性

3.1 双端（Double-Ended）

每个listNode同时持有prev和next指针。这意味着你可以从任意节点出发，向前或向后遍历。RPUSH之后紧接着LPOP，效率都是O(1)。

127.0.0.1:6379>RPUSH tasks"task1""task2""task3"# 从右边入队(integer)3127.0.0.1:6379>LPOP tasks# 从左边出队——O(1)!"task1"127.0.0.1:6379>RPOP tasks# 从右边出队——也是O(1)!"task3"

3.2 无环（Acyclic）

头节点的prev是NULL，尾节点的next是NULL。这和Linux内核的环形链表不同——Redis选择无环设计的理由是简单直接，遍历时不需要检查"是不是回到开头了"。

head ──────────────────────────> tail NULL ←] [→] [←] [→] [←] [→ NULL

3.3 带头尾指针

list结构体直接持有head和tail指针，所以：

• LLEN命令是O(1)——直接读list->len
• LPOP命令是O(1)——直接操作list->head
• RPOP命令是O(1)——直接操作list->tail

3.4 带长度计数

list->len字段让获取链表长度成为O(1)操作。不需要遍历，不需要计数，直接return。这个设计贯穿Redis的所有数据结构——能用字段记的就绝对不用遍历算。

四、链表迭代器：访问每一个节点

4.1 listIter结构体

typedefstructlistIter{listNode*next;// 下一个节点intdirection;// 迭代方向}listIter;

direction有两个可选值：

• AL_START_HEAD：从头到尾（正向迭代）
• AL_START_TAIL：从尾到头（逆向迭代）

4.2 迭代器的使用

// 正向迭代listIter*iter=listGetIterator(list,AL_START_HEAD);listNode*node;while((node=listNext(iter))!=NULL){// 处理 node->value}listReleaseIterator(iter);// 逆向迭代listIter*riter=listGetIterator(list,AL_START_TAIL);listNode*node;while((node=listNext(riter))!=NULL){// 从后往前处理 node->value}listReleaseIterator(riter);

4.3 迭代方向ASCII图

正向迭代 (AL_START_HEAD): head ───> [A] ───> [B] ───> [C] ───> NULL next=^ next=NULL→结束 逆向迭代 (AL_START_TAIL): head <─── [A] <─── [B] <─── [C] <─── tail next=^

五、链表API全景图

Redis链表提供了一套完整的CRUD API，我们逐一梳理：

⚠️ 注意：listIndex支持负数索引（-1表示最后一个节点）。但它的时间复杂度是O(N)，因为链表不支持随机访问。索引为正时从头走到第index个节点，为负时从尾走到第|index|个节点。

六、链表 vs 数组 vs 跳跃表

链表虽然灵活，但不是银弹。我们把它和数组、跳跃表做个全面对比：

看完这张表你就能理解，为什么Redis 3.2之后毅然决然地用quicklist替代了纯链表。纯链表在数据量大时，那叫一个"缓存粉碎机"——每访问一个节点都是指针跳转，每跳一次都可能Cache Miss。

七、Redis 3.2+：quicklist取代纯链表

7.1 纯链表的致命弱点

链表最大的问题是内存不连续。现代CPU都有三级Cache，一次Cache Miss的代价可达几百个CPU周期。纯链表每个节点散落在堆的各处，访问100个节点可能触发100次Cache Miss——这对CPU来说简直是灾难。

7.2 quicklist的折中方案

quicklist本质上是一个用链表串起来的ziplist：

quicklist: +-----------+ +-----------+ +-----------+ | ziplist | ───> | ziplist | ───> | ziplist | | [A B C D] | <─── | [E F G H] | <─── | [I J K L] | +-----------+ +-----------+ +-----------+

• 每个ziplist节点内部是一块连续内存（Cache友好！）
• 多个quicklist节点用链表串起来（保持了插入/删除的灵活性）
• 可以通过list-max-ziplist-size配置每个ziplist最多存多少元素

这样既保留了链表的优点（头尾插入O(1)），又规避了它的缺点（内存不连续）。Redis 3.2之后，List的底层实现根据元素大小和数量自动选择ziplist、linkedlist或quicklist。

⚠️ 注意：如果你的Redis版本还在2.x或3.0，List底层还是纯链表实现。升级到3.2+后，LPUSH等命令的行为是兼容的，但底层已经悄悄换成了quicklist。可以通过DEBUG OBJECT key来确认当前的编码方式。

八、用Redis List模拟栈/队列/双端队列

Redis List的本质就是双端链表，所以天然支持栈和队列。同样的数据结构，不同的命令组合，就能玩出不同的花样。

8.1 栈（Stack）——后进先出（LIFO）

栈的特点是同一端进、同一端出：

# 压栈：从左侧推入127.0.0.1:6379>LPUSH my_stack"page1""page2""page3"(integer)3127.0.0.1:6379>LRANGE my_stack0-11)"page3"# 最后进去的排在前面2)"page2"3)"page1"# 最先进去的排在后面# 弹栈：从左侧弹出（后进先出！）127.0.0.1:6379>LPOP my_stack"page3"# 最后push的最先pop127.0.0.1:6379>LPOP my_stack"page2"127.0.0.1:6379>LPOP my_stack"page1"

LPUSH + LPOP 或 RPUSH + RPOP 都是栈。入和出在同一端就行。

8.2 队列（Queue）——先进先出（FIFO）

队列的特点是进和出在不同端：

# 入队：从右侧进入（生产者）127.0.0.1:6379>RPUSH task_queue"task1""task2""task3"(integer)3# 出队：从左侧取出（消费者）127.0.0.1:6379>LPOP task_queue"task1"# 最先进入的最先被消费127.0.0.1:6379>LPOP task_queue"task2"127.0.0.1:6379>LPOP task_queue"task3"

这是经典的生产者-消费者模式。多个消费者阻塞等待时，可以用BLPOP/BRPOP：

# 消费者1：阻塞等待，超时时间30秒127.0.0.1:6379>BLPOP task_queue30

8.3 双端队列（Deque）——两端都能进出

# 从左边进、从右边出（反过来也行）127.0.0.1:6379>LPUSH deque"left1""left2"(integer)2127.0.0.1:6379>RPUSH deque"right1""right2"(integer)4127.0.0.1:6379>LRANGE deque0-11)"left2"2)"left1"3)"right1"4)"right2"# 既可以LPOP也可以RPOP127.0.0.1:6379>LPOP deque"left2"127.0.0.1:6379>RPOP deque"right2"

8.4 阻塞队列：消息队列的基石

# 生产者向队列右端推送任务127.0.0.1:6379>RPUSH notifications"new_order:12345"# 消费者A：从队列左端阻塞获取（等待5秒）# 终端A执行127.0.0.1:6379>BLPOP notifications51)"notifications"2)"new_order:12345"(2.34s)# 等了2.34秒拿到数据# 消费者B：如果队列已空，会等满5秒然后返回nil127.0.0.1:6379>BLPOP notifications5(nil)(5.04s)

这种模式让Redis成为了轻量级消息队列的首选——简单、可靠、毫秒级延迟。

九、LPUSH/RPUSH/LPOP/RPOP/LRANGE的链表视角

当你执行这些命令时，它们直接映射到底层list的API：

十、总结

从listNode的三字段简洁设计，到list结构体用函数指针实现多态，再到四大特性让链表操作几乎全O(1)，Redis的链表实现处处体现着"刚刚好"的设计哲学——不做过度抽象，但把每个细节都打磨到极致。

然而，纯链表的内存不连续性最终导致了quicklist的诞生。这个演进过程告诉我们：没有任何数据结构是银弹，甚至Redis最经典的数据结构也在随着硬件特性（CPU Cache）和业务需求不断进化。

下一篇，我们将进入Redis的核心中的核心——哈希表。看看dictht和dict是怎么撑起Redis的键值对世界的。

上一篇【第11篇】SDS实战——Redis字符串操作背后的黑科技
下一篇【第13篇】哈希表——Redis字典的核心数据结构