链表是一种数据结构,用一组通过引用相互连接的节点来表示序列。每个节点包含一个值或对某个值的引用,以及一个或多个指向其他节点的链接。与数组(数据结构)不同,链表不要求相邻元素占据连续的内存位置:元素的顺序由链接决定,而不是由物理存储位置决定。
链表的重要之处在于,它将数据的逻辑组织方式与存储布局分离开来。一旦确定了相关节点,许多插入、删除和重排操作就只需修改固定数量的链接。这种灵活性也有代价:查找某个位置通常需要遍历,而链接本身会占用内存,并且往往会降低访问的局部性。因此,链表体现了计算机科学中的一个核心区别:定位信息的成本与修改信息的成本并不相同。
链表广泛用于语言运行时、操作系统内核、哈希表、缓存和符号计算。其实际表现取决于链表的变体、内存管理模型、接口以及硬件。理论上耗时为常数的更新操作,在应用中未必很快;而序列这一抽象也不一定要用链表来实现。
节点、链接与表示不变式
最简单的链表是一条单向链接的链。每个节点包含数据和一个 next 链接。一个外部引用指向第一个节点,通常称为头指针;沿着 next 反复访问,即可依次到达后续节点。在以空值结尾的表示方式中,最后一个节点的链接存放一个特殊的空值,空表的头指针也为空。例如,逻辑序列 可以表示为 head → [a | next] → [b | next] → [c | null]。
链接通常是一个指针,但不一定是机器地址。它也可以是数组索引、内存区域内的偏移量,或由运行时管理的对象引用。当数据需要在重定位后仍然有效,或需要存储在进程地址空间之外时,这一区别就很重要。基于索引的链表可以将所有节点存放在同一个数组中,同时仍按任意逻辑顺序将它们链接起来。这种表示仍然属于链式结构,因为后继节点是通过已存储的链接来确定的,而不是根据元素在序列中的位置计算得出的。
正确性依赖于表示不变式,即每当该结构可供操作访问时都必须成立的条件。对于常规的、有限且以空值结尾的单链表,从头指针开始沿链接访问,必须能够到达空值,且不能重复访问任何节点。途中遇到的每个链接都必须指向有效节点或为空。如果链表保存了尾指针,它就必须指向最后一个可达节点,且该节点的后继为空。如果链表保存了长度,该数值就必须等于可达节点的数量。额外的维护信息可以加快查询,但每次修改都必须保持这些信息正确。
哨兵节点是一种不代表普通元素的结构性节点。在第一个元素之前设置一个虚拟节点,可以使表头插入和删除操作采用与中间位置操作基本相同的逻辑。在循环结构中,哨兵可以同时标记起点和终点;空的循环链表可以仅由一个链接到自身的哨兵节点组成。哨兵能简化边界情况的处理,但不能将其与承载数据的节点混淆。
节点的身份与元素的值是两个不同的概念。两个节点可以包含相等的值,却处于不同的位置;删除其中一个,并不意味着也要删除另一个。反过来,节点的地址可以保持不变,而其存储的数据发生变化。暴露节点句柄的接口会明确体现这一区别。只暴露值的接口可以将其隐藏起来,但在实现中,仍然必须将每个节点的身份和生命周期与其内部所存数据的含义区分开来。
遍历、插入、删除与拼接
遍历从一个已知节点开始,反复沿后继链接向前访问。按值查找时,将每个访问到的节点所存储的数据与目标值进行比较;按位置访问元素时,则从起点开始对经过的链接计数。这两种操作通常都不能直接跳到任意位置。遍历时也可以保留前一个节点,这很有用,因为单链表不提供直接向后访问的路径。
在已知节点 p 之后插入节点,需要一个新节点 q,以及以下两个概念上的赋值操作:
q.next = p.next
p.next = q
赋值顺序很重要:在将原后继节点的引用存入 q 之前,必须保证该引用仍然可用。在表头插入的过程与此类似,只是用头引用代替 p.next。如果维护了有效的尾引用,尾部追加就能在常数时间内完成;否则,通常必须遍历单链表才能找到最后一个节点。内存分配和节点数据的构造所产生的开销,与这些链接修改的开销是分开的。
删除 p 之后的节点时,需要修改前驱节点的链接,使其绕过被删除的节点:
q = p.next
p.next = q.next
随后,实现代码必须处理被移除节点的生命周期:可以销毁并释放该节点,将其归还节点池,或将其所有权转交给调用方。如果 q 原本是尾节点,保存的尾引用就必须改为 p。移除首节点时,则改为更新头引用。在单链表中,仅持有目标节点通常不足以按常规方式在常数时间内将其移除:还需要知道它的前驱节点,或持有指向该节点的链接的引用。
一种经常被提及的捷径是,将后继节点的值复制到目标节点中,然后移除后继节点。这并不能实现一般意义上的目标节点删除。它不适用于最后一个节点,会改变节点身份与值之间的对应关系,可能需要执行开销很大或不允许执行的数据赋值操作,也可能违背外部引用所依赖的预期。只有在特定的限制条件下,这种做法才有用。
拼接通过重新连接边界处的链接来转移已有节点或节点链,而不是复制其中的元素。只要具备合适的边界引用,就能通过固定次数的指针修改,将一条节点链从一个链表中摘下,再接入另一个链表。不过,接口还可能需要确定这条节点链的末端、统计其元素数量、更新所有权元数据,或检查分配器是否兼容。这些额外要求可能使某次具体的拼接操作具有线性时间复杂度,即使其中的链接操作本身只需常数时间。
双向链表同时保存前驱和后继链接,因此更容易按常规方式移除一个已知节点。这些额外信息减少了查找相邻节点的需要,但每次插入或移除时,都必须一致地更新两个方向的链接。
复杂度与硬件性能
对链表操作的标准分析采用这样一种模型:读取或写入一个链接所需的时间为常数。在这一模型下,遍历 个节点或在其中进行一次未命中的查找,都需要 时间。在单链表中,从头节点出发,访问从零开始编号的位置 处的元素,需要 时间。对于可直接访问两端的双链表,可以从较近的一端开始遍历,因此访问时间为 。
通常的复杂度界限会区分定位某个位置与在该位置执行更新的成本:
| 操作 | 典型链表开销 | 重要条件 |
|---|---|---|
| 读取第一个元素 | 保存了头节点引用 | |
| 查找某个值 | 没有辅助查找索引 | |
| 在头部插入 | 节点创建的成本单独计算 | |
| 在单链表尾部追加 | 维护了尾节点引用 | |
| 删除单链表的最后一个元素 | 必须找到其前驱节点 | |
| 删除已知的双链表节点 | 该节点属于此链表 | |
| 获取长度 | 或 | 取决于是否维护长度等辅助信息 |
这些是时间复杂度的界限,而非对实际耗时的直接测量。连续存储的数组,其扫描速度往往远快于包含相同值的链表。连续的数组访问具有空间局部性,能够受益于预取和向量化执行。链表遍历则需要执行具有依赖关系的加载操作:只有取回当前节点之后,才可能知道下一个节点的地址。因此,CPU 缓存未命中的开销可能成为执行时间的主要部分。
普通链表的空间复杂度为 ,但常数因子也很重要。在指针占用八字节的机器上,一个存储八字节值的单链表节点,在不计内存分配器开销和额外对齐影响的情况下,需要十六字节。在同样的简单内存布局假设下,双链表节点至少需要二十四字节。这些数字仅用于说明,并非普遍适用:指针压缩、带标签的表示方式、有效载荷的对齐要求以及运行时头部信息都可能改变这些数值。
动态数组支持常数时间的按索引访问,以及摊销常数时间的尾部追加,不过单次扩容操作可能需要搬移大量元素。链表在局部插入时无需移动其后的所有元素,但定位插入位置的成本可能抵消这一优势。反复遍历的代价尤其高:如果一个循环分别从头查找链表中位置 处的元素,总工作量可能达到 ,而一次连续遍历只需要 时间。
因此,有意义的性能比较需要考虑元素大小、内存分配策略、遍历频率、修改位置以及句柄稳定性。笼统地声称链表“更适合插入”并不完整,还必须说明如何确定插入位置,以及与之比较的数据表示方式需要移动哪些内容。
主要变体及其权衡
单向链表将每个节点用于连接的字段数量降至最低,并天然支持向前遍历。对于集中在表头进行的操作,它尤其方便。例如,栈(数据类型)可以在表头压入和弹出节点,无须维护尾指针。队列(数据类型)则可以从表头删除节点,在表尾插入节点。当队列从仅有一个元素变为空队列时,必须同时正确重置头、尾两个引用,否则尾引用可能仍指向已删除的节点。
双向链表为每个节点增加一个 prev 链接。如果节点 位于节点 之前,为保持一致性,通常必须同时满足 和 。这样一来,双向遍历以及删除已知节点的操作都变得直接。其缺点是需要额外的存储空间,并且要更新更多链接。损坏的前向链接还可能与仍然有效的后向链接不一致,导致同一结构在不同遍历方向下表现不同。
循环链表将最后一个节点直接或通过哨兵节点连接回第一个节点。由于没有空的后继引用来标记末尾,遍历必须在回到指定起点时停止。循环链表适合循环处理,也能通过少量链接修改完成某些拼接操作。但如果终止条件仍假定链以空引用结尾,就很容易意外陷入无限遍历。这里的循环是有意设计的,本身并不意味着结构已损坏。
侵入式链表将链接字段嵌入被组织的对象内部,而不是为每个对象单独分配一个包装节点。这样可以省去包装节点的分配,并能通过对象引用在常数时间内将其移除。如果一个对象为每个所属链表都设置了独立的链接字段,它就可以同时属于多个链表。单个链接字段通常无法同时表示对象在多个独立链表中的成员关系。此外,外围系统还必须确保:只要任何链表仍将该对象作为成员引用,对象就必须保持存活。
展开链表在每个相互链接的块中存储多个元素。它减少了平均每个元素所需的链接数量和内存分配次数,并改善了块内的局部性,但在块内插入元素时,可能需要移动多个值。块的占用规则和分裂策略决定了其实际表现。其他表示方式会将链接编码为偏移量,或将多个逻辑上的链接信息合并到一个字段中。例如,异或链表将前驱地址和后继地址一起编码,但会使遍历、调试、垃圾回收以及与指针模型的兼容变得更加复杂。
跳表增加了多层前向链接,以支持查找。在适当假设下,其标准随机化形式的查找、插入和删除操作均具有对数级的期望时间复杂度。它不只是普通顺序遍历的一种紧凑变体:新增链接构成了辅助导航结构。与树和哈希表一样,更快的定位依赖于维护基本链表顺序之外的信息。
链式序列上的算法
许多常见算法都必须作出调整,以适应链表只能沿后继引用访问元素、而不能通过索引在常数时间内定位元素的特点。顺序过滤、映射和累积操作很适合链表:每个节点只访问一次,结果可以收集到其他位置,也可以并入累加器。那些依赖反复跳转到任意索引位置来提高效率的算法,通常需要采用不同的策略或数据表示方式。
单链表的原地反转是谨慎操作链接的一个典型例子。算法维护三个引用,分别指向已处理的前缀、当前节点和尚未处理的后缀:
previous = null
current = head
while current != null:
following = current.next
current.next = previous
previous = current
current = following
head = previous
一个有用的循环不变量是:previous 指向已经反转的已处理前缀的头节点,而 current 指向尚未处理的后缀的头节点。在覆盖 current.next 之前先保存 following,可以避免丢失通往该后缀的引用。该算法的时间复杂度为 ,辅助空间复杂度为 。如果还保存了尾节点引用,也必须相应更新,通常将其指向原来的头节点。
归并排序非常适合链表,因为两个有序链可以通过反复选取各自的头节点来合并。这一过程不需要随机访问,而且可以通过重新连接节点而非复制节点来完成。将链表分成长度大致相等的两半,再递归归并,可得递推关系
因此时间复杂度为 。自顶向下的实现通常需要 的调用栈空间。自底向上的实现则逐步归并长度不断增加的有序段,可以避免递归调用。当键比较结果相等时,优先选取左侧有序段中的元素,即可保持排序的稳定性。
使用两个以不同速度移动的引用,可以实现若干实用算法。要寻找中间位置,可以让一个引用每步前进一个节点,另一个每步前进两个节点;当较快的引用到达末尾时,较慢的引用就位于中间附近。这项技巧也可以用于在排序时拆分链表。当链表长度为偶数时,具体选中哪个中间节点取决于边界处理方式。
Floyd 判圈算法利用同样的速度差,以 的额外空间检测意外形成的环。如果存在可达的环,两个引用最终会在环内相遇。按照标准流程,将其中一个引用重置到头节点,再让两个引用每次各前进一步,就能找到环的入口。如果非环前缀的长度为 ,环的长度为 ,则检测所需的时间为 。另一种方法是使用已访问节点集合,以额外的内存开销为代价,显式记录此前访问过的节点身份。
仅仅有序,并不足以让普通链表上的二分查找变得高效。链表无法在常数时间内取得中点。即使通过反复定位中点来减少比较次数,仍然需要大量遍历;仅有值的有序性,并不能带来数组在二分查找中所具有的对数级访问优势。
所有权、内存管理与语言接口
链表的逻辑操作与节点所有权密切相关。在 C编程语言中,典型实现会显式分配节点,并在移除节点后释放其内存。如果丢失了指向某条已分配链的唯一指针,就可能造成内存泄漏。继续访问已释放的节点会导致悬空指针错误,而对同一块已分配内存释放两次则可能破坏内存分配器的状态。因此,仅有正确的链接修改顺序还不够,内存分配、生命周期和清理也必须正确。
垃圾回收改变的是内存回收机制,而非逻辑结构。被移除的节点只有在从任何活跃根都无法到达时,才可被回收,而不一定是在它离开某个特定链表时。外部引用可能使它继续存活。反过来,如果一个活跃的头引用意外保留了已经不再需要的链,那么所有可达节点都可能因此无法回收。追踪可达性的回收器可以回收不可达的环;单纯的引用计数则无法回收成员相互引用、使彼此引用计数始终非零的环。
在函数式编程中,不可变单链表通常由一个空表值,以及一个包含头部值和尾部链表的构造器来构建。在表头添加元素时,只需创建一个新节点,使其尾部指向已有序列。原有序列仍然可用,因此这种结构是一种共享尾部的可持久化数据结构。如果 xs 表示 ,那么构造 无须复制 和 。不过,在不可变单链表末尾追加元素通常需要复制左侧的链,因为不能修改它的最后一个链接。
共享会影响接口所提供的保证。如果一个可变节点通过多个引用暴露给外部,那么通过其中一个引用进行的更新,也会通过其他引用显现出来,这就是混叠的一种情形。不可变链表避免了这种结构上的相互干扰,但其存储的数据本身仍可能引用可变对象。独占所有权系统则采用另一种方法,限制同时进行的可变访问。双向链式结构的要求尤其严格,因为其双向引用必须与生命周期和所有权规则相协调。
标准库中的名称反映的是接口选择,而不是某种统一的链表抽象。C++ 提供 std::forward_list 用于单链式存储,提供 std::list 用于双链式存储。Java 的 LinkedList 是双向链表,而 Python 内置的 list 则是可调整大小的数组。因此,仅凭“list”这个名称,无法判断其内存布局或操作成本。不同实现还可能在是否存储长度、迭代器行为以及内存分配策略等方面存在差异。
证明方法会明确给出所有权假设。分离逻辑于 21 世纪初提出,为可变内存中互不重叠的区域提供断言,并为链接形成的链提供递归描述。在形式验证中,这些描述有助于证明某个例程能够保持结构形态、不丢失节点,并且只修改它所拥有的内存。无环性、引用有效性和互不重叠性,往往与最终的值序列同样重要。
并发访问与安全回收
当多个线程可以访问同一个可变链表时,指针更新的先后顺序就成为正确性问题的一部分。在单线程程序中有效的插入操作,可能会暴露尚未完成初始化的节点,或丢失另一个线程的更新。因此,并发计算既需要协调逻辑变更的规则,也需要规定何时可以回收已移除节点的规则。
一种直接的解决方案是使用互斥锁,保护每次操作或整个链表。锁可以同时保护链接、大小元数据以及端点引用。更细粒度的加锁允许更多操作并行进行,但也带来了额外要求,包括采用一致的锁获取顺序,以避免死锁。如果另一个线程可能在赋值前移除节点,或在遍历过程中回收节点,那么仅保护修改链接的赋值语句可能还不够。
非阻塞算法通常使用比较并交换:这是一种原子操作,只有当某个位置仍包含预期值时,才会更新该位置。链式栈可以先准备一个新节点,使其指向所观察到的栈顶,然后以原子方式尝试用新节点替换栈顶。如果另一个线程已改变栈顶,操作就会重新读取栈顶并重试。要正确地发布节点,还需要遵守内存顺序规则,确保看到新栈顶的线程也能看到该节点已初始化的内容。
一个主要难点是 ABA 问题。一个线程观察到地址 ,另一个线程移除了该地址对应的节点,而后续活动又使同一地址再次出现。此时,即使底层状态的变化过程已经不同,比较仍可能成功。这是否会导致错误取决于具体算法,但仅凭地址相等,并不能证明对象的身份始终未变。版本标记可以帮助区分不同状态,不过也需要考虑表示方式和计数回绕问题。
内存回收是另一个独立问题。将节点从链表中断开,并不能证明其他线程不再持有指向它的指针。危险指针允许线程公开自己持有的引用,内存回收时必须将这些引用纳入考虑。基于纪元的技术会推迟回收,直到可能观察到旧状态的读取线程都不再处于活动状态。在 Linux 中广泛使用的读-复制-更新机制支持这样一种模式:读取线程遍历可访问的数据,而更新线程则推迟内存回收,直到适当的宽限期结束。每种方法都对读取线程和更新线程规定了各自必须遵守的规则。
进展保证也需要使用精确的术语。无锁算法保证,即使个别参与线程出现延迟,系统整体仍能取得进展;无等待算法则保证,在其模型下,每个操作都能在有界步数内完成。仅仅使用原子指针,并不能确立其中任何一种性质。内存分配、回收、重试循环和辅助锁,都可能影响完整实现的进展保证,而不能只考察修改头指针的代码。
应用与表示方式的选择
当应用程序已经持有需要移动或删除的对象的引用时,链表最能发挥作用。在这种情况下,无须额外查找即可在常数时间内局部调整链接,这一点很有价值。如果操作以顺序扫描或按索引查找为主,数组或其他紧凑的表示方式往往能在访问开销和内存性能之间取得更好的平衡。
一种常见的应用是将哈希表与双向链表结合起来,实现最近最少使用(LRU)缓存。哈希表将键映射到节点,从而避免线性查找。访问某个条目时,将其节点移到最近使用端;淘汰条目时,则从最久未使用端移除节点。如果哈希表操作的期望时间为常数,那么查找和更新使用顺序的期望开销也可以是常数时间。链表记录顺序,哈希表则提供直接定位能力。单独使用其中任何一种结构,都难以同样自然地兼顾这两种能力。
哈希表的冲突处理是另一种用途。采用分离链接法时,每个桶保存一组条目,通常用链表表示。插入和删除可以很简单,而且条目不会仅仅因为另一个条目被删除就需要移动。不过,链式节点会增加内存分配开销,并带来局部性方面的代价。分离链接法并不等同于链表:桶内的条目集合可以使用数组或其他结构,而采用开放寻址法的哈希表则完全不需要为每个桶设置链。
在操作系统中,侵入式链表用于组织那些由其他机制管理其身份和生命周期的对象,包括工作项和资源记录。Linux 内核的链表机制包含通过内嵌链接构成的循环双向链表结构。这类设计允许一个对象通过不同的链接字段,同时参与多种组织关系。但它们也要求对初始化、成员归属、加锁和对象销毁实行严格管理。
图的邻接表涉及另一个重要的术语区别。邻接表记录每个顶点的邻居,但这些记录并不一定要用链表保存。数组、动态数组和压缩布局都是常见的替代方案。在稀疏图处理中,连续存储邻居可以显著提升遍历性能。同样,队列、栈或有序集合是抽象接口,并不意味着必须采用链式分配。
链式空闲表可以跟踪内存池中的可用块,有时会在块未被使用时将链接存储在块内部。这避免了为管理信息单独分配内存,但链接一旦被覆盖,就可能破坏内存池。更紧凑的替代方案包括位图和以索引表示的空闲槽位数组。在更大的规模上,数据库或文件系统可能通过持久化标识符连接记录或存储块;当这些链接构成一条链时,遍历也会具有同样的顺序依赖性,只是其主要开销可能来自存储访问,而非内存延迟。
历史发展与影响
链表技术起源于早期的符号计算。当时,程序需要表示在执行过程中大小和形态都可能发生变化的表达式。早期的数值程序设计通常侧重于固定格式的记录和数组,而符号推理则需要在大小可变的结构中方便地进行插入、删除和共享。将分散存储的数据片段连接起来,就能表示这些不断变化的关系,而无须搬移所有相邻数据。
20 世纪 50 年代中期,艾伦·纽厄尔、克利夫·肖和赫伯特·A. 西蒙围绕信息处理语言(IPL)开展的工作,是早期表处理发展的关键。IPL 是为符号人工智能研究而开发的,相关项目包括逻辑理论机。它提供的表处理功能,使内存有限的机器也能够切实处理复杂的符号结构。历史叙述通常将这项工作与链表程序设计的兴起联系起来,不过,表的表示方式是在多个相关系统中逐步发展形成的,并非源自某个类似现代程序库中的统一定义。
约翰·麦卡锡从 20 世纪 50 年代末开始开发Lisp编程语言,赋予了链式结构一种影响尤为深远的形式。他于 1960 年发表的关于递归函数与符号表达式的论文,为一种将符号数据与程序结构紧密联系起来的语言奠定了基础。Lisp 的 cons 单元包含两个字段,传统上分别通过 car 和 cdr 访问。正规列表由一串 cons 单元构成,沿其 cdr 字段最终会到达空表。
cons 单元比普通的单链表节点更具通用性。其字段可以引用其他 cons 单元和原子,从而表示树、共享结构、点对以及有环图。因此,正规列表只是这种更广泛的表示方式中一种遵循特定规则的组织形式。这一区别有助于将表处理与递归、符号处理、解释器和自动存储管理联系起来。通过分别定义空表以及由表头和表尾构成的非空表上的操作,来递归地描述运算,至今仍是讲解结构化计算的标准方式。
随着编程语言和程序库日趋成熟,链表成为算法与数据结构研究中的经典范例。它们揭示了一些在高级接口中很容易被掩盖的区别:值与身份、存储位置与访问路径、逻辑删除与物理回收,以及渐近开销与硬件性能。链表的局部更新规则简单,也使其成为程序验证和并发研究中实用的测试案例。
随着处理器速度的提升越来越快于主存访问速度,缓存局部性也变得更加重要,链表在实际软件中的地位随之改变。这并未否定抽象的复杂度分析,而是揭示了将每次内存访问都视为具有相同开销这一假设的局限。因此,现代实现采用了节点池、侵入式链接、分块序列以及由数组支持的索引等方式。每种方式都保留了链接机制的部分优势,同时改变了存储组织、所有权规则或访问模式,而这些因素决定了其实际开销。