链表定义

在计算机科学中，链表（linked list）是一种线性数据集合，其元素的顺序并非由它们在内存中的物理位置决定。相反，每个元素都指向下一个元素。它是一种包含节点集合的数据结构，代表一个序列。在其最基本的形式中，每个节点都包含数据和一个指向序列中下一个节点的引用（或链接）。在遍历过程中，这种结构能够高效地在序列的任何位置插入或删除元素。更复杂的变体将添加更多链接，从而能够更有效地在任意位置插入和删除节点。链表的一个缺点是访问时间是线性的（这使得流水线式访问变得困难）。无法实现更快的访问，例如随机访问。与链表相比，数组具有出色的缓存局部性。

链表是最基本且广泛使用的数据结构之一。它们可以用来构建其他常见的抽象数据类型，例如列表、队列、关联数组和 S 表达式，包括堆栈。同时，直接实现这些数据结构而不以链表为基础也是很常见的。

与传统数组相比，链表的主要优势在于，无需重新分配或重新组织整个结构即可轻松插入或删除列表元素，因为数据项不需要在内存或磁盘上连续存储，而运行时重新组织数组是一个成本更高的操作。链表通过在列表遍历过程中将要添加或删除的链接之前的链接保留在内存中，允许以常数次操作在列表的任何位置添加和删除节点。但是，由于简单的链表不支持随机数据访问或高效索引，因此许多基本操作，例如获取列表的最后一个节点、定位包含给定数据的节点或定位应插入新节点的位置，可能需要遍历列表的大部分或全部元素。

链表历史

Allen Newell、Cliff Shaw 和 Herbert A. Simon 于 1955-1956 年在 RAND 公司和卡内基梅隆大学为他们的信息处理语言 (IPL) 创建了链表作为主要数据结构。作者们使用 IPL 创建了许多早期的人工智能程序，例如逻辑理论机、通用问题求解器和计算机国际象棋程序。他们工作的报告发表在 1956 年的 IRE Transactions on Information Theory 以及 1957 年至 1959 年的几篇会议论文中，包括 1957 年和 1958 年的 Proceedings of the Western Joint Computer Conference 以及 1959 年的数据处理（Proceedings of the First UNESCO International Conference on Information Processing）。1975 年，Newell 和 Simon 因“在人工智能、人类认知心理学和列表处理方面的基础性贡献”而获得了 ACM 图灵奖。麻省理工学院 (MIT) 的 Victor Yngve 由于自然语言处理机器翻译的困难，在他的 COMIT 编程语言中将链表用作数据结构，用于语言学计算机研究。1958 年，一篇题为“A programming language for mechanical translation”的报告出现在 Mechanical Translation 中。

Hans Peter Luhn 于 1953 年 1 月撰写了一份内部 IBM 备忘录，建议在散列表中串联使用链表，他是链表的另一早期采纳者。LISP，即列表处理器，由 John McCarthy 于 1958 年在 MIT 开发，其设计于 1960 年发表在 Communications of the ACM 上，文章题为“Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”。链表是 LISP 中的关键数据结构。在 20 世纪 60 年代初，链表及其作为其主要数据表示形式的语言的价值已经确立。1961 年 3 月，MIT 林肯实验室的 Bert Green 发表了一篇题为“Computer languages for symbol manipulation”的评论文章，发表在 IRE Transactions on Human Factors in Electronics 上，总结了链表技术的优势。1964 年 4 月，Bobrow 和 Raphael 在 Communications of the ACM 上发表了“A Comparison of List-Processing Computer Languages”。单向链表在 Technical Systems Consultants 设计的几个操作系统中用作文件格式。目录条目引用了文件的第一个扇区，并通过遍历指针找到其他扇区。TSC 在 Smoke Signal Broadcasting 在加利福尼亚创建的一个变体中也使用了双向链表。

链表类型

链表分为四种类型

单向链表

单向链表（Singly linked list）被描述为单向链表。因此，它只能沿一个方向遍历，从头节点到尾节点。

• 单向链表结构

单向链表有多种用途。一个典型应用是维护一个必须按正确顺序处理的项目列表。例如，单向链表可以用来保存一个必须完成的任务列表，其中头节点代表第一个任务，尾节点代表最后一个任务。单向链表也经常用于必须以相反顺序处理元素列表的算法。例如，流行的排序算法快速排序将要排序的对象列表存储在单向链表中。快速排序可以通过反向处理列表来更有效地对其进行排序。

• 单向链表的创建和遍历

链表是一种数据结构，它包含一个按特定顺序排列的组件列表。列表中的每个元素都称为节点，每个节点都链接到列表中的下一个节点。列表中的第一个节点称为头节点，最后一个节点称为尾节点。我们必须先定义一个节点类来构建单向链表。每个节点将有两个数据成员，例如一个整数值和一个指向列表中下一个节点的引用。下一步是开发一个 LinkedList 类。此类将有两个数据成员，即头节点和尾节点。列表中的第一个元素将存储在头节点中，列表中的最后一个元素将存储在尾节点中。

