第3章 链表

为什么从“双向链表所有权台”开始

第3章 链表的核心任务是沿listNode双向指针和list头尾、长度、复制与释放函数指针理解通用链表。命令返回值只暴露外层合同；实现解释还必须连接内存结构、写入与读取路径、事件顺序以及失败后的旧状态回收。双向链表所有权台把这些关系放进同一条可复位轨迹。

先写预测：当变更动作由“尾插”进入“删除中点”时，哪个可观察状态最先变化？再规定什么结果会推翻当前解释。交互中的分数只表达透明因果方向，不冒充真实Redis测量。

来源、版次与独立重写边界

黄健宏作者读者服务页确认正式出版新版以Redis 3.0为源码基线，列出4部分、24章及完整小节，并链接Redis 3.0中文注释源码。本课程据此映射24个正式单元、145个目录节点，另设学习地图和总复习；未取得出版正文授权，目录只界定范围，不宣称复现原书正文。

本章字段与控制流由Redis官方3.0源码：adlist.c和作者注释源码交叉核对；Redis当前持久化文档只用于辨认版本差异。中文解释、图示、交互、实验与答案均为独立教学重写，不把目录页或代码仓库许可证误报为原书许可证。

本章术语与源码合同

第3章 链表必须守住“头尾、前后指针和长度在插入删除后相互一致，节点所有权与释放回调明确”。观察同时记录双向链表所有权台一致率与边界位置分叉风险；只有结构快照、函数入口、运行结果和故障反例互相一致，才接受实现结论。

作者目录逐项深读

链表和链表节点的实现

四级证据 1/3。 listNode保存prev、next和值；list保存head、tail、len以及复制、释放和比较回调，使容器不拥有固定值类型。本节点用“链表和链表节点的实现”作观察点，执行rg 'listAddNode|listDelNode' src/adlist.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证链表和链表节点的实现时，先预测变更动作从“尾插”切到“删除中点”会改变哪个字段、偏移、文件或消息；再固定边界位置做一次对照。若故障注入没有破坏“头尾、前后指针和长度在插入删除后相互一致，节点所有权与释放回调明确”，就撤回当前解释而不是补写故事。

链表和链表节点的API

四级证据 2/3。 头尾插入、索引、删除与旋转必须同步维护head、tail、相邻指针和len，删除时按free回调处理值。本节点用“链表和链表节点的API”作观察点，执行rg 'listAddNode|listDelNode' src/adlist.c或等价源码探针，保存版本、输入、前后状态和能推翻解释的反例。

验证链表和链表节点的API时，先预测变更动作从“尾插”切到“删除中点”会改变哪个字段、偏移、文件或消息；再固定边界位置做一次对照。若故障注入没有破坏“头尾、前后指针和长度在插入删除后相互一致，节点所有权与释放回调明确”，就撤回当前解释而不是补写故事。

重点回顾

四级证据 3/3。 第3章 链表的回顾要重新证明“头尾、前后指针和长度在插入删除后相互一致，节点所有权与释放回调明确”，并用同一输入比较结构前态、变更轨迹、故障首错与恢复后态

验证重点回顾时，先预测变更动作从“尾插”切到“删除中点”会改变哪个字段、偏移、文件或消息；再固定边界位置做一次对照。若故障注入没有破坏“头尾、前后指针和长度在插入删除后相互一致，节点所有权与释放回调明确”，就撤回当前解释而不是补写故事。

最小源码与运行切片

+git clone --branch 3.0 --depth 1 https://github.com/redis/redis.git redis-3.0
+cd redis-3.0
+rg 'listAddNode|listDelNode' src/adlist.c

该切片固定Redis 3.0分支、编译器、配置、数据集和命令序列；先保存结构或函数位置，再运行隔离实例。任何持久化损坏、断线、故障转移、大键或高流量实验都必须使用临时数据并规定CPU、内存、磁盘、延迟和停止上限。

unit: rdi-03-linked-list
source_file: adlist.c
axis_a: "变更动作"
axis_b: "边界位置"
fault: "删除节点后只修一侧指针或漏调释放回调，使len与拓扑分叉"
invariant: "头尾、前后指针和长度在插入删除后相互一致，节点所有权与释放回调明确"
replay: same_version_same_input

三个必须主动触发的误区

误区 1

现象 → 大列表用 LINDEX 访问 原因 → O(N) 遍历拖慢响应 修法 → 改用 LRANGE 分段或换编码

误区 2

现象 → 以为链表是列表唯一编码 原因 → 小列表其实走 ziplist 修法 → 用 OBJECT ENCODING 确认实际编码

误区 3

现象 → 两端操作不当心空表 原因 → 空表操作返回 nil 被误判 修法 → 先 LLEN 判空再操作

小结

• 双端链表支撑列表键与发布订阅
• 无环设计让两端操作 O(1)
• 多态指针容纳任意类型
• 表长字段让计数 O(1)
• 列表键数据少时可用压缩结构

练习、答案与节点验证

术语复核与本章回顾

完成第3章 链表意味着能从adlist.c解释沿listNode双向指针和list头尾、长度、复制与释放函数指针理解通用链表，能运行章专属状态实验，能制造反例并在复位后证明旧状态没有残留。