[ Elixir | 为什么使用链表？]

我一直觉得数据结构很酷，但你知道什么更酷吗？那就是在实际应用中看到它们！

在阅读 Elixir 的文档时，我发现 Elixir 底层使用链表作为其线性数据结构。我觉得这很酷，但有一点让我很困惑：我理解数组和链表，但我完全不明白它们与编程语言的联系。这个问题一直困扰着我，我需要弄清楚为什么Elixir 会使用链表，所以就有了这篇文章！

回到文章本身，根据我目前的研究，Elixir 这样做的原因可能有三点（当然，我的理解可能完全错误，欢迎指正！）。让我们逐一来看：

不可篡改数据

在 Elixir（实际上大多数函数式语言都是如此）中，数据是不可变的。这是理解为什么使用链表的重要第一步，所以让我们来探讨一下。

不可变性意味着一旦数据被声明，就不能再对其进行修改/更改。

假设你已经了解数组的底层工作原理（如果你想复习一下，可以看看我的另一篇文章）。让我们来看看如果尝试用数组实现不可变性会发生什么！

数组被定义为一块连续的内存块。问题在于，一个包含 5 个元素的数组仍然只是一个数组，当我们添加/删除元素时，我们就是在修改它。那么，我们如何才能在数组中实现不可变性呢？这并非不可能，但让我们来看看为什么这样做并不实际。

如果我们想要在数组中强制执行真正的不可变性，这意味着每次我们想要在数组中添加/删除元素时，都需要对旧数组进行完整复制。

这意味着，如果你有一个大小为 5 的数组，如果你想向其中添加一个新元素，你的内存使用量会立即翻倍（因为你需要保持原数组不变，同时还需要创建一个包含相同元素的新数组）。而这仅仅是空间复杂度，我们还需要考虑时间复杂度！

链表没有同样的限制，因为节点都单独存储在内存中，这意味着我们在向链表中添加/删除节点时，不必担心空间/时间复杂度。

这给了我们第一个解释为什么它使用列表的理由，但这并不是全部原因——递归结构/尾部共享在这里发挥作用，一切开始变得有意义。

递归结构

你有没有注意到，链表根据定义就是递归的？

例如，A -> B -> C -> D是一个链表，也是一个链表B -> C -> D，C -> D依此类推，每个链表都只是另一个链表的子结构！

这本身并没有什么令人兴奋的地方，但这对解开下一个谜题至关重要！

有趣的事实：递归的特性，再加上数据必须是不可变的（所以你不能有循环计数器），这就是为什么函数式语言通常与递归联系在一起的原因——它们某种程度上不得不如此！

结构/尾部共享

因此，我们知道链表本质上是递归的。结合编程语言的不可变性，我们知道数据永远不会改变。

这很有意思，因为现在我们可以自信地说，这A -> B -> C -> D两个列表是不同的B -> C -> D（即使一个列表递归地包含另一个列表），而且由于我们有了这个保证（以及列表不能改变的事实），我们就不必定义两次相同的数据，并且可以重用现有的链表！这被称为结构共享。

很棒吧？我们来看一个例子。

例如：

list = [5,6,7,8]
list_one = [1 | list]
list_two = [2 | list]

现在我们有三个不同的列表！list，list_one和list_two，但它们都共享同一个引用（尾部），它们之间唯一的区别是头部指针。

这意味着内存中总共会有 6 个元素。向列表中添加元素占用内存很少，同时又能保持我们所需的不可变性。

可重复使用的婴儿用品！

如果你想了解更多，可以研究一下Trie 树，它与共享数据/前缀的概念完全相同！

垃圾回收和缓存？

这两个我不太确定，但我听说链表有利于垃圾回收，而尾共享很适合局部性引用/缓存（我不明白为什么，因为它们存储的位置不一样）。如果有人愿意分享一下，那就太好了！

结语

顺便提一下，实际上这跟 Elixir 关系不大，因为它最终会编译成 Erlang，但跟 Erlang 也关系不大，因为所有函数式编程做的事情都差不多，但这正是引起我好奇心的原因，所以才跟 Elixir 扯上了关系。

在撰写本文的过程中，我发现必须先深入讲解数组的工作原理，才能深入探讨 Elixir 部分，所以我把这部分内容作为另一篇文章发布在这里；请阅读那篇文章，以便更好地了解其中的权衡取舍！

数组的工作原理

Edison Yap ・ 2019年2月12日

#Ruby #计算机科学 #C

我也没有详细讨论大 O 符号，因为我觉得它们可能会增加文章不必要的阅读时间和复杂性，但它们对于计算机科学来说非常重要和基础，所以我建议你稍微复习一下。

如果你喜欢播客，可以收听CodeNewbie 的BaseCS 播客，该播客由 Vaidehi Joshi 和 Saron 共同主持。

不过，如果你想阅读的话，Vaidehi Joshi 的博客文章版本（我相信正是它启发了播客的创作）在BaseCS Medium上也很棒。

至于视频教程，MyCodeSchool简直太棒了，我几乎所有现在掌握的知识都是在那里学到的，强烈推荐！

除此之外，希望你们和我一样喜欢这篇文章！

来源

https://elixir-lang.org/getting-started/basic-types.html#linked-lists - 这篇文章的灵感来源