列表实现：LinkedList真的表现如此糟糕与ArrayList和TreeList？

Question

从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尚未考虑插入和移除时间的项目。

Answer 1

这里的关键是三个List实现中插入/删除操作的复杂性。 ArrayList对于任意索引具有O（n）的插入/删除时间，但如果操作位于列表的末尾，则为O（1）。 ArrayList对任何位置都有O（1）访问的便利。 LinkedList类似于O（n），但对于任意位置的列表（开始和结束）和O（n）访问的任一端的操作，O（1）是O（1）。 TreeList对于任何位置的所有操作都具有O（logn）复杂性。

这清楚地表明TreeList对于足够大的列表来说更快，只要在任意位置上进行插入/删除。但是AFAIK，TreeLists被实现为一个二叉搜索树，并且具有与其O（logn）操作相关的更大的常量，而ArrayLists的相似操作仅仅是数组的封装。这使得TreeList对于小列表实际上更慢。另外，如果你所做的只是把元素附加到List中，那么ArrayList/LinkedList的O（1）性能显然更快。而且，插入/删除的次数通常比访问次数少得多，这在很多情况下倾向于使ArrayList总体上更快。 LinkedList在列表两端的常量时间插入/删除使得实现Queues，Stacks和Deques等数据结构的速度更快。

在一天结束时，这一切都取决于你需要一个列表。没有一种万能的解决方案。您必须选择最适合您工作的实施。

Answer 2

这是由于这些集合背后的data structures。 TreeList是tree，它允许相对较快的读取，插入，删除（全O（log n））。 ArrayList使用array来存储数据，所以当您插入或删除数据时，阵列中的每个项目都必须向上或向下移动（最坏情况是O（n））。数组的大小也是固定的，所以如果它溢出当前数组的容量，则必须创建一个新的较大的数组（通常是最后一个数组的两倍，以保持最小大小）。 LinkedList使用...一个linked list。链表通常会引用列表中的第一个（有时是最后一个）元素。然后，列表中的每个元素都会引用列表中的下一个元素（对于单链表）或下一个元素和上一个元素（对于双链表）。因此，要访问某个特定元素，必须遍历每个元素才能到达那里（O（n）最坏的情况）。当插入或删除特定元素时，您必须找到插入或移除特定元素的位置，这需要时间（O（n）最差的情况）。然而，简单地将另一个元素添加到开始或结束（O（1））的成本非常低。

有关于数据结构的完整书籍，以及何时使用它们，我建议您阅读更基本的书籍。

Answer 3

因为链表必须逐节点浏览以获取列表中的任何位置（根据实现情况保存前端或后端），因此这些数字非常高。

为了在一个大的LinkedList中添加/插入/删除，你需要从节点到节点进行大量的跳转才能到达正确的位置。

如果他们让适当大小的ArrayList开始，那么成长的痛苦将不会是什么。如果ArrayList很小，那么成长的痛苦并不重要。

对于LinkedList，如果操作都在列表的前面，那么如果它们在最后，它的影响会小得多。

你应该做的是始终使用接口，例如：List当声明变量和参数时，你可以改变“new LinkedList（）;”到“new ArrayList（）;”并剖析代码以了解它在特定代码中的表现。

由于无需从节点跳到节点，我总是默认为ArrayList而不是LinkedList。

我相信树列表将比两者都快很多（即使不查看代码）。树被设计得很快。

Answer 4

对于ArrayList，由于它不经常进行，所以基本上可以忽略该成本。如果它实际上是一个问题，那么只需将数组放大就可以开始。

如果我有一个小列表，那么一个LinkedList是有意义的，因为在这一点上有最小的好处。如果列表将会很长，那么显然TreeList更有意义。

如果我要对列表进行大量的随机访问，那么ArrayList更有意义。

要使用哪个容器取决于您将使用哪种容器。没有一个正确的容器，因为每个容器都有自己的优势和弱点，并且有了经验，你就开始了解何时使用哪个容器。

Answer 5

每个在这里回答的人都是正确的。他们都认为他们的观点是正确的，这很大程度上取决于你的使用模式，即没有一个通用的列表。但是在写作的那一刻，当LinkedList处于最佳状态时，他们都忘记提及（或者说，或者我是草率的阅读器）用例：迭代器定位插入。这意味着，如果你正在做不只是

LinkedList::add(int index, E element) 
      Inserts the specified element at the specified position in this list. 

这似乎是他们曾经获得的统计方法，但

iterator.insert(E element) 

通过两种

public abstract ListIterator<E> listIterator(int index) 
Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list. 

获得 iterator

或

public Iterator<E> 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的是已经被定位为 。

Answer 6

请注意，ArrayList通常比LinkedList快，即使您的代码只调用两个常量时间的方法。例如，当不需要调整大小时，ArrayList.add（）简化拷贝单个变量并增加计数器，而LinkedList.add（）也必须创建节点并设置多个指针。另外，LinkedList节点需要更多内存，这会减慢应用程序的运行速度，垃圾收集必须处理节点。

如果需要添加或删除列表中的任一端的元素，但不需要随机访问，一个ArrayDeque率比在LinkedList快，但它需要Java 6

一个LinkedList意义用于迭代整个列表，然后添加或删除中间的元素，但这是一种不寻常的情况。