例如，Java有ArrayList和LinkedList，它们的行为与人们对Big O.的预期一致
JavaScript有一个数组[]，它的行为就像一个动态数组，因为你可以在任何你喜欢的地方插入和删除它，在最后的中间等等
对于某些数据集较大的情况，使用链表可以获得更好的插入和删除时间。我宁愿不自己实现，也不使用库。如果它不存在，是否有计划在未来添加它？
为了解释这一点，我们来解释一下为什么java的LinkedList几乎完全无用。这就应该理解为什么一个真正有用的LinkedList在API中实现起来有点棘手了。
对于某些数据集较大的情况，使用链表可以获得更好的插入和删除时间。
不，除非在非常非常奇特的情况下。让我们开始吧。
假设你有一个包含50个元素的列表，你想在在中间添加一些内容。对于arraylists，这意味着系统必须将25个元素向上"移动"到一个插槽中，这样才能有"空间"，如果后备阵列刚好达到容量，情况会变得更糟(在这种情况下，我们必须创建一个新阵列，将原始阵列复制到这个新创建的两块中的一块，然后在正确的索引处设置新值)。但至少系统知道在哪里切割。
现在让我们看看链表。理论上，这是一个O(1)操作：创建一个新的跟踪器对象，将其"prev"设置为第24个元素，将其"next"设置为第25个元素，然后更新第24个元件的跟踪器，使其"next"指向新的跟踪器，并更新第25个元件的追踪器，使其的"prev"指向新跟踪器。完成。即使列表中有几百万个条目，这种算法也能工作。O(1)。正确的
没有。问题是，您是如何到达的？
list.add(25, newItem)无法神奇地绕过LinkedList几乎致命的缺点，即：它必须迭代25个元素，才能首先找到正确的跟踪器。换句话说，LinkedList的.add(idx, newItem)方法与ArrayList的方法一样是O(n)
如果你把O(n)land抛在后面，进入语用学，人们可能会说，当你在列表的"开始"附近添加时，LinkedList具有出色的性能，而ArrayList在那里会处于最差的状态(LinkedList只需要迭代几个跟踪器就可以到达正确的跟踪器，而Array list需要移动一个巨大的块)，但你不想这样做-当我们把理论性能模型(即O(n)表示法)抛在后面，而进入实际性能时，LinkedList的真的很糟糕-几乎所有可能出错的非算法的东西都会出错。
一旦我们谈到"一开始就添加"，LinkedList的"一开始很快"就会发展到完美，并保证O(1)行为。然而，这有点假——你可以简单地从arraylist中获得相同的性能，只需将其包装成一个反转所有操作的东西(例如，.get(x)实现为.get(size() - 1 - x))，因为arraylist在末尾插入时是O(1)。所以这并不是什么额外的奖励。大多数情况下，只需使用ArrayDeque，它在近距离开始时有着出色的表现，在近距离结束时也同样出色。
关于语用学：
LinkedList需要一个跟踪器对象：一个有3个字段的额外对象：
value：链表中该位置的实际值prev：这个列表中摆在我们面前的项目的跟踪器对象(因为LinkedList是双向可遍历的；如果你不需要双向，你可以忽略这个)。第一个元素是nullnext：这个列表中在我们后面的项目的跟踪器对象——它是最后一个的null
最后，列表本身只是两个字段：start和end，起点指向第一个对象的跟踪器，end指向最后一个对象的追踪器。具有具有null值的空链表。
这些跟踪器对象的价格非常昂贵。
现代CPU无法访问内存。完全他们只能访问整个页面中的片上缓存。CPU可以发送到内存控制器的唯一操作是"将整个页面刷新到主内存"(它不能刷新半个页面；页面大小取决于您的CPU，但考虑64k左右)，以及"通过从主内存加载整个页面来替换片上缓存"。这两种操作都需要500个或更多的CPU周期，所以CPU真的会像拇指一样转动，而慢如糖蜜的内存控制器则会完成它的工作。主内存组距离CPU只有几纳秒的距离，仅此一点就让它慢得像糖蜜！
因此，当你谈论一个小的数组列表时，假设JVM保证数组"在内存中是连续的"，只要整个列表适合一个页面，那么实际上它上的所有操作都是即时的，整个O(n)听起来不错，但实际上，这完全没有意义。
正如他们所说，在理论上，实践就像理论一样。但在实践中。。。。它通常离这儿很远。
LinkedList走向了相反的方向——现代CPU设计的本质(这里引用的是"现代"——在缓存页上，CPU没有实际的直接内存访问，这已经有十多年的历史了)实际上是个坏消息：那些额外的跟踪器有一种严重的趋势，即不连续，这意味着对链表的完全遍历会导致大量缓存未命中，每一次缓存未命中都会带来500多个CPU周期的空闲时间。哎哟。
那么，我该如何从这个东西中挤出O(1)性能呢
在java中？唯一的方法是使用.listIterator()或.iterator().remove()从ArrayList有O(n)的LinkedList中获得O(1)性能的唯一方法是通过这些
您可以使用ListIterator迭代到正确的位置(如果您想在中间添加，这将是O(n))，但从那里您可以随心所欲地添加，并且每个.add操作实际上都是O(1)，尽管您正在制作的跟踪器可能在不同的缓存页中，因此您会对该列表的任何未来性能产生负面影响。
太糟糕了。有更好的方法吗
肯定有！想象字符串的链接列表。但现在想象一下，java自己的String类比您习惯的多了两个字段：String next;和String prev;，next和prev指向列表中的下一个/上一个字符串。现在，您只需从任何字符串中"在该字符串和列表中的下一个字符串之间添加一个新内容"，只需更新.next.prev，然后更新.next，即可指向新字符串(当然，还可以为新字符串中的next和prev字段分配正确的值)。现在，你如何获得列表中的任何项目都无关紧要，一旦你获得了它，你就可以在列表上执行O(1)运算。我们甚至可以在跟踪器上"保存"-我们不需要它们(单个对象中的字段本身保证是连续的，但请注意，所有非原始字段当然都是指针，它们指向的对象可能不是)。
但是java不是这样工作的。
有些语言可以很容易地制作一个在内存中充当单个新类型的伪"组合类型"(即保证某些类型的组合和对类型的某些添加的连续性)，这通常被称为"混合类型"。有了这种能力，您可以创建自己的链表，甚至不会有任何名为LinkedList的类型——有些类型只是在命令中"增长"next和prev变量。
java不是那样的。Javascript可以是-对象实际上只是hashmap，如果您愿意，您可以自由地引入prev和next指针。要做到这一点，你不需要任何类型的内置类型，你只需要一个教程，真的。
尽管如此，还是很好的
实际上javascript几乎不包含电池。众所周知，像左填充字符串这样疯狂而简单的东西需要一个臭名昭著的库。
因此，更普遍地说，"为什么javascript没有X烘焙"的答案是一个非常普遍的答案："因为javascript根本没有太多烘焙"。
我不相信你——我是O(n)教会的一名持牌成员
好吧，作为一名程序员，有些怀疑是非常健康的，对你来说太好了！
你应该写一些代码来测试你的先入为主的想法。并且在你做的时候检验我的理论！
例如，使用list.set(list.size() / 2, newElem)制作插入中间的代码，并在list是ArrayList实例时为其计时，也为LinkedList实例计时。确保你使用了一个框架来知道如何正确地做到这一点，因为在热点编译、JVM预热、跳过没有产生任何完全使用的结果的代码的优化、现代CPU设计以及现代操作系统不是实时的事实之间，这真的很难做到。因此，使用Java Microbenchmark Harness来运行这些测试。
您会发现，创建一个LinkedList显著优于ArrayList的场景是非常困难的，而创建相反的场景则非常容易。即使在基本的big-O表示法可能会提出其他建议的情况下。
那么我应该用什么来代替呢
在某些情况下，ArrayList的性能特征肯定不好。然而，对于几乎所有可以想象的场景，LinkedList都不是最好的，甚至不是一个好的替代方案。相反，看看ArrayDeque，或者重写算法以使用TreeMap或HashMap，使用数据库、skiplist、基元列表(因为您可以拥有相当大的基元列表，并且仍然可以获得出色的性能)或enumsets。
其中大多数也没有javascript等价物，但在节点生态系统中，所有这些都有第三方库。当然，如果你这样做，你最终可能会遇到padLeft的崩溃，但当你决定首先使用javascript时，你就有点注册了。