要向列表中添加元素，我们必须创建一个新节点，并将前一个尾节点的下一个引用设置为指向新节点。然后，我们可以使新节点成为列表的新尾。要从列表中删除元素，我们必须先找到包含我们要删除的值的节点。这可以通过遍历列表直到找到具有匹配值的节点来完成。找到节点后，我们应该将前一个节点的下一个引用更改为指向下一个节点。要查找列表中的元素，我们必须遍历它，直到找到具有匹配值的节点。要遍历列表，我们可以从头节点开始，向下移动，直到到达尾节点。

双向链表

双向链表（Doubly linked list）也称为双向链表。因此，您可以双向遍历它。与单向链表相比，其节点有一个额外的指针，称为前向指针（previous pointer）。此指针指向前一个节点。

• 双向链表结构

双向链表是由单向链表（SLLs）组成的集合，这些单向链表是双向链接的。它以一种能够更快地添加和删除元素的方式存储数据。每个 SLL 有两个部分，包括一个头和一个尾。每个 SLL 都有一个指向列表中第一个元素的指针（在头节点中）和一个指向列表中最后一个元素的指针（在尾节点中）。它易于实现，可用于各种应用程序。

• 双向链表的创建和遍历

双向链表是一种数据结构，它允许像单向链表一样线性存储数据。与单向链表不同，双向链表允许对其中存储的数据进行向前和向后遍历。这使得它成为需要能够向前和向后遍历数据列表的应用程序的合适数据结构。我们必须首先开发一个 Node 类来保存我们的数据，以便创建一个双向链表。这个 Node 类将有两个属性，分别是 data 和 next。data 属性将保存我们要存储在列表中的实际数据，next 属性将引用下一个节点。创建 Node 类后，我们可以创建我们的双向链表。为此，我们必须首先开发一个类来表示我们的列表。这个类有两个属性，head 和 tail。head 属性将引用我们列表中的第一个节点，而 tail 属性将引用我们列表中的最后一个节点。创建列表类后，我们可以开始向其中添加数据。

要向我们的列表中添加数据，我们必须首先创建一个新节点，并将其 data 属性设置为我们要添加的数据。然后，我们必须将新节点的 next 属性设置为指向我们列表中的第一个节点。最后，我们将我们列表的 head 节点指向新节点。现在我们已经知道如何添加数据，我们可以编写一个函数来遍历我们的列表。为此，我们必须首先创建一个变量，该变量将跟踪我们正在探索的当前节点。首先，我们可以将此变量设置为我们列表的 head 节点。然后，我们应该设计一个 while 循环，该循环将一直运行，直到当前节点为 None，这表明我们已到达列表末尾。在 while 循环中，我们需要打印当前节点中的数据。然后，在继续循环的下一次迭代之前，我们需要将当前节点设置为我们列表中的下一个节点。

循环链表

循环链表（Circular linked list）是单向链表。因此，您只能沿一个方向遍历。但是，此链表中的最后一个节点指向头节点。因此，在遍历时，您必须小心并在到达头节点时停止。

• 循环链表结构

循环链表是一种数据结构，它使用链表技术以线性、顺序的方式存储数据。另一方面，与典型的链表不同，循环链表没有开始或结束，它实际上是一个节点环。因此，循环链表适用于必须以连续循环方式处理数据的应用程序，例如实时应用程序或模拟。单向链表数据结构通常用于实现循环链表。这意味着列表中的每个节点都有一个指向下一个节点的指针。然后通过将列表中的最后一个节点连接到第一个节点来形成环状结构。循环链表中的数据访问与传统链表中的数据访问类似。但是，由于列表没有明确的开始或结束，因此很难知道从哪里开始遍历它。因此，许多循环链表实现使用指向列表中第一个节点的“头”指针。

与传统链表相比，使用循环链表有几个优点。首先，数据可以随时添加和删除，因为列表没有固定的开始或结束。因此，循环链表非常适合数据必须定期添加或删除的应用程序，例如在实时应用程序中。其次，由于数据存储在环状结构中，因此可以以连续循环的方式访问数据。循环链表适用于必须以连续循环方式处理数据的应用程序，例如实时应用程序或模拟。第三，循环链表通常比传统链表更节省内存，因为列表没有固定的开始或结束。这是因为传统链表通常需要额外的内存来存储指向列表开始和结束的指针。另一方面，循环链表只需要一个内存指针，即头指针。最后，循环链表通常比传统链表更简单、更容易实现。这是因为传统链表通常需要不同的数据结构，例如堆栈和队列来跟踪列表的开始和结束。相比之下，循环链表只需要一个单向链表数据结构。

• 循环链表的创建和遍历

循环链表是一种可以保存项目列表的数据结构。它与单向链表和双向链表都有联系。与末尾包含 NULL 指针的单向链表不同，循环链表有一个指向列表第一个节点的指针。这使您可以遍历整个列表，而无需跟踪列表的末尾。循环链表分为单向链表和双向链表。单向循环链表中的每个节点都包含一个指向下一个节点的指针。列表的最后一个节点指向第一个节点。双向循环链表中的每个节点都包含指向下一个和上一个节点的指针。循环链表有多种用途。它们可用于创建队列、堆栈和双端队列。它们也适用于需要循环缓冲区或循环数组的应用程序。

