Go 语言的数据结构：链表

数据结构和算法是计算机科学的重要组成部分。虽然有时候它们看起来很吓人，但大多数算法都有简单的解释。同样，当问题能用算法来解释清楚的时候，算法的学习和应用也会很有趣。

这篇文章的目标读者是那些对链表感到不舒服的人，或者那些想要看到并学习如何用 Golang 构建一个链表的人。我们将看到如何通过一个（稍微）实际的例子来实现它们，而不是简单的理论和代码示例。

在此之前，让我们来谈谈一些理论。

链表

链表是比较简单的数据结构之一。维基百科关于链接列表的文章指出：

在计算机科学中，链表是数据元素的线性集合，其中线性顺序不是由它们在内存中的物理位置所给出的。相反，每个元素指向下一个元素。它是由一组节点组成的数据结构，它们共同代表一个序列。在最简单的形式下，每个节点都由数据和一个指向下个节点的引用（换句话说，一个链接）组成。

尽管这些看起来可能太过或令人困惑，让我们把它分解一下。 线性数据结构，是一种其元素组成某种序列的数据结构。 就这么简单。为什么记忆中的物理位置不重要呢？ 当你有数组时，数组的内存数量是固定的，就是说，如果你有一个 5 项的数组，语言只会在内存中只抓取 5 个内存地址，一个接一个。 因为这些地址创建一个序列，数组知道它的值将存储在什么内存范围内，因此这些值的物理位置将创建一个序列。

有了链表，就有点不同了。在定义中，您将注意到“每个元素指向下一个”，使用“数据和引用（换句话说，就是链接）指向下一个节点”。这意味着链接列表的每个节点存储两个东西：一个值和一个指向列表中的下一个节点的引用。就这么简单。

数据流

人类所感知到的一切都是某种信息或数据，我们的感官和头脑知道如何处理并将其转化为有用的信息。 不管我们是看，闻，还是摸，都是我们在处理数据，并从数据中找到意义。当我们浏览我们的社交媒体网络时，我们总是求助于数据，按时间顺序排列，有看不完的信息。

那么，我们如何使用链表来建模这样的新闻流呢? 让我们先快速浏览一下简单的 Tweet，例如:

实例我们社交网络的目的，我们从 Twitter 获得灵感并创建一个 类型，它有一个 ，一个 和一个 帖子的链接:

接下来，我们如何建模一个帖子的提要？如果我们知道数据流是由一个连着另一个的帖子组成，那么我们可以试着创建一个这样的类型：

结构将有一个开始(或 )，它指向提要中的第一个 Post 和一个 属性，该属性将在任意时刻存储 的大小。

因此，假设我们想创建一个有两个帖子的 ，第一步是在 类型上创建一个 函数:

然后我们可以两次调用它:

那么这段代码是用来干嘛的呢？首先， 函数 - 创建一个指向 结构的指针，两个 结构包含一些虚构的内容，它两次调用 上的 函数，使得它的长度为 2 。我们检查 的两个值，它访问 (实际上是 t )的 和 后的 项，这是第二个 。

当我们运行程序时，输出将会是:

可以看出，当我们在 添加第一个 后，它的长度为 1 并且第一个 拥有一个 和一个 （作为 Unix 时间戳），与此同时，它的 值为 nil 。 然后，我们将第二个 添加到 中，当我们查看两个 时，我们会看到第一个 的内容与之前的内容相同，但它的指针指向列表中的下一个 。 第二个 也有一个 body 和一个 ，但是没有指向列表中的下一个 的指针。 此外，当我们添加更多的 时， 的长度也会增加。

现在让我们回过头来看 函数并解构它，这样我们就能更好地理解如何使用链表。 首先，该函数创建一个指向 值的指针，将 参数作为 的 ，并将 设置为当前时间的 Unix 时间戳表示。

然后，我们检查 的length是否为 0 — 这意味着它没有 Post 。第一个被添加的 会被设为起始 Post，为方便起见，我们把它命名为 start。

但是，如果 的长度大于 0 ，那么我们的算法就会发生不同的变化。 它将从 的 开始，它将遍历所有的 ，直到找到一个没有指向 next 的指针。 然后，它将把新的 附加到列表的最后一个 上。

优化 Append

想象一下，我们有个用户刷 ，就像其他社交网络一样。 由于文章是按时间顺序排列的，基于 ， 会随着用户的滑动而变得越来越多，更多的 Post 会被附加到 上。 考虑到这种方法，我们采用了 函数，因为 变得越来越长， 函数将会付出越来越沉重的代价。 为什么? 因为我们必须遍历整个 ，在末尾添加一个 。如果你听说过 Big-O 表示法，这个算法有一个 O(n) 的时间复杂度，这意味着它在添加 之前总是遍历整个 。

您可以想象，这可能非常低效，特别是如果“Feed”增长相当长。如何改进“追加”函数，降低其渐近复杂性?

因为我们的 数据结构只是一个 Post 的列表，要遍历它，我们必须知道列表的开头(称为 start )，它是 类型的指针。 因为在我们的示例 中总是添加一个 到 的末尾，如果 不仅知道它的起始 元素，而且还知道它的 结束元素，那么我们可以大大提高算法的性能。 当然，对于优化总是有一个折衷，这里的权衡是数据结构将消耗更多的内存(对于 结构的新属性)。

