列表实现:与ArrayList和TreeList相比,LinkedList的性能真的很差吗?

这里的关键是在三个列表实现中插入/删除操作的复杂性。对于任意索引,arraylist有O(n)个插入/删除时间,但如果操作在列表末尾,则为O(1)。ArrayList还可以方便地访问任何位置的O(1)。LinkedList与O(n)类似,但对于列表两端的操作(开始和结束)为O(1),对于任意位置为O(n)访问。对于任何位置的所有操作,TreeList都具有O(logn)复杂性。

这清楚地表明,对于足够大的列表来说,对于任意位置的插入/删除来说,TreeList更快。但是,在afaik中,treelist被实现为一个二进制搜索树,它的o(logn)操作所关联的常量比arraylist的类似操作要大得多,后者仅仅是数组的包装器。这使得对于小列表来说,TreeList实际上更慢。此外,如果您所做的只是将元素添加到列表中,那么arraylist/linkedlist的O(1)性能显然更快。此外,插入/删除的数量通常比访问的数量要少得多,这会使arraylist在许多情况下总体上更快。LinkedList在列表两端的恒定时间插入/删除使它在实现诸如队列、堆栈和出局等数据结构方面更快。

在一天结束的时候,这完全取决于你到底需要一个列表来做什么。没有一刀切的解决方案。您必须选择最适合您工作的实现。

这是因为 data structures 在这些收藏后面。特雷斯特是 tree 允许相对快速的读取、插入、删除(所有O(log n))。数组列表使用 array 要存储数据,所以在插入或删除时,数组中的每个项都必须向上或向下移动(O(N)最坏情况)。数组也有固定的大小,因此如果它溢出当前数组的容量,则必须创建一个新的较大的数组(通常是最后一个数组的两倍大小,以使大小保持在最小值)。已使用LinkedList…一 linked list .链接列表通常引用列表中的第一个(有时是最后一个)元素。然后列表中的每个元素都有对列表中下一个元素(对于单独链接的列表)或下一个和上一个元素(对于双重链接的列表)的引用。因此,要访问一个特定的元素,必须在每个元素到达之前对其进行迭代(o(n)最坏的情况)。插入或删除特定元素时,必须找到插入或删除它们的位置,这需要时间(o(n)最坏情况)。然而,仅仅在开始或结束时添加另一个元素(o(1))的成本很低。

有整本书都是关于数据结构的,我建议您在什么时候使用它们,阅读一些更基本的。

因为链接列表必须逐节点导航才能到达列表中的任何位置(根据实现情况,保存前面和后面),所以数字太高是有意义的。

对于在大型LinkedList中添加/插入/删除,您将有大量的从节点跳到节点以到达正确的位置。

如果他们把适当尺寸的排列表从生长的痛苦开始,那就什么都不是了。如果阵列列表很小,生长的痛苦就不重要了。

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

您应该始终使用该接口,例如:list在声明变量和参数时,可以将“new linkedlist();”更改为“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<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).

,那么您一定会获得有史以来最好的任意插入性能。当然,这意味着您可以限制对迭代器()和listirator()的调用次数,以及迭代器在列表中的移动次数(例如,您只能对列表进行一次连续传递,以完成所需的所有插入)。这使得它的用例数量非常有限,但是它们是经常发生的用例。而LinkedList在其中的表现是为什么(将来会)保存在所有语言的容器集合中,而不仅仅是Java。

当然,上述所有操作都适用于所有其他操作,如get()、remove()等,也就是说,通过迭代器精心设计的访问将使所有操作都具有非常小的实际常量o(1)。当然,对于所有其他列表也可以这样说,即迭代器访问将加快所有列表的速度(不管有多轻微)。但不是arraylist的insert()和remove()-它们仍然是o(n)…不是TreeList的insert()和remove()-树平衡开销不是可以避免的…TreeList可能有更多的内存开销…你明白我的意思。综上所述,LinkedList是一种针对列表的小型高性能扫描操作。这是否是你需要的用例——只有你知道。

PSS。也就是说,我也因此而留下

想得出结论 摊余或忽略数组列表 成长的痛苦,并且没有 考虑插入和 中的项的移除时间 已经存在的LinkedList 位于。

对于ArrayList,因为它很少执行,所以基本上可以忽略不计。如果这实际上是一个问题,那么只需从更大的数组开始。

如果我有一个小的列表,那么使用LinkedList是有意义的,因为在这一点上收益微乎其微。如果列表很长,那么很明显树型列表更有意义。

如果我要对一个列表进行大量的随机访问,那么数组列表就更有意义了。

使用哪个容器实际上取决于您将如何使用它。没有一个容器是正确的,因为每个容器都有各自的优点和缺点,有了经验,你开始了解何时使用哪个容器。

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

如果需要从列表的任一端添加或删除元素,但不需要随机访问,则 ArrayDeque 虽然它需要Java 6,但它比链接表快。

LinkedList在列表中迭代,然后在中间添加或删除元素是有意义的,但这是一种不寻常的情况。