链表：从指针到索引

01 / NODE

链表不是一排值，而是一组关系

数组把元素放在连续位置里，通过下标寻址；链表把每个值放进节点，再用指针描述下一个或上一个节点。Head 和 Tail 是进入结构的入口，不是普通节点的别名。

单向链表

每个节点只保存 Next；向前简单，反向移动需要重新寻找。

双向链表

同时保存 Prev 与 Next；删除已知节点方便，但必须维护双向一致。

数组

按下标读取是 O(1)；中间插删通常需要搬动后续元素。

Head                                                     Tail
  │                                                        │
  ▼                                                        ▼
[ nil | A | B ] ⇄ [ A | B | C ] ⇄ [ B | C | nil ]

02 / INVARIANTS

先定义一直不能坏的关系

空链表：Head == nil 且 Tail == nil。
非空双向链表：Head.Prev == nil，Tail.Next == nil。
如果 A.Next == B，那么 B.Prev == A。
从 Head 连续沿 Next 前进，最终应抵达 Tail，并覆盖全部仍在链内的节点。

修改过程可以短暂经过不完整的中间状态，但这些状态不能被其他执行单元看见；操作结束时必须恢复全部不变量。

03 / REMOVE

四种删除可以收敛成两个方向

删除唯一节点、头、尾和中间节点看起来是四个 case，本质上都在回答两个问题：左边是否存在，右边是否存在。不存在的一侧由链表入口接管。

if node.Prev != nil {
    node.Prev.Next = node.Next
} else {
    list.Head = node.Next
}

if node.Next != nil {
    node.Next.Prev = node.Prev
} else {
    list.Tail = node.Prev
}

node.Prev = nil
node.Next = nil

唯一节点同时满足 Prev == nil 和 Next == nil，因此头尾都会变成 nil。这时不能再解引用新的 Head 或 Tail。

04 / COST

`O(1)` 删除有一个前提

操作	普通链表	关键前提
按下标读取	`O(n)`	必须从入口逐个前进
按 key 查找	`O(n)`	链表本身没有 key 索引
已知节点后插入	`O(1)`	已经持有目标节点指针
双向链表删除已知节点	`O(1)`	已经定位节点，且能访问左右邻居
尾部追加	`O(1)`	保存了 `Tail`

LRU 用 map 把“按 key 找节点”降到平均 O(1)，再由双向链表把顺序更新和淘汰降到 O(1)。两种结构各自承担一部分语义。

05 / CIRCULAR

环形链表改变的是终止条件

环形链表让尾节点重新指向头节点。它适合轮转调度、循环缓冲区附近的模型，以及需要不断遍历参与者的场景。

Head
  │
  ▼
  A ──▶ B ──▶ C
  ▲           │
  └───────────┘

普通链表以遇到 nil 结束；环形链表没有这个出口，必须在“回到起点”、达到明确计数或满足其他业务条件时停止。忘记改变终止条件，就会无限循环。

06 / SKIP LIST

跳表给有序链表增加稀疏索引

普通有序链表寻找目标仍要逐个前进。跳表让一部分节点出现在更高层：高层负责跨过大片区间，接近目标后再下沉到底层确认。

L2  H ─────────▶ 30 ─────────▶ 60
L1  H ───▶ 20 ───────▶ 40 ───▶ 60
L0  H ▶ 10 ▶ 20 ▶ 30 ▶ 40 ▶ 50 ▶ 60

搜索只做两种动作：下一个值不超过目标时向右；会越过目标时向下。随机层高使搜索、插入和删除具有期望 O(log n)，但最坏情况仍可能退化为 O(n)。

本页只建立搜索模型。随机层高、完整插入删除、并发跳表和工程参数选择不在当前范围。

07 / OWNERSHIP

并发不一定要进入链表内部

多个调用方 ──▶ command queue ──▶ 单一 owner task
                                      │
                                      ▼
                                Map + 普通链表

让一个 owner 独占链表，其他执行单元通过 queue 提交操作，可以把业务状态串行化。queue 或 channel 内部仍有同步，但链表不需要自己解决并发修改协议。

无锁链表属于另一层问题：它用 CAS、重试和内存回收协议代替互斥锁。ABA、逻辑删除、节点回收和内存顺序都需要单独建模，本页不展开。

08 / COUNTEREXAMPLES

按结构覆盖边界

结构	要确认的事实	最小 case
空链表	头尾同时为 `nil`	初始化后不做操作
唯一节点	删除后不能解引用新头尾	`A`
头 / 尾	入口与相邻反向指针同步更新	`A ⇄ B`
中间节点	左右邻居重新互相指向	`A ⇄ B ⇄ C`
重复移动	节点不能重复出现在链中	连续两次触碰同一 key
环形遍历	回到起点时终止	`A → B → C → A`
跳表搜索	右移不会越过目标，下沉能够继续	命中、缺失、最小值、最大值

当前只要求拿稳节点关系、入口、终止条件和复杂度前提。链表不是为了背代码，而是为了能在每次指针改写后说明：谁仍在结构里，入口在哪里，下一步能走到谁。