链 (数据结构)

提示：此条目的主题不是关联数组。

计算机科学中，链数据结构是一种由许多记录 (节点)通过引用 (链接或指针)进行链接所构成的数据结构。

在链数据结构中，链接通常被视为一种特殊的、只能被解除引用或进行比较的数据类型。因此，链数据结构通常会与数组等需要对指针进行运算的数据结构进行对比。即使节点是以单个数组的形式实现的、且引用的是数组索引，链仍与数组等数据类型有区别：只要不对其索引进行算术运算，该数据结构本质上就仍是一个链表数据结构。

有两种进行连接的方式 – 使用动态分配连接或使用数组索引链接。

链数据结构包括链表、搜索树、二叉表达式树及许多被广泛应用的数据结构。它们也是许多高效算法（如拓扑排序和并查集）的关键组成部分。

常见的链数据结构

链表

链表是一种结构的集合，其依据作为数据结构自身存储的逻辑链接来排序，而非依据在内存中的物理位置来排序。因此，其数据不必存储在相邻的内存位置上。链表的每个节点都包含一个数据域和一个地址域。地址域存储着其后继节点的地址。

链表可以是单链、双链以及多链的，并且可以是线性的或者是循环的。

基本性质

• 被称为节点的对象以线性形式进行连接。
• 始终引用链表的首个节点，该节点被称为“头节点”。

一个包含三个节点的链表，每个节点包含两个字段：一个整数值和一个指向下一个节点的链接。

一个只有单个节点的链表

伪代码

存储类型为 T 的元素的链表，其布局可能如下所示：

struct LinkedList {
    T value; // 存储数据
    LinkedList next; // 指向下一个节点（如果此节点为最后一个节点，则该值为null）
}

搜索树

搜索树是一种树形数据结构，其节点中可以存储来自某个有序集的数据值，且具有以下特性：当对树进行中序遍历时，节点按存储值的升序访问。

基本性质

• 节点存储在一个有序集合中。
• 中序遍历提供树中数据的升序读取。

优点与缺点

链表与数组

与数组相比，链表数据结构在数据组织和空间分配方面具有更大的灵活性。在数组中，必须在开始时精确指定数组的大小，这可能造成内存浪费，或形成某种任意限制，从而在后期以某种方式阻碍功能实现。链表数据结构是动态构建的，其大小永远不会超过程序所需。此外，在创建时无需预估需要分配多少空间。这一特性对于避免内存浪费至关重要。

在数组中，数组元素必须位于内存中连通（相连且顺序排列）的区域内。但在链表数据结构中，对每个节点的引用为用户提供了查找下一个节点所需的信息。与数组不同，链表数据结构的节点可以单独移动到物理内存中的不同位置，而不会影响它们之间的逻辑连接。 只要操作得当，某个进程或线程可以在数据结构的一部分中添加或删除节点，即使其他进程或线程正在处理数据结构的其他部分。

另一方面，访问链表中任何特定节点都需要沿着存储在每个节点中的引用链进行追踪。 如果该结构有 n 个节点，且每个节点最多包含 b 个链接，则会存在某些节点无法在少于 log_b n 步内到达，从而减慢访问这些节点的过程——这有时会导致相当大的性能下降，特别是在包含大量节点的结构中。 对于许多结构而言，某些节点可能需要多达 n-1 步的 最坏情况。相比之下，许多数组数据结构允许通过恒定次数的操作访问任何元素，且与条目数量无关。

总体而言，这些链表数据结构的实现是通过动态数据结构实现的。这使我们能够重复利用特定空间。通过使用这些数据结构，可以更高效地利用内存。内存会根据需求进行分配，当不再需要时，则进行释放。

普遍缺点

在节点是单独分配的情况下，链状数据结构可能会产生相当大的动态内存分配开销，并会阻碍内存分页和处理器缓存算法的运行（因为其通常具有较差的访问局部性）。因为链表数据结构并不连续，因此在部分情况下，链状数据结构可能比数组结构占用更多内存（用于链接字段）。与数组不同，数据的实例可能分散在内存的各个角落。

在数组中，第 n 个元素可以立即访问，而在链表数据结构中，则必须追踪多个指针，因此元素的访问时间取决于该元素在结构中的位置。

在诸如指针机之类的一些强制执行链表结构约束的计算理论模型中，许多问题的求解步骤会比无约束的随机存取机模型更多。

参见

• 数据结构术语列表