链表到底是什么？[第一部分]

信息无处不在。

在软件世界中，我们选择组织信息的方式是成功的一半。但问题是：解决问题的方法有很多。在组织数据方面，有很多工具可以胜任这项工作。关键在于知道使用哪种工具最合适。

无论我们使用哪种语言编写代码，我们首先接触到的都是数据结构，也就是我们组织数据的不同方式；变量、数组、 哈希表和对象都属于数据结构。但这些只是数据结构的冰山一角；数据结构还有很多，有些结构你了解得越多，就越觉得它们复杂。

对我来说，链表一直是那些复杂事物之一。我知道链表已经有几年了，但我总是记不清它们到底是什么。只有在准备技术面试（或者有时在面试过程中）时，有人问我关于链表的问题时，我才会真正想到它们。我会做一些研究，自以为了解它们的含义，但几周后，我又忘了它们。整个过程效率很低，而这一切都源于我知道它们的存在，但我并不从根本上理解它们！所以，是时候改变这种现状，回答这个问题了：链表到底是什么？

线性数据结构

如果我们真的想了解链表的基础知识，那么讨论它们是什么类型的数据结构就很重要。

链表的一个特点是它们是线性数据结构，这意味着它们的构造和遍历是有序的。我们可以将线性数据结构想象成跳房子游戏：为了到达列表的末尾，我们必须按顺序（或按顺序）遍历列表中的所有项目。然而，线性结构与非线性结构相反。在非线性数据结构中，项目不必按顺序排列，这意味着我们可以非顺序地遍历数据结构。

我们可能并不总是意识到这一点，但我们每天都在使用线性和非线性数据结构！当我们将数据组织成哈希表（有时也称为字典）时，我们就是在实现一种非线性数据结构。树和图也是非线性数据结构，我们以不同的方式遍历它们，但我们将在今年晚些时候更深入地讨论它们。

类似地，当我们在代码中使用数组时，我们实际上是在实现一种线性数据结构！将数组和链表想象成数据排序方式类似会很有帮助。在这两种结构中，顺序都很重要。但是，数组和链表有什么不同呢？

内存管理

数组和链表之间最大的区别在于它们在机器中使用内存的方式。对于使用 Ruby、JavaScript 或 Python 等动态类型语言的人来说，在日常编写代码时无需考虑数组占用多少内存，因为有几层抽象，我们完全不必担心内存分配。

但这并不意味着内存分配不会发生！抽象并非魔法，它只是简单地隐藏那些你不需要经常看到或处理的东西。即使我们在编写代码时不必考虑内存分配，如果我们想真正理解链表内部的运作方式以及它强大的功能，就必须深入到最基本的层面。

我们已经学习了二进制以及数据如何分解成位和字节。正如字符、数字、单词和句子需要占用内存字节来表示一样，数据结构也需要占用内存字节来表示。

创建数组时，需要一定量的内存。如果我们有 7 个字母需要存储在一个数组中，那么我们需要 7 个字节的内存来表示该数组。但是，我们需要将所有内存放在一个连续的内存块中。也就是说，我们的计算机需要找到 7 个空闲的内存字节，一个字节挨着一个字节，全部放在一个地方。

另一方面，链表诞生时，并不需要将 7 个字节的内存全部集中在一个地方。一个字节可以存储在某个地方，而下一个字节可以存储在内存中的另一个地方！链表不需要占用任何一块内存；相反，它们使用的内存可以分散在各个地方。

数组和链表之间的根本区别在于，数组是静态数据结构，而链表是动态数据结构。静态数据结构需要在创建时分配所有资源；这意味着即使结构的大小增加或缩小，元素被添加或删除，它仍然需要一定大小和数量的内存。如果需要向静态数据结构添加更多元素，而它没有足够的内存，则需要复制该数组的数据，然后重新创建具有更多内存的数组，以便可以向其中添加元素。

另一方面，动态数据结构可以在内存中收缩和增长。它不需要分配固定数量的内存才能存在，它的大小和形状可以改变，所需的内存量也可以改变。

