为了解释这一点，让我们解释一下为什么 java 的 LinkedList 几乎完全没用。这应该继续解释为什么实际有用的 LinkedList 在 API 方面实现起来有点棘手。

对于某些大型数据集的情况，使用 linked list 具有更好的插入和删除时间。

不，它没有，除非在非常非常奇特的情况下。让我们开始吧。

假设您有一个包含 50 个元素的列表，并且您想在中间添加一些内容。对于数组列表，这意味着系统必须将 25 个元素向上“移动”一个插槽以便有“空间”，如果后备数组正好满载，情况会变得更糟（在这种情况下，我们必须创建一个新数组，将原件复制到这个新创建的两块中，然后将新的 value 设置在正确的索引处）。但至少系统知道在哪里切割。

现在让我们看看链接列表。理论上，这是一个 O(1) 操作：创建一个新的跟踪器对象，将其“上一个”设置为第 24 个元素，将其“下一个”设置为第 25 个元素，然后将第 24 个元素的跟踪器更新为“下一个”指向新的跟踪器，并更新第 25 个元素的跟踪器，使其“prev”指向新的跟踪器。完毕。即使列表中有数不胜数的条目，该算法也有效。 O(1)。正确的？

不，问题是，你怎么去那里？

list.add(25, newItem) 不能神奇地绕过 LinkedList 几乎致命的缺点，即：它必须遍历 25 个元素才能首先到达正确的跟踪器。换句话说，LinkedList 的 .add(idx, newItem) 方法和 ArrayList 的一样是 O(n)！

如果您将 O(n) 土地抛在身后并开始使用语用学，那么当您在列表的“开始”附近添加时，可能会说 LinkedList 具有出色的性能，而 ArrayList 在那里的表现最差（LinkedList 只需要迭代几个跟踪器找到正确的，而 ArrayList 需要移动一个巨大的块），但你不想这样做 - 当我们将理论性能模型（即 O(n) 表示法）抛在后面并获得实际性能时， LinkedList 真的很糟糕——几乎所有不是算法的东西都可能出错，LinkedList 确实出错了。

一旦我们谈论“在开头添加”，LinkedList 的“开始时快速”就会变得完美，并保证 O(1) 行为。然而，这有点假——你可以很容易地从数组列表中获得相同的性能，只需将它包装成一个反转所有操作的东西（例如，.get(x) 被实现为 .get(size() - 1 - x)），因为 ArrayList 是 O(1 ) 在末尾插入。所以这并不是什么好处。大多数情况下，只需使用 ArrayDeque，它对于 add-near-start 具有出色的性能，对于 add-near-end 也同样出色。

关于那些语用：

LinkedList 需要一个跟踪器对象：一个具有 3 个字段的额外对象：

• value：linked list 中此位置的实际 value
• prev：此列表中我们前面的项目的跟踪器对象（因为 LinkedList 是双向可遍历的；如果您不需要双向，则可以将其省略）。第一个元素是 null。
• next：此列表中我们之后的项目的跟踪器对象 - 最后一个是 null。

最后，列表本身只是两个字段：start 和 end，start 指向第一个对象的跟踪器，end 指向最后一个对象的跟踪器。使用具有 null values 的空链表。

那些跟踪器对象很昂贵。

现代 CPU 无法访问内存。完全没有。他们只能访问整个页面中的片上缓存。 CPU 可以发送到内存控制器的唯一操作是“将整个页面刷新到主内存”（它不能刷新页面的一半；页面大小取决于您的 CPU，但考虑 64k 左右），并“替换这个通过从主内存加载此整个页面来进行片上缓存”。而且这两个操作都需要 500 或更多的 CPU 周期 - 所以 CPU 真的会在慢如糖蜜的内存控制器完成它的工作时做相当多的拇指操作。那个主内存库距离 CPU 有好几纳秒的距离，仅此一项就让它像糖蜜一样慢！

因此，当您谈论一个较小的数组列表时，鉴于 JVM 保证 arrays 在内存中是“连续的”，只要整个列表适合单个页面，那么实际上对它的所有操作都是瞬时的，并且整个 O(n) 事情听起来不错，但实际上完全没有意义。

正如他们所说，理论上，实践就像理论一样。但在实践中......它通常是遥不可及的。

