几天前，在 Twitter 上（哦，亲爱的 Twitter：无论发生什么，我都会在那里待得越久越好——如果你在乎那些为它倾注了大量心血的人，离开这个平台之前请三思）。在 Twitter 上，我谈到了一个用 Rust 写的非常糟糕的链表实现。从某些回复的语气来看，我感觉很多人认为链表就像个笑话：一个只配出现在编程面试里的、除此之外毫无用处的简单数据结构。一言以蔽之：数据结构中的冒泡排序。我不同意这种看法，所以我想写这篇博客文章，讲讲我喜爱链表的所有理由。

所以，准备好读一篇关于数据结构的深情之作吧，别说我没提醒过你。

链表具有教育意义。当你的老师，或书中的某一页，或任何让你第一次接触链表的东西，向你展示那个指向另一个圆圈的小圆圈时，某种宏大的东西会在你的脑海中发生。这类似于你第一次理解递归时的感受。你领会了由链接构成的数据结构真正的本质：一个简单的节点，一旦引用了另一个节点，就变得强大和复杂得多。链表向新手程序员展示了计算中关于空间和时间的基本道理：如何以常数时间添加元素，以及为什么有序性从根本上是昂贵的，因为如果你想“就地”插入一个元素，你必须从一个节点走到另一个节点。你立刻开始思考如何加速这个过程（为接下来的学习做好准备），同时你也深刻地理解了 O(1) 和 O(N) 的真正含义。

链表是可扩展的。添加一个指向前一个元素的指针，现在就可以双向遍历了。时不时添加一些“远”指针，你就得到了一个性质完全不同的跳表。让每个节点容纳多个元素，你的链表就变成了展开链表，提供截然不同的缓存友好性。链表还可以被嵌入。例如，Linux 内核提供了宏，可以给任何结构体添加一个字段，以便把它们链接在一起。还有更多：链表是可组合的。这是一个大胆的性质：你可以在 O(1) 内把一个链表拆分成两个，也可以在 O(1) 内把两个链表拼接起来。如果明智地利用这个性质，就能实现一些有趣的东西。例如，在实现线程化操作的 Redis 模块中，处理慢请求的线程面对的是一个伪造的客户端结构（这样就无需加锁，也没有竞争）。当线程化的命令最终执行完毕时，该客户端的输出缓冲区可以被直接拼接到真实客户端的实际缓冲区上。这之所以容易实现，是因为输出缓冲区是用链表表示的。

链表是有用的：Redis 可能会出错，但 Redis 和 Linux 内核不可能都出错。链表有用，是因为它们类似于某些自然过程：按照事物到达的顺序添加它们，或者按相反的顺序添加，即使在物理世界中也是很自然的。逐步地取出元素也很有用，把这些元素从头移动到尾，或者把它们移动到当前位置之后，同样如此。

链表是简单的。它是那些罕见的数据结构之一——与二叉树、哈希表以及其他少数几个一样——你仅凭记忆就能实现它，而不太可能犯下大错。

链表是富有概念性的。一个指向自身的节点，是我在计算领域能想象到的最以自我为中心的东西：最粗俗的死循环的理想化身。一个指向 NULL 的节点，是孤独的隐喻。尾和头相连的链表，则是封闭循环的强大象征。

基于所有这些理由，我热爱链表，我希望你至少能开始对它报以微笑。