链表

定义

链表是一种线性表，其元素并不集中存放，而是分散成一串彼此独立的结点，再通过结点里的指针把逻辑上的前后关系表达出来。线性表的这种存放方式被称为链式存储结构，与之相对的是元素紧挨着排列的顺序存储结构^[1]。

每个结点通常由两部分构成：一部分存放数据本身，称为数据域；另一部分存放相邻结点的地址，称为指针域。单链表的指针域只有一项，指向后继结点；结点的指针域为空则表明它是最后一个结点^[2]。

按指针的数目和首尾是否相接，链表可分为单向与双向两类，也可分为循环与非循环两类；是否在首个数据结点之前附设一个不存数据的头结点，又构成带头与不带头两种写法。这些维度组合起来有八种形式，实际使用最多的是不带头单向非循环链表和带头双向循环链表^[3]。

原理

链表的基本操作依赖指针改接。要在已知的相邻两个结点之间插入新结点，只需让新结点的指针指向原来的后继结点，再让前一个结点的指针改指新结点，过程不涉及其他元素的搬动；删除则把被删结点的前驱直接连到其后继上。因此在定位到有关结点的前提下，这两个操作都只要常数时间，记为 $O(1)$^[2]。

查找则是链表的薄弱环节。结点的地址是分散存放的，无法由首地址和序号直接算出第 $i$ 个元素的位置，只能沿指针逐个向下走，直到遇见目标结点，时间为 $O(n)$。这也是链表不具备随机存取特性、不能用下标直接访问的原因^[1]。

双向链表的结点额外保存一个指向前驱的指针，除后继之外还能反向找到前一个结点，代价是每个结点多占一份指针空间^[2]。单链表只能单向遍历，要取得某结点的前驱仍需从头走一遍；双向链表获取前驱只需常数时间，删除给定结点时因此比单链表更省事^[4]。

循环链表把最后一个结点重新接回首个结点，使首尾相连、没有明显的端点；好处是从任一结点出发都能遍历全表，风险是处理时若无正确的终止条件，容易陷入反复绕圈的困境^[1]。下图示意一个单向链表的指针走向。

graph LR

H[head 指针] --> A[结点1 数据|next]

A --> B[结点2 数据|next]

B --> C[结点3 数据|next]

C --> N[空]```

## 发展历程

按维基百科的记述，链表是在 1955 年至 1956 年间发展出来的，当时任职于兰德公司的艾伦·纽厄尔、克里夫·肖和司马贺在他们编写的信息处理语言(IPL)中把它作为一种原始数据类型来用[^2]。

这套语言本身是为符号处理而设计的，包含列表、动态内存分配、递归、把函数作为参数等功能，用于编写逻辑推理机、通用问题求解器和计算机象棋程序等早期人工智能程序[^5]。列表处理语言的这一支后来由 LISP 承接，链表也由此成为程序设计中长期沿用的基本结构。

此后，链表没有改变结点加指针的内核，变化主要发生在使用方式上：人们把它与散列表、跳表等结构组合，或把多个元素塞进一个结点以减少指针开销，从而在保留灵活性的同时缓解查找效率与缓存命中的问题[^2]。

## 应用

链表常用作其他结构的底层构件。栈和队列可以借链表实现；图的邻接表中，每个顶点的邻接点通常排成一个单链表；散列表用链表法处理冲突时，散列到同一位置的所有元素也串在一条链上[^2]。

缓存淘汰是链表较典型的应用场景。以最近最少使用(LRU)策略为例，用一条按访问时间排序的链表存放缓存项，缓存满时淘汰链尾结点，被访问的项则移到另一端；仅靠链表实现时，查找仍需遍历，整体时间为 $O(n)$[^6]。若在双向链表之外再叠一张散列表，把结点同时挂在哈希拉链上，查找、插入和删除都可降到 $O(1)$[^7]。

数据库与中间件中也可见到类似组合。Redis 的有序集合以跳表维护按分值的排列，同时另建散列表支持按键查找，两者合用兼顾了范围查询与按键操作[^7]。Java 的 LinkedHashMap 在散列表的基础上加挂链表，用来保留插入顺序或访问顺序，按访问顺序排列时即具备缓存淘汰的语义[^8]。

## 局限

链表无法随机存取，按位置或按值查找都要从头顺序遍历，时间为 $O(n)$，因此需要频繁按下标取值的场合不宜使用；有序链表也无法像数组那样用二分法快速缩小范围。插入删除的常数时间以已经取得相关结点指针为前提，若需先定位，实际代价仍是 $O(n)$[^2]。

指针域带来额外空间开销。当元素本身很小时，链接占用的空间可能超过数据本身，链表因此不划算；常用的补救办法是让每个结点存放多个元素，以降低指针的占比[^2]。

结点分散在内存各处，使链表的缓存表现较差。处理器一次取数会连带读入一段连续内存，数组因此易于命中所读数据，而链表的下一个结点往往落在别处，指针追逐常导致缓存未命中，遍历的实际耗时明显高于同样复杂度的数组遍历[^9]。此外，逐个结点反复申请和释放内存容易产生内存碎片，这一点也与连续分配的数组不同[^4]。

循环链表缺少天然的尾部，判空与遍历的终止条件要依赖与特定结点比较，写错就会陷入死循环；单链表则难以反向遍历，需要反向访问时应改用双向链表[^1]。

## 参见

- [[数组]] —— 采用连续内存的顺序存储结构，常与链表对照讨论访问与插删的取舍

- [[栈]] —— 可以基于链表实现的受限线性表

- [[队列]] —— 同样可用链表作为底层存储

- [[散列表]] —— 其链表法冲突处理与 LRU 缓存实现都依赖链表

- [[跳表]] —— 在链表之上增加多级索引以改善查找效率

- [[邻接表]] —— 图的一种存储方式，以单链表串联各顶点的邻接点