24

取自ApacheTreeList文档：

以下相对性能统计数据表明该类别：

             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几乎总是一个很好的替代品，尽管它确实使用了更多的内存。

我的问题是：

  • ArrayList add, insert, 和remove时代 粉碎 是 什么LinkedList? 一方面，我们是否应该期望现实世界的插入和删除案例非常有利于ArrayList?

  • 这难道TreeList只是给尊者的棺材钉了钉子LinkedList吗？

我很想得出结论，他们已经摊销或忽略了ArrayList成长的痛苦，并且没有考虑到LinkedList已经找到的项目的插入和移除时间。

4

6 回答 6

26

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

这清楚地表明，就在任意位置插入/删除而言，对于足够大的列表，TreeList 更快。但是 AFAIK，TreeLists 是作为二叉搜索树实现的，并且与它的 O(logn) 操作相关联的常量比 ArrayLists 的类似操作要大得多，ArrayLists 只是数组的包装器。这使得 TreeList 实际上对于小型列表更慢。此外，如果您所做的只是将元素附加到列表中，那么 ArrayList/LinkedList 的 O(1) 性能显然更快。此外，插入/删除的数量通常比访问的数量少得多，这往往会使 ArrayList 在许多情况下总体上更快。LinkedList 在列表两端的恒定时间插入/删除使其在实现队列、堆栈和双端队列等数据结构时更快。

归根结底，这完全取决于您究竟需要一个列表来做什么。没有一种万能的解决方案。您必须选择最适合您工作的实施。

于 2009-11-11T05:40:53.417 回答
3

这是由于这些集合背后的数据结构。TreeList 是一棵树，它允许相对快速的读取、插入、删除（所有 O(log n)）。ArrayList 使用一个数组来存储数据，因此当您插入或删除时，数组中的每个项目都必须向上或向下移动（O(n) 最坏情况）。数组也有一个固定的大小，所以如果它溢出了当前数组的容量，就必须创建一个新的、更大的（通常是最后一个数组的两倍，以将调整大小保持在最低限度）。LinkedList used... 一个链表. 链表通常引用列表中的第一个（有时是最后一个）元素。然后列表中的每个元素对列表中的下一个元素（对于单链表）或下一个和前一个元素（对于双链表）都有一个引用。正因为如此，要访问一个特定的元素，你必须在它到达之前遍历每个元素（O(n) 最坏的情况）。插入或删除特定元素时，您必须找到插入或删除它们的位置，这需要时间（O(n) 最坏情况）。然而，简单地在开头或结尾添加另一个元素（O（1））几乎没有成本。

有很多关于数据结构以及何时使用它们的书籍，我建议阅读更基础的书籍。

于 2009-11-11T05:27:01.403 回答
2

在这里回答的每一个人都是正确的。他们的想法都是正确的，这在很大程度上取决于您的使用模式，即没有一刀切的列表。但是在我写这篇文章的时候，他们都忘了提到（或者我是草率的读者）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<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.

或者

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 中已经定位的项目的插入和删除时间。

于 2009-11-11T06:51:31.300 回答
2

因为链表必须逐个节点导航才能到达列表中的任何位置（根据实现情况保存前面和可能的后面），所以数字如此之高是有道理的。

对于大型 LinkedList 中的添加/插入/删除，您需要从一个节点跳到另一个节点才能到达正确的位置。

如果他们制作了适当大小的 ArrayList 以开始成长的烦恼将一事无成。如果 ArrayList 很小，那么成长的痛苦并不重要。

对于 LinkedList，如果操作都在列表的前面，那么如果它们在末尾，则影响要小得多。

您应该做的是始终使用接口，例如：声明变量和参数时的列表，然后您可以更改“new LinkedList();” 到“新的 ArrayList();” 并分析代码以查看它在您的特定代码中的执行情况。

由于不必从一个节点跳到另一个节点的速度，我总是默认使用 ArrayList 而不是 LinkedList。

我相信树列表会比两者都快得多（即使不看代码）。树的设计速度很快。

于 2009-11-11T05:27:08.907 回答
1

对于 ArrayList，由于它很少执行，因此您基本上可以忽略该成本。如果它确实是一个问题，那么只需将数组变大即可。

如果我有一个小列表，那么使用 LinkedList 是有意义的，因为此时的好处很小。如果列表很长，那么显然 TreeList 更有意义。

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

使用哪个容器实际上取决于您将使用它做什么。没有一个正确的容器，因为每个容器都有其优点和缺点，并且随着经验，您开始了解何时使用哪个容器。

于 2009-11-11T05:32:12.327 回答
1

请注意，ArrayList 通常比 LinkedList 快，即使您的代码仅调用对两者而言都是恒定时间的方法。例如， ArrayList.add() 只需复制单个变量并在不需要调整大小时增加一个计数器，而 LinkedList.add() 还必须创建一个节点并设置多个指针。此外，LinkedList 节点需要更多内存，这会减慢您的应用程序，并且垃圾收集必须处理这些节点。

如果您需要从列表的任一端添加或删除元素，但不需要随机访问，则ArrayDeque比 LinkedList 更快，尽管它需要 Java 6。

LinkedList 对于遍历列表然后在中间添加或删除元素是有意义的，但这是一种不寻常的情况。

于 2009-11-18T07:38:44.690 回答