链表只有面试有用？Redis 之父说：我不同意！

几天前，Redis 之父 Salvatore Sanfilippo（又名 antirez）在 Twitter 上用 Rust 实现了一个糟糕的链表，引发了大家的讨论。

在评论中，不少人觉得链表这种数据结构一无是处，于是几天后，antirez 发了一篇博客。

原文见：http://antirez.com/news/138

antirez 说：“从某些评论的语气中，我感觉到很多人认为链表就像一个笑话，‘一种微不足道的数据结构’‘也就面试的时候用一下，否则，一无是处’……，一言以蔽之，请用链表实现冒泡排序。”

“我不赞成！所以用一篇博客表达，和大家分享我眼中的链表。”

（小伙伴们，准备好阅读一篇关于链表的“情诗”吧！感谢张同学和岳老师对翻译工作的贡献与指导）

链表具有教育意义

当从老师、教材等资料那里第一次接触到链表的时候，带有箭头的圆圈通过箭头指向另一个圆圈，你的脑海中自然会建立对应的构图。就像你第一次对递归有所理解时候的体悟。你会感受到由链接而成数据结构的真正要义：不起眼的单个节点，一旦它指向另一个节点，就会被赋予更强的能力和更高的复杂度。链表为新手程序员很好地引入了计算中关于空间和时间的基本知识：你会思考如何高效添加元素，思考顺序存储所带来的代价。因为如果想在特定位置插入一个元素，那么必须从一个节点到另一个节点按顺序遍历，由此你会马上转而思考加快执行的方法（为接下来的任务做好准备），同时也能够深入地理解了 O (1) 和 O (N) 的真正含义。

链表是可扩展的

可以添加指向前一个元素的指针，也可以添加指向后一个元素是指针，链表支持双向访问。再添加“远”指针，可以在链表内部跳跃访问。除此之外，还可以对每个节点进行更改，容纳多个属性和操作，进而拓充功能，拥有不同的存储策略。链表同时也支持嵌入。例如，Linux 内核具有宏，能够将字段添加到任何结构体，进而组成链表。这是链表的一个 bold 属性：可以在 O (1) 复杂度内将一个链表拆分为两个，也可以在 O (1)复杂度内将两个链表融合在一起。如果巧妙利用这个属性，可以完成很多有意思的任务。例如，在 Redis 模块中进行线程操作，处理慢速请求的线程处理了一个伪造的客户端结构体（没有锁，没有争用），当线程指令最终结束执行时，伪造客户端的输出缓冲区可以链接到真实客户端的缓冲区中。因为输出缓冲区是用链表表示的，使得这种操作简单易行。

链表很有用

Redis 可能会出错，但 Redis 和 Linux 内核不会。它们就这样自然而然地发生了：按照它们到达的顺序，或者相反的顺序依次添加。以增量方式拉动项目也很有用，因为它会将这些项目从头到尾移动，或者将它们移动到当前项目之后的位置。

链表很简单

它是稀有的，遇见“她”花费了我不少运气。与二叉树、哈希表等结构一起，可以仅从内存中实现，且不会出现什么大问题。

链表是概念性的

指向自身的节点是我能想象到的计算中最以自我为中心的东西：更粗俗的无限循环的理想表示。指向 NULL 的节点是孤独的隐喻。首尾相连的链表，是闭环的有力象征。

所以，我深爱着链表，多么希望你也能喜欢“她”，至少，从今天开始，可以给“她”一个微笑！

大家学习链表的时候，是怎样去理解它的呢？

“一般都和数组一起！”

没错，我们来对比看看数组和链表的区别~

假设我们要存储一份有 3 个项目的待办清单：

如果使用数组，占用连续的存储空间，那么它存在内存里是这样的：

如果使用链表，每个项目可以存在内存的任何地方，就是这样的：

显然，数组看起来更好理解。

但是假设你现在要加入第 4 个待办项目，放在哪里呢？这时就需要重新找到一个可以连续放 4 个项目的位置，添加第 5 个项目时呢？还需要重新找。太麻烦了，虽然我们可以通过提前预留位置来减少移动这份清单的次数，但还是避免不了浪费位置的情况。

链表就不同了，它更像一个寻宝游戏，每个格子里写着下一个格子位置的“线索”，只要内存里还有位置，就可以无限添加，不用移动已经存好的数据。

链表完美了吗？当然不是！

排行榜网站总是使用“卑鄙”的手段来增加页面浏览量。比如“十大电视反派”排行，它不在一个页面中显示整个排行榜，而是 TOP10 在第 1 页，剩下 9 个都单独放在一个页面中，让你不停地单击“Next”才能看到第一大反派，好让这 10 个页面中的广告都增加展示次数，真是烦！

链表就存在类似的问题。如何解决呢？聪明的你快来评论区聊聊吧！

数据结构魅力无限，仅仅是数组和链表就有这么多精彩的细节，想要了解更多有趣的数据结构和算法故事？下面两本书推荐给大家！

第 1 本

第 2 本

这两本书

双十一期间 5 折直降！

错过等一年！

点击下方链接直达页面

—— 电子书活动 ——