链表与变体：单链、双链与哨兵
学习状态：
一句话定义
链表（Linked List）用「节点 + 指针」把元素串成链式存储：每个节点存数据与指向后继（双向链表还指向前驱）的引用，以放弃随机访问为代价，换取在已知位置上的 O(1) 插入与删除。
为什么重要
链表是与数组互补的另一极：所有「已知节点位置、要求 O(1) 摘除/嫁接」的场景（LRU 淘汰、任务队列、内存空闲链、邻接表）都靠它。同时它是指针操作的试金石——反转、找环、合并这些操作训练出的不变量思维，会直接迁移到树与图的操作里。
前置知识
kp-006（作为对照面）；指针/引用的基本语义。
核心概念
- 单链表：节点 = {值, next}；只能单向前进；找前驱需从头 O(n)。
- 双向链表：节点 = {prev, 值, next}；已知节点可 O(1) 自我摘除，是 LRU 的标配。
- 循环链表：尾指回头，适合环形调度（约瑟夫问题）。
- 哨兵节点（Sentinel/Dummy）：增设永不删除的头（尾）占位节点，统一「空表/头插/头删」的边界代码，消灭大部分特判。
- 快慢指针：同速/倍速双指针一次遍历完成找中点、判环（Floyd 判圈）等任务。
直观类比
数组是连排座位，链表是寻宝游戏：每张卡片（节点）写着下一张卡片藏在哪。找到位置后插入新卡片只需改两张卡片的「下一站」，但想直接「跳到第 1000 张」只能一张张翻。
原理与机制
反转单链表的三指针迭代法（核心训练题）：
prev ← null; cur ← head
当 cur ≠ null:
nxt ← cur.next // 先保住后继
cur.next ← prev // 反转当前指针
prev ← cur; cur ← nxt
返回 prev // prev 即新表头
不变量：prev 已反转完成；cur 待反转；nxt 未触碰。
时间 Θ(n)，空间 O(1)。操作代价表：
| 操作 | 单链表 | 双向链表 |
|---|---|---|
| 头插/头删 | O(1) | O(1) |
| 尾插（无尾指针） | O(n) | O(n)，有尾指针 O(1) |
| 已知节点摘除 | O(n)（需前驱） | O(1) |
| 按下标访问 | O(n) | O(n) |
图示
单链表: head ─▶ [A|•]──▶ [B|•]──▶ [C|✕]
双向链表: ⇄ [A] ⇄ [B] ⇄ [C] ⇄（哨兵 D 双向环）
删除已知节点 X（双向）： X.prev.next ← X.next ; X.next.prev ← X.prev实例或案例
- LRU 缓存：哈希表（kp-009）键→双向链表节点定位，链表按访问时间排序，命中/淘汰均 O(1)——两大结构互补的经典组合。
- 操作系统的空闲内存块链、内存池的 free list 都是链表。
- 多项式加法：按指数降序的链表合并，是「归并」思想的最小练习。
- 约瑟夫问题：循环链表模拟报数出圈，或直接用数学递推 O(n)。
常见误区
- 头插法建表后忘记新表头，或遍历中丢失
next导致断链（必须先存后继再改指针）。 - 认为「链表省内存」：每节点多一个指针（8 字节级）外加内存碎片与缓存劣势，小元素时总占用反而更高。
- 用链表做按下标随机访问：O(n) 的访问让整体复杂度崩坏，该场景必须用数组。
- 实现栈/队列时链表版忽视哨兵，边界特判写漏导致空表崩溃。
自测题
- 用快慢指针描述「找中间节点」的做法，并说明奇偶长度时的结果。
答案要点：慢走 1 快走 2，快到尾时慢在中点；偶数长度时慢落在后一半的第一个（约定可自定，说明清楚即可）。
- 只给你指向单链表中间某节点的指针 p，能否 O(1) 删除该节点（不含表尾）？
答案要点：把后继的值复制进 p，再摘除后继节点；表尾节点不可行（前驱无法 O(1) 获得）。
- 为什么 LRU 必须用双向链表而不是单链表？
答案要点：需在 O(1) 内删除任意已知节点（含尾部淘汰），单链表摘除需前驱，只能 O(n)。
与其他知识点的关系
kp-008 的栈队列可用链表实现；kp-009 哈希冲突的链地址法本质是链表；kp-016 图的邻接表同样以链式存储为骨架；树（kp-011）可以看作「每个节点可以有两个 next 的链表」。
延伸阅读
《数据结构与算法分析：C 语言描述》第 3 章；LeetCode 206（反转链表）、141（环形链表）题解对照本节三指针不变量。