c - 链接列表仍然相关吗？

Question

我遇到了这篇文章：您是否曾经使用过 Linked List。它指出，鉴于可用内存和 RAM 结构的技术进步，使用数组会比链表更好。

还有一个老问题何时在数组/数组列表上使用链表？

文章中的论点是否真的成立并且 Linked List 是否已经过时，或者如果论点为真，使用 LinkedList 仍然比 Arrays 更好的场景是什么？（举例说明任何一点都会有帮助）

Answer 1

废话。O(n) 永远不会超过常数时间。任何需要使用已保存的迭代器进行插入的列表都将使用链表。它们是基本结构，不会消失。

我会以另一种方式旋转这个论点：这些天链接列表更容易接受。在 386 上，您必须注意性能，但现在，我们甚至用 Python 编写程序并忍受它们的速度。从使用虚拟机（或被解释）的语言编写的代码量来看，我认为可以公平地说，很多人在选择数据结构时并不担心缓存未命中。

我们现在拥有快速的 CPU，因此通常不需要担心在实现我们的数据结构时可能需要的一些额外指令。我们可以查看我们的用途，找出我们有什么要求，并根据它们的渐近性能选择我们的结构。这也使代码更易于维护：如果您在六个月后发现对于 n=100 列表毕竟更快，您将不必更改代码。分析是一项艰巨的工作，因此我们应该在消耗大量 CPU 的日子里非常自在地选择具有我们想要的算法属性的结构，而不是猜测向量。