Go 语言的数据结构：链表

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

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

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

链表

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

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

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

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

数据流

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

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

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

type Post struct {
    body         string
    publishDate int64 // Unix timestamp
    next *Post // link to the next Post
}

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

type Feed struct {
    length int // we'll use it later
    start  *Post
}

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

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

func (f *Feed) Append(newPost *Post) {
    if f.length == 0 {
        f.start = newPost
    } else {
        currentPost := f.start
        for currentPost.next != nil {
            currentPost = currentPost.next
        }
        currentPost.next = newPost
    }
    f.length++
}

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

func main() {
    f := &Feed{}
    p1 := Post{
        body: "Lorem ipsum",
    }
    f.Append(&p1)

    fmt.Printf("Length: %v\n", f.length)
    fmt.Printf("First: %v\n", f.start)

    p2 := Post{
        body: "Dolor sit amet",
    }
    f.Append(&p2)

    fmt.Printf("Length: %v\n", f.length)
    fmt.Printf("First: %v\n", f.start)
    fmt.Printf("Second: %v\n", f.start.next)
}

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

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

Length: 1
First: &{Lorem ipsum 1257894000 <nil>}
Length: 2
First: &{Lorem ipsum 1257894000 0x10444280}
Second: &{Dolor sit amet 1257894000 <nil>}

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

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

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

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

优化 Append

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

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

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

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

type Feed struct {
    length int
    start  *Post
    end    *Post
}

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

func (f *Feed) Append(newPost *Post) {
    if f.length == 0 {
        f.start = newPost
        f.end = newPost
    } else {
        lastPost := f.end
        lastPost.next = newPost
        f.end = newPost
    }
    f.length++
}

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

1. 现在代码更简单、更短了。
2. 我们极大地提高了函数的时间复杂度。

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

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

移除一个 Post

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

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

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

func (f *Feed) Remove(publishDate int64) {
    if f.length == 0 {
        panic(errors.New("Feed is empty"))
    }

    var previousPost *Post
    currentPost := f.start

    for currentPost.publishDate != publishDate {
        if currentPost.next == nil {
            panic(errors.New("No such Post found."))
        }

        previousPost = currentPost
        currentPost = currentPost.next
    }
    previousPost.next = currentPost.next

    f.length--
}

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

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

插入一个 Post

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

func (f *Feed) Insert(newPost *Post) {
    if f.length == 0 {
        f.start = newPost
    } else {
        var previousPost *Post
        currentPost := f.start

        for currentPost.publishDate < newPost.publishDate {
            previousPost = currentPost
            currentPost = previousPost.next
        }

        previousPost.next = newPost
        newPost.next = currentPost
    }
    f.length++
}

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

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

如果我们使用数组呢？

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

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

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

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

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