链表是否仍然相关？

Question

我偶然发现了这篇文章：Should you ever use Linked List。它引用了在可用内存和RAM结构方面的技术进步，使用数组将比链表更好。

还有一个老问题When to use a linked list over an array/array list?

本文中的参数是否真的有效，链表是否已经过时，或者如果参数为真，使用LinkedList仍然比使用数组更好的情况会是什么情况？(举例说明任何一点都会很有帮助)

Answer 1

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

我会用另一种方式来解释这个问题:如今，链表更容易被接受。在386上，你必须注意性能，但现在，我们甚至用Python编写程序，并忍受它们的速度。从使用VM (或被解释)的语言编写的代码数量来看，我认为可以公平地说，许多人并不担心他们选择的数据结构中的缓存缺失。

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