列表实现:与 ArrayList 和 TreeList 相比，LinkedList 的性能真的那么差吗? [英] List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

问题描述

取自 Apache TreeList 文档:

Taken from the Apache TreeList doc:

以下相对性能统计数据表明了这一点班级:

The following relative performance statistics are indicative of this class:

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

LinkedList is rarely a good choice of implementation. TreeList is almost always a good replacement for it, although it does use sligtly more memory.

我的问题是:

• ArrayList add 有什么用，insert 和 remove 次粉碎LinkedList?我们是否应该期待，对于一、真实世界的插拔案例非常喜欢ArrayList?

• What is with the ArrayList add, insert, and remove times crushing LinkedList? Should we expect, for one, that real-world insertion and removal cases greatly favor ArrayList?

这个TreeList是不是简单地把钉子钉在了可敬的LinkedList的棺材里?

Does this TreeList simply put the nail in the coffin of the venerable LinkedList?

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

I am tempted to conclude they have amortized or ignored ArrayList's growing pains, and have not taken into consideration the insertion and removal times for an item in a LinkedList that has already been located.

推荐答案

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

The key thing here is the complexity of insert/delete operations in the three List implementations. ArrayList has O(n) insert/delete times for arbitrary indices, but it is O(1) if the operation is at the end of the list. ArrayList also has the convenience of O(1) access for any location. LinkedList is similarly O(n), but is O(1) for operations at either end of the List (start and end) and O(n) access for arbitrary positions. TreeList has O(logn) complexity for all operations at any position.

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

This clearly shows that TreeList is faster for large enough Lists as far as insert/deletes in arbitrary positions are concerned. But AFAIK, TreeLists are implemented as a binary search tree, and has a much bigger constant associated with its O(logn) operations than similar operations with ArrayLists which are simply wrappers around an array. This makes TreeList actually slower for small Lists. Also, if all you are doing is appending element into a List, the O(1) performance of ArrayList/LinkedList is clearly faster. Moreover, often the number of insert/deletes are much fewer than the numbers of accesses, which tends to make ArrayList faster overall for many cases. LinkedList's constant time insert/delete at the either end of the List makes it much faster at implementing data structures like Queues, Stacks and Deques.

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

At the end of the day, it all depends on what exactly you need a List for. There isn't a one-size-fits-all solution. You have to select the implementation most suitable for your job.

这篇关于列表实现:与 ArrayList 和 TreeList 相比，LinkedList 的性能真的那么差吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！