LinkedList 走向相反的方向——现代 CPU 设计的本质（这里引用的“现代”——片上缓存页面和 CPU 没有实际的直接内存访问在这一点上已有十多年的历史了）实际上是个坏消息：那些额外的跟踪器有一种不连续的趋势，这意味着完全遍历 linked list 会导致大量缓存未命中，并且每个缓存未命中都会带来 500 多个 CPU 周期的空闲时间。哎哟。

那么我如何从这件事中挤出 O(1) 性能呢？

在 java 中？唯一的方法是使用 .listIterator() 或 .iterator().remove()。从 ArrayList 具有 O(n) 的 LinkedList 中获得 O(1) 性能的唯一方法是通过这些！

您可以使用 ListIterator 以您的方式迭代到正确的位置（如果您想在中间添加，这将是 O(n)），但是您可以从那里添加任意数量的内容，并且每个 .add 操作都是确实是 O(1)，尽管您创建的跟踪器可能位于不同的缓存页面中，因此您对该列表的任何未来性能都有负面影响。

太糟糕了。有没有更好的办法？

肯定有！想象一个字符串的链表。但现在想象一下，java 自己的 String 类比你习惯的多了 2 个字段：String next; 和 String prev;，其中 next 和 prev 指向列表中的下一个/上一个字符串。现在，您只需更新 .next.prev，然后更新 .next，即可从任何字符串“在此字符串和列表中的下一个字符串之间添加一个新内容”（当然， ，用右边的 values 分配新字符串中的 next 和 prev 字段）。现在，您如何获得列表中的任何项目都无关紧要，一旦获得它，您就可以在列表上执行 O(1) 操作。我们甚至可以在跟踪器上“保存”——我们不需要 em（单个对象中的字段本身保证是连续的，但请注意，所有非原始字段当然都是指针，以及它们所指向的东西可能不是）。

但是 java 不能那样工作。

一些语言可以很容易地制作一个在内存中作为单一新类型的 ersatz 'combi-type'（即保证某些类型的组合和对该类型的一些添加的连续性），这通常称为“mixins”。有了这种能力，您可以创建自己的链表，而且您甚至不会有任何名为 LinkedList 的类型——某些类型只是在命令上“增长”下一个和上一个变量。

java 不是那样的。 Javascript 可以是 - 对象实际上只是 hashmaps ，如果需要，您可以自由地引入 prev 和 next 指针。为此，您不需要任何类型的任何内置类型，您只需要一个教程，真的。

不过还是不错的

实际上 javascript 几乎没有包含电池。众所周知，像左填充字符串这样疯狂的简单化需要https://qz.com/646467/how-one-programmer-broke-the-internet-by-deleting-a-tiny-piece-of-code/。

所以，更一般地说，“为什么 javascript 没有 X 烘焙”的答案是非常普遍适用的：“因为 javascript 根本没有太多烘焙”。

我不相信你——我是O(n)教会的持卡成员！

好吧，作为一名程序员，有些怀疑是相当健康的，对你有好处！

您应该编写一些代码来测试您的先入之见。并在你做的时候测试我的理论！

制作代码，例如当 list 是 ArrayList 的实例以及 LinkedList 的实例时，使用 list.set(list.size() / 2, newElem) 在中间插入并计时。确保您使用框架来知道如何正确执行此操作，因为在热点编译、JVM 预热、跳过不会产生任何完全使用的结果的代码的优化、现代 CPU 设计以及现代操作系统的事实之间t 实时，这真的很难做到。因此，使用 https://www.baeldung.com/java-microbenchmark-harness 来运行这些测试。

您会发现创建 LinkedList 明显优于 ArrayList 的场景非常困难，反之则很容易。即使在基本 big-O 表示法会提出其他建议的情况下。

那么我应该改用什么？

在某些情况下，ArrayList 的性能特征肯定不好。但是，对于几乎所有可以想象到的情况，LinkedList 都不是最好的，甚至不是一个很好的替代方案。相反，请查看 ArrayDeque，或重写算法以使用 TreeMap 或 HashMap，使用数据库、跳过列表、原始列表（因为您可以拥有非常大的原始列表并且仍然获得出色的性能）或枚举集。

其中大多数也没有 javascript 等效项，但所有这些都具有节点生态系统中的第三方库。当然，如果你这样做，你最终可能会遇到整个 padLeft 崩溃的事情，但是当你决定首先使用 javascript 的那一刻，你就有点注册了。