可以通过两种方式创建循环链表

• 创建一个单向链表，其中最后一个节点指向第一个节点。
• 创建一个双向链表，其中最后一个节点指向第一个节点，第一个节点指向最后一个节点。

要创建单向循环链表，首先我们应该创建一个单向链表。我们可以通过开发一个 Node 类和一个 LinkedList 类来完成此操作。Node 类将表示列表中的每个节点，LinkedList 类将表示列表本身。

要创建双向循环链表，首先我们需要创建一个双向链表。我们可以通过创建 Node 类和 LinkedList 类来完成此操作。Node 类将表示列表中的每个节点，LinkedList 类将表示列表本身。创建 Node 和 LinkedList 类后，我们可以通过生成几个节点并将它们链接在一起来创建循环链表。首先，我们必须先创建一个节点。然后必须将节点链接在一起以形成循环链表。或者，我们也可以使用双向链表来连接节点。

循环链表可以通过两种方式遍历

• 通过遍历列表返回到头节点。
• 记录您访问过的节点。

当循环可以遍历列表直到再次到达头节点时，您可以使用列表或集合来跟踪您访问过的节点。

循环双向链表

双向循环链表（Circular doubly linked list）是双向链表和循环链表的混合体。与双向链表一样，它有一个称为前向指针（previous pointer）的额外指针，并且像循环链表一样，它的最后一个节点指向头节点。这种类型的链表是双向列表。因此，您可以双向遍历。

• 双向循环链表结构

双向循环链表（DCL）类似于一种双向链表。DCL 中的第一个和最后一个节点链接在一起形成一个圆。这使得无需在列表的开头或结尾进行特殊情况处理，即可快速轻松地遍历整个列表。

DCLs 经常用于必须以顺序方式处理数据的应用程序，例如在视频或音频播放器中。列表的循环结构使得在节点之间快速轻松地移动，而无需额外的特殊情况处理。DCLs 也用于需要随机访问数据的应用程序，例如数据库。在这种情况下，列表的循环特性使得无需特殊情况处理即可快速轻松地跳转到任何节点。

• 双向循环链表的创建和遍历

要构建双向循环链表，我们必须首先创建一个节点结构，用于容纳我们的数据和指针。然后，我们可以创建一个 head 指针并将其初始化为 null。接下来，我们需要创建函数以将新节点添加到列表中。此函数应接受要插入的数据和 head 指针作为输入。然后，它应该用此数据创建一个新节点并将其插入到列表中。最后，我们应该编写一个函数来遍历列表并输出每个节点中包含的数据。此函数应以 head 指针作为输入。然后，它应该通过输出每个节点中包含的数据来遍历列表。

不同类型链表的应用

• 使用链表实现堆栈和队列。
• 稀疏矩阵表示为链表。
• 可以使用循环链表实现图像查看器。
• 可以使用链表思想来导航网站。
• 可以使用循环双向链表实现斐波那契堆。

链表的优点

• 动态数据结构

链表是一种动态数据结构，因为它可以动态分配和释放内存，从而在运行时增长和收缩。因此，无需指定链表的初始大小。

• 无内存浪费

链表中没有内存浪费，因为链表的大小在运行时增加或减少。因此，没有内存浪费，也不需要预先分配内存。

• 实施

堆栈和队列等线性数据结构通常使用链表实现。

• 插入和删除操作

链表中的插入和删除操作更简单。插入或删除元素后，无需移动元素，只需更新下一个指针中的地址即可。

• 灵活

与数组元素不同，链表元素不存储在连续的内存位置。

• 对大量数据有效

在处理大量数据集时，链表起着重要作用，因为它们可以动态增长和收缩。

• 可扩展性

它具有从任何位置添加或删除元素的能力。

链表的缺点

• 内存要求

链表比数组需要更多内存。因为链表需要一个指针来存储下一个条目的地址，所以它需要额外的内存。

• 遍历

在链表中，遍历比在数组中更耗时。与数组不同，链表不允许按索引直接访问元素。例如，要访问位置 n 处的节点，您必须遍历所有前面的节点。

• 反向遍历

单向链表中无法反向遍历，但在双向链表中可以，因为每个节点都有一个指向先前连接节点的指针。为此，需要为后向指针分配更多内存，因此会浪费内存。

• 随机访问

由于链表中的动态内存分配，不可能进行随机访问。

• 有时效率较低

某些活动，例如搜索元素或遍历列表，在链表中可能较慢。

• 复杂的实现

链表的实现比数组方法更复杂。它需要对编程有透彻的理解。

• 难以共享数据

由于无法直接访问链表条目的内存地址，因此不容易通信数据。

• 不适用于小型数据集

与数组相比，它无法在小型数据集上提供任何实质性改进。

结论

链表通常用于收集需要从序列中间高效插入和删除条目的对象序列。链表通过构建一组包含需要保存的值或信息的引用的节点来构建。最后，链表通过作为其他数据结构和算法的基础，为处理具有灵活性的数据元素集合提供了动态且有效的方法。