列表实现:LinkedList与ArrayList和TreeList相比是否真的表现不佳？

Question

取自Apache TreeListdoc:

以下相对性能统计数据表示此类:

             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已经找到的物品的插入和移除时间.

Answer 1

这里的关键是三个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.没有一个通用的解决方案.您必须选择最适合您工作的实施方案.