到目前为止，我们已经开始看到数组和链表之间的一些主要区别。但这引出了一个问题：是什么让链表的内存分散到各处？要回答这个问题，我们需要了解链表的结构。

链表的组成部分

链表可大可小，但无论大小，组成它的部分实际上都相当简单。链表由一系列节点组成，这些节点是链表的元素。

列表的起点是对第一个节点的引用，该节点称为head。几乎所有链表都必须有一个 head ，因为它实际上是列表及其所有元素的唯一入口，没有它，你就不知道从哪里开始！列表的末尾不是一个节点，而是一个指向null（或空值）的节点。

单个节点也非常简单。它只有两部分：数据（即节点包含的信息）以及对下一个节点的引用。

如果我们能理解这一点，那么我们就成功了一半。节点的工作方式非常重要，也非常强大，可以概括如下：

一个节点只知道它包含什么数据，以及它的邻居是谁。

单个节点并不知道链表的长度，甚至可能不知道链表的起始和终止位置。节点唯一关心的就是它包含的数据，以及它的指针指向哪个节点——链表中的下一个节点。

这正是链表不需要连续内存块的原因。因为单个节点拥有指向下一个节点的“地址”或引用，所以它们不需要像数组中的元素那样紧挨着彼此。相反，我们可以依靠指向下一个节点的指针引用来遍历列表，这意味着我们的机器不需要为了表示列表而阻塞一块内存。

这也解释了为什么链表可以在程序执行过程中动态增长和收缩。使用链表添加或删除节点变得像重新排列一些指针一样简单，而不是复制数组的元素！然而，链表也有一些缺点，我现在暂时不提——“下周我会详细介绍。”

现在，我们只需沉浸在链表的酷炫之中！

各种形状和大小的列表

即使链表的组成部分不变，我们构建链表的方式也可能大相径庭。就像软件中的大多数事情一样，根据我们试图解决的问题，一种类型的链表可能比另一种更适合。

单链表是最简单的链表类型，因为它只朝一个方向。我们可以通过一条路径遍历整个列表；从头节点开始，从根节点开始遍历，直到最后一个节点，最后一个节点的值为空。

但是，正如一个节点可以引用其后续邻居节点一样，它也可以拥有指向其前一个节点的引用指针！这就是我们所说的双向链表，因为每个节点包含两个引用：一个指向下一个节点的引用，以及一个指向前一个节点的引用。如果我们不仅希望能够沿单轨或单向遍历数据结构，而且还希望能够反向遍历，那么双向链表就非常有用。

例如，如果我们希望能够在一个节点和上一个节点之间跳转，而无需回到列表的最开头，那么双向链表会比单向链表更适合。然而，任何操作都需要空间和内存，所以如果我们的节点必须存储两个引用指针而不是一个，那就需要另行考虑了。

循环链表有点奇怪，因为它的结尾不是指向空值的节点。相反，它有一个节点作为链表的尾部（而不是传统的头节点），尾节点之后的节点是链表的开头。这种组织结构使得在链表末尾添加内容变得非常容易，因为你可以从尾节点开始遍历，因为第一个元素和最后一个元素互相指向。循环链表可能会变得非常疯狂，因为我们可以将单链表和双链表都变成循环链表！

但是无论链表有多复杂，如果我们能够记住节点的基本原理及其工作原理以及列表中不同指针引用的结构，那么就没有我们无法解决的链表！

下周，在本系列的第二部分中，我们将深入探讨链表的空间时间复杂度，以及它与它的“表亲”数组的比较。我保证，这实际上比听起来有趣得多！

资源

如果您认为链表非常酷，请查看这些有用的资源。

1. 数组和链表之间的区别，Damien Wintour
2. 数据结构：数组与链表，mycodeschool
3. 链接列表：基础知识，Edward Gehringer 博士
4. 链表简介，Victor Adamchik 博士
5. 数据结构与实现，Jennifer Welch 博士
6. 静态数据结构与动态数据结构，Ayoma Gayan Wijethunga