2 javascript java arrays big-o linked-list
例如，Java 具有 和ArrayList，LinkedList其行为与 Big O 的预期一致。
JavaScript 有 array []，它的行为就像一个动态数组，因为你可以在任何你喜欢的地方插入和删除它，在中间、最后等等。
对于某些具有大型数据集的情况，使用链表具有更好的插入和删除时间。我不想自己实现一个或使用图书馆。如果不存在，以后有计划添加吗？
rzw*_*oot 11
为了解释这一点，让我们解释一下为什么javaLinkedList几乎完全没用。这应该可以解释为什么实际有用的 LinkedList 在 API 方面实现起来有点棘手。
对于某些具有大型数据集的情况，使用链表具有更好的插入和删除时间。
不，事实并非如此，除非是在非常非常奇特的情况下。让我们开始吧。
假设您有一个包含 50 个元素的列表，并且您想在中间添加一些内容。对于数组列表，这意味着系统必须将 25 个元素向上“移动”一个槽，以便有“空间”，如果后备数组正好达到容量，情况会更糟（在这种情况下，我们必须创建一个新数组，将原始值分两块复制到新创建的值，然后在正确的索引处设置新值）。但至少系统知道在哪里剪切。
现在让我们看看链接列表。理论上，这是一个 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) 行为。然而，这有点假 - 你可以轻松地从 arraylist 中获得相同的性能，只需将其包装成一个反转所有操作的东西（例如，.get(x)实现为.get(size() - 1 - x)），因为 ArrayList 在末尾插入的时间复杂度为 O(1) 。所以这并没有什么好处。大多数情况下，只需使用 ArrayDeque，它对于 add-near-start 具有出色的性能，对于 add-near-end 也同样出色。
关于这些语用学：
LinkedList 需要一个跟踪器对象：一个具有 3 个字段的额外对象：
value：链表中该位置的实际值prev：此列表中前面一项的跟踪器对象（因为 LinkedList 是双向可遍历的；如果不需要双向，可以忽略此一项）。这是null第一个元素。next：此列表中位于我们之后的项目的跟踪器对象 - 这是null最后一个。最后，列表本身只有 2 个字段：start和end， start 指向第一个对象的跟踪器和end最后一个对象的跟踪器。使用具有值的空链表null。
那些跟踪器对象很昂贵。
现代 CPU 无法访问内存。完全没有。他们只能访问整个页面中的片上缓存。CPU 可以发送到内存控制器的唯一操作是“将整个页面刷新到主内存”（它不能刷新页面的一半；页面大小取决于您的 CPU，但可以考虑 64k 左右），以及“替换此页面”通过从主内存加载整个页面来实现片上缓存”。这两个操作都需要 500 个或更多的 CPU 周期 - 所以 CPU 确实会做相当多的拇指转动，而慢如糖蜜的内存控制器则在工作。主内存条距离 CPU 相当几个光纳秒，仅此一点就让它慢得像糖蜜一样！
因此，当您谈论较小的数组列表时，鉴于 JVM 保证数组“在内存中是连续的”，只要整个列表适合单个页面，那么实际上对它的所有操作都是瞬时的，整个O(n)事情听起来不错，但是，这完全没有意义，真的。
正如他们所说，理论上，实践就像理论。但在实践中......它通常相距甚远。
LinkedList 走向相反的方向 - 现代 CPU 设计的本质（这里用引号引起来的“现代” - 芯片上的缓存页面并且 CPU 没有实际的直接内存访问已经有十多年的历史了）实际上是坏消息：额外的跟踪器有一种讨厌的不连续的倾向，这意味着对链表的完整遍历会导致大量缓存未命中，并且每个缓存未命中都会带来 500 多个 CPU 周期的空闲时间。哎哟。
在java中？唯一的方法是使用.listIterator(), 或.iterator().remove()。从 LinkedList 中获得 O(1) 性能（其中 ArrayList 具有 O(n)）的唯一方法就是通过这些！
您可以使用 ListIterator 迭代到正确的位置（O(n)如果您想在中间添加，这将是 ），但是从那里您可以添加任意数量的内容，并且每个.add操作确实是 O(1)，尽管您正在制作的跟踪器可能位于不同的缓存页面中，因此您会对该列表的任何未来性能产生负面影响。
肯定有！想象一个字符串的链表。但现在想象一下，java 自己的String类比您习惯的多了 2 个字段：String next;和String prev;，其中 next 和 prev 指向列表中的下一个/上一个字符串。现在，您可以从任何字符串“在该字符串和列表中的下一个字符串之间添加一个新内容”，只需更新.next.prev, 然后.next, 指向新字符串（当然，还可以分配下一个和上一个字符串）新字符串中的字段具有正确的值）。现在，如何获得列表中的任何项目并不重要，一旦获得它，就可以在列表上执行 O(1) 操作。我们甚至可以在跟踪器上“保存” - 我们不需要它们（单个对象中的字段本身保证是连续的，但请注意，所有非原始字段当然都是指针，并且它们指向的东西可能不是）。
但java不是这样工作的。
有些语言可以很容易地制作一个代用的“组合类型”，它在内存中充当单个新类型（即保证某些类型和该类型的某些添加的组合的连续性），这通常称为“混合”。有了这种能力，您可以创建自己的链表，甚至不需要任何名为LinkedList- 有些类型只是根据命令“增长”下一个和上一个变量。
java只是不是那样的。JavaScript 可以是——对象实际上只是哈希图，如果你愿意，你可以随意引入上一个和下一个指针。要做到这一点，您不需要任何类型的内置类型，您只需要一个教程，真的。
实际上javascript几乎不包含电池。众所周知，像向左填充字符串这样疯狂简单的事情需要一个相当臭名昭著的库。
因此，更一般地说，“为什么 javascript 没有内置 X”的答案是非常普遍适用的：“因为 javascript 根本没有内置太多”。
O(n)！好吧，作为一名程序员，有些怀疑是很健康的，这对你有好处！
您应该编写一些代码来测试您的先入之见。并在你参与的同时测试我的理论！
编写代码，例如在中间插入，并为 ArrayList 实例和 LinkedList 实例list.set(list.size() / 2, newElem)计时。list确保您使用的框架知道如何正确执行此操作，因为在热点编译、JVM 预热、跳过不产生任何完全使用的结果的代码的优化、现代 CPU 设计以及现代操作系统的事实之间不是实时的，这真的很难做到。因此，使用Java Microbenchmark Harness来运行这些测试。
您会发现创建 LinkedList 显着优于 ArrayList 的场景非常困难，反之则相当容易。即使在基本的大 O 符号表示其他情况的情况下也是如此。
当然，在某些情况下 ArrayList 的性能特性并不好。然而，对于几乎所有可以想象的情况，LinkedList 都不是最好的，甚至不是一个很好的替代方案。相反，查看ArrayDeque或重写算法以使用TreeMap或HashMap，使用数据库、跳过列表、原始列表（因为您可以拥有非常大的原始列表，并且仍然获得出色的性能）或枚举集。
其中大多数也没有 javascript 等效项，但所有这些在节点生态系统中都有第三方库。当然，如果你这样做，你最终可能会遇到整个 padLeft 崩溃的事情，但是当你决定首先使用 javascript 时，你就有点同意了。