形式陈述

链表由节点组成，每个节点存数据与到后继的引用；双向链表还存前驱。给定节点引用时，插入和删除只改常数条链接，时间 $O(1)$；按位置查找第 $i$ 个元素通常需从表头顺序走 $O(i)$。链表表示一个有序序列，但节点在内存中不必连续。哨兵节点可统一空表和边界操作。

直觉

数组通过地址算术快速跳到任意位置，链表则把“下一个在哪里”显式存入节点，牺牲随机访问换取局部结构修改。

例子与边界

在已知节点 $x$ 后插入 $y$，只需令 $y.next=x.next$、$x.next=y$。若只给键值而未给节点位置，仍需线性搜索，所以“链表删除 $O(1)$”有前提。单链表删除当前节点通常还需前驱，除非可采用复制后继等特定技巧且语义允许。链表每节点有指针开销，局部性差，实际遍历常慢于数组；循环链表还需防止无限遍历。

推论与应用

链表用于队列、邻接表、空闲链和需要稳定节点地址的容器，也是理解指针、所有权和局部更新复杂度的基础模型。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011，Chs. 1–6。