列表实现：LinkedList与ArrayList和TreeList相比真的表现不佳吗？
取自Apache TreeList doc ：
以下相对性能统计数据表示此类：
get add insert iterate remove TreeList 3 5 1 2 1 ArrayList 1 1 40 1 40 LinkedList 5800 1 350 2 325
它继续说：
LinkedList很少是一个很好的实现选择。TreeList几乎总是一个很好的替代品，虽然它确实使用了更多的内存。
我的问题是：
-
什么是使用
ArrayListadd，insert和remove时间来破坏LinkedList？ 我们是否应该期望，真实世界的插入和删除案例非常有利于ArrayList？ -
这个
TreeList只是简单地将钉子放在古老的LinkedList的棺材里吗？
我很想得出结论，他们已经摊销或忽略了ArrayList不断增长的痛苦，并没有考虑到已经找到的LinkedList中项目的插入和删除时间。
这里的关键是三个List实现中插入/删除操作的复杂性。 对于任意索引，ArrayList具有O（n）插入/删除时间，但如果操作位于列表的末尾，则它为O（1）。 ArrayList还具有对任何位置进行O（1）访问的便利。 LinkedList类似地是O（n），但对于任意位置的List（开始和结束）和O（n）访问的任何一端的操作是O（1）。 TreeList对于任何位置的所有操作都具有O（logn）复杂度。
这清楚地表明，就任意位置的插入/删除而言，TreeList对于足够大的列表来说更快。 但是AFAIK，TreeLists是作为二叉搜索树实现的，并且与其O（logn）操作相关联的常量要大于使用ArrayLists的类似操作，而ArrayLists只是数组的包装器。 这使得TreeList实际上对于小列表来说更慢。 此外，如果你所做的只是将元素附加到List中，那么ArrayList / LinkedList的O（1）性能显然更快。 此外，插入/删除的数量通常比访问次数少得多，这使得ArrayList在许多情况下总体上更快。 LinkedList在List两端的常量时间插入/删除使得它在实现Queues，Stacks和Deques等数据结构时更快。
在一天结束时，这完全取决于你需要什么样的List。 没有一个通用的解决方案。 您必须选择最适合您工作的实施方案。
这是由于这些集合背后的数据结构 。 TreeList是一棵树 ，允许相对快速的读取，插入，删除（所有O（log n））。 ArrayList使用数组来存储数据，因此当您插入或删除时，数组中的每个项都必须向上或向下移动（O（n）最坏的情况）。 数组也有固定的大小，因此如果它溢出当前数组的容量，则必须创建一个新的，较大的（通常是最后一个的两倍，以保持resize最小）。 使用LinkedList … 链表 。 链表通常引用列表中的第一个（有时是最后一个）元素。 然后，列表中的每个元素都对列表中的下一个元素（对于单链表）或下一个和前一个元素（对于双链表）有所引用。 因此，要访问特定元素，必须遍历每个元素才能到达（O（n）最坏情况）。 插入或删除特定元素时，必须找到插入或移除它们的位置，这需要时间（O（n）最坏情况）。 然而，简单地在开头或结尾添加另一个元素（O（1））的成本非常低。
有关于数据结构的完整书籍以及何时使用它们，我建议阅读更基本的书籍。
因为链接列表必须逐个节点地导航以获取列表中的任何位置（根据实现保存前面和后面可能），因此数字是如此之高。
对于在大型LinkedList中添加/插入/删除，您将从节点到节点进行大量跳转以到达正确的位置。
如果他们制作了适当大小的ArrayList，那么成长的痛苦将一事无成。 如果ArrayList很小，那么成长的烦恼并不重要。
对于LinkedList，如果操作都在列表的前面附近，那么它的影响远小于它们在最后的情况。
您应该做的是始终使用接口，例如：在声明变量和参数时列出，然后您可以更改“new LinkedList（）;” to“new ArrayList（）;” 并分析代码以查看它在特定代码中的执行情况。
由于不必从节点跳到节点的速度，我总是默认使用ArrayList而不是LinkedList。
我相信树列表会明显快于两者（即使没有查看代码）。 树木设计得很快。
在这里回答的每个人都是正确的。 他们都是正确的，他们在很大程度上取决于你的使用模式，即没有一个适合所有人的名单。 但是在我写作的那一刻，当LinkedList处于最佳状态时，他们都忘记提及（或者我或者是草率的读者）一个用例：迭代器定位插入。 这意味着，如果你不是这样做的话
LinkedList::add(int index, E element) Inserts the specified element at the specified position in this list.
这似乎是他们用来获取统计数据的方法，但是
iterator.insert(E element)
通过任何一个获得的iterator
public abstract ListIterator listIterator(int index) Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.
要么
public Iterator iterator() Returns an iterator over the elements in this list (in proper sequence).
那么你一定会获得最好的任意插入性能。 这当然意味着，您可以限制对iterator（）和listIterator（）的调用次数，以及迭代器在列表中的移动次数（例如，您只能对列表执行一次顺序传递以执行所需的所有插入操作）。 这使得它的使用情况在数量上非常有限，但是它们很常见。 而LinkedList在其中的表现就是它（并将在未来）保存在所有语言的所有容器集合中的原因，而不仅仅是Java。
PS。 所有上述当然都适用于所有其他操作，如get（），remove（）等。即通过迭代器精心设计的访问将使所有这些操作都具有非常小的实际常量O（1）。 当然，对于所有其他列表也可以这样说，即迭代器访问将加速它们（无论多少）。 但不是ArrayList的insert（）和remove（） – 它们仍然是O（n）……而不是TreeList的insert（）和remove（） – 树平衡开销不是你可以避免的……和TreeList可能有更多的内存开销……你明白我的想法。 总而言之，LinkedList适用于列表上的小型高性能扫描类操作。 这是否是您需要的用例 – 只有您可以告诉。
PSS。 那就是说，我因此也留下来了
试图得出结论，他们已经摊销或忽略了ArrayList不断增长的痛苦，并没有考虑已经找到的LinkedList中项目的插入和删除时间。
对于ArrayList，由于它很少进行，基本上可以忽略不计。 如果它实际上是一个问题，那么只需将数组放大即可。
如果我有一个小列表，那么使用LinkedList是有意义的，因为在那一点上有最小的好处。 如果列表很长，那么显然TreeList更有意义。
如果我要对列表进行大量随机访问，那么ArrayList更有意义。
使用哪个容器实际上取决于您将使用它做什么。 没有一个正确的容器，因为每个容器都有自己的优点和缺点，并且凭借经验，您开始了解何时使用哪个容器。
请注意，ArrayList通常比LinkedList更快，即使您的代码只调用两者的常量时间方法。 例如，ArrayList.add（）简化了复制单个变量并在不需要resize时递增计数器，而LinkedList.add（）还必须创建一个节点并设置多个指针。 此外，LinkedList节点需要更多内存，这会降低应用程序的速度，垃圾收集必须处理节点。
如果您需要在列表的任何一端添加或删除元素，但不需要随机访问，则ArrayDeque比LinkedList更快，但它需要Java 6。
LinkedList对于遍历列表然后在中间添加或删除元素有意义，但这是一种不寻常的情况。