几天前在 Twitter 上（哦，亲爱的 Twitter：无论发生什么，我都会尽可能久地留在这里——如果你在乎那些为它倾注了大量心血的人，离开这个平台前请三思）。当时在 Twitter 上，我聊到了一个用 Rust 写的非常糟糕的链表实现。从一些回复的语气来看，我感觉很多人把链表当成了笑话。一种除了应付编程面试就一无是处的平庸数据结构，除此之外毫无用处。一句话概括：数据结构里的冒泡排序。我不同意，所以想写下这篇博客，聊聊我喜欢链表的种种理由。

所以，准备好读一篇关于数据结构的多愁善感的文章吧，别说我没提醒过你。

链表具有教育意义。当你的老师、书上的一页、或是任何第一次让你接触链表的东西，向你展示那个带箭头指向另一个圆圈的小圆圈时，你的脑海中会发生某种巨大的变化。就像你第一次理解递归时那样。你领会了由链接构成的数据结构的真正含义：单个节点的平凡，一旦指向另一个节点，就会变得强大而复杂得多。链表向初学者揭示了计算中关于空间与时间的一些根本问题：如何在常数时间内添加元素，以及有序为何在本质上是昂贵的，因为如果你想“就地”插入一个元素，就必须逐个节点地遍历。你会立刻开始思考加速这一过程的办法（这也为你学习后面的知识做好了准备），与此同时，你也会深刻地理解 O(1) 和 O(N) 究竟意味着什么。

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

链表是有用的：Redis 可能会错，但 Redis 和 Linux 内核不可能同时都错。它们有用，是因为它们贴近某些自然过程：按到达顺序添加东西，或按相反顺序添加，在物理世界中也是自然而然的。增量地取出元素也很有用，把元素从头部移到尾部，或是把它移动到当前位置之后一个位置，同样如此。

链表是简单的。它是少数几种罕见的数据结构之一，和二叉树、哈希表等一样，你可以仅凭记忆就把它实现出来，而且不太可能犯下大错。

链表是富有概念意味的。一个指向自身的节点，是我能在计算中所能想象到的最以自我为中心的事物：对那种更粗陋的无限循环的完美体现。一个指向 NULL 的节点，则是孤独的隐喻。而一条首尾相连的链表，则是闭环的强有力象征。

正是出于所有这些原因，我热爱链表，也希望你至少能开始对它们报以微笑。