扩展我们的 Feed 数据结构是轻而易举的：

但是，我们的 Append 算法必须被调整，以适应 Feed 的新结构。这是使用 Post的 end 属性的 Append 的版本:

这看起来简单一点，对吧？让我给你一些好消息:

现在代码更简单、更短了。

我们极大地提高了函数的时间复杂度。

我们在重新审视一下算法，它做了两件事情：如果 为空，它就会设置一个新的 作为 的开头和结尾，反之它会设置一个新的 作为 end 项并且依附到链表中先前的 。很重要的一点是它很简单，并且算法复杂度为 O(1) ,也称为常数时间复杂度。这意味着无论 结构的长度如何， 都将执行相同的操作。

很简单，对吧？但让我们想象一下， 实际上是我们的配置文件中的 Post列表。因此，它们是我们的，我们应该能够删除它们。我的意思是，什么样的社交网络不允许用户(至少)删除他们的帖子?

移除一个 Post

正如我们在前一节中建立的，我们希望我们的 用户能够删除他们的帖子。那么，我们如何建立模型呢?如果我们的 是一个数组，我们就会删除该条目并对其进行处理，对吧？

这事实上就是链表闪耀的地方。当数组大小改变时，运行时会捕获一个新的内存块来存储数组的项。 由于其设计的链表，每个条目都有一个指向列表中的下一个节点的指针，并可以分散到整个内存空间中，从空间的角度来看，从列表中添加或者删除节点是低开销的。 当一个人想要从一个链表中移除一个节点时，只需要连接被删除节点的邻居节点。 垃圾收集语言(如 Go 语言)使这个更加容易，因为我们不必担心释放被分配的内存 —— GC 将启动并删除所有未使用的对象。

为了让我们操作方便，让我们给每个 上的 设置一个限制，它将有一个独特的 。这意味着发布者可以在他们的 上每秒钟创建一个 。将其付诸实施，我们可以很容易地从 中删除 :

函数将把 作为一个 作为一个参数，它将检测哪些 需要删除(或未链接)。 这个函数很小。如果它检测到 Feed 的 项将被删除，它将会重新分配 的 ，并在 中添加第二个 。 否则，它会跳转到 Feed 中的每个 Post ，直到它遇到一个 ， 该 有一个匹配的 作为函数参数。 当它找到一个时，它会把之前的和下一个 连接在一起，有效地从 Feed 中删除中间(匹配)一个。

有一个边界情况，我们需要确保我们在 Remove 函数中覆盖 —— 如果 Feed 没有带有指定的 publishDate 的 Post ？ 为了简单，函数会检查 Feed 中的下一个 Post ，然后再跳到它。如果下一个是 nil 的函数，它告诉我们它找不到一个 publishDate 的 Post 。

插入一个 Post

现在我们有了添加和移除的方法，让我们来看看一些假设的情形。 假设生成 Post 的来源并不是按照时间顺序将他们发送到我们的应用程序的。 这就意味着需要基于 publishDate 将 Post 放到 Feed 中合适的位置。比如这样：

本质上，这是一个非常类似于 函数的算法，因为尽管它们都做了一件非常不同的事情(在 中添加 . 删除 )，它们都是基于搜索算法的。 这意味着，这两个函数实际上遍历整个 ，搜索与 匹配的 Post，并在函数的参数中接收到一个 。 唯一的区别是， 实际上会在日期匹配的地方放置新的 ，而 将从 中删除 。

此外，这意味着这两个函数都具有相同的时间复杂度，即 O(n) 。 这意味着在最坏的情况下，函数必须遍历整个 才能到达需要插入新 (或删除)项。

如果我们使用数组呢？

如果你问自己，让我先说，你有一个观点。 的确，我们可以将所有的 Post 存储在一个数组中(或者是一个 Go 语言的 slice )，可以轻松地将条目推到它上面，甚至还可以使用 O(1) 复杂性随机访问。

鉴于数组的性质，它的值必须存储在内存中，所以读取速度非常快而且开销很低。 一旦你有了存储在数组中的东西，就可以用它的 0-based 索引来获取它。 在插入一个条目时，无论是在中间还是在最后，数组的效率都不如链表。 这是因为如果数组没有为新项保留更多的内存，它将不得不保留它并使用它。 但是，如果下一个内存地址不是空闲的，它将不得不“移动”到一个新的内存地址，只有那样才有空间容纳它的所有项(新和旧的)。

看看我们到目前为止的所有例子和讨论，我们可以为我们创建的每一个算法创建一个具有时间复杂度的链表，并将它们与数组的相同算法进行比较:

正如你所看到的，当面对一个特定的问题时，选择正确的数据结构可以真正地成就或毁掉你所创建的产品。 对于不断增长的 ，插入 是最重要的，链表会做得更好，因为插入非常代价更小。 但是，如果我们的手上有一个不同的问题需要频繁的删除或大量的检索/搜索，那么我们就必须为我们正在处理的问题选择正确的数据结构。

你可以看到 的整个实现，并在这里体验它。另外，Go 语言也有自己的链表实现，它已经内置了一些不错的功能。你可以在这里看到它的文档。