列表实现：LinkedList真的表现如此糟糕，而ArrayList和TreeList？ [英] List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

问题描述

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

我的问题是：

• ArrayList 添加，
  插入 times crushing
  LinkedList ？如果我们期望，对于
  一，真实世界的插入和删除情况
  大大优惠 ArrayList ？




• 这个 TreeList 只是把指甲放在虔诚的 LinkedList ？ / p>

我试图推断他们已经摊还或忽略 ArrayList 并且没有考虑已经找到的 LinkedList 中的项目的插入和移除时间。

解决方案

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

这清楚地表明，对于足够大的列表，TreeList更快，只要在任意位置插入/删除关心。但是AFAIK，TreeLists被实现为二叉搜索树，并且与使用ArrayLists的类似操作相比，它具有比其O（logn）操作更大的常量，ArrayLists仅仅是数组的包装器。这使得TreeList实际上对于小列表更慢。另外，如果你所做的是将一个元素添加到一个List中，ArrayList / LinkedList的O（1）性能明显更快。此外，通常插入/删除的数量比访问的数量少得多，这往往使ArrayList在许多情况下更快。 LinkedList在List的任一端的常量时间插入/删除使得在实现诸如Queues，Stacks和Deques等数据结构时更快。

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

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

It goes on to say:

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

My questions are:

• 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?

• Does this TreeList simply put the nail in the coffin of the venerable 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.

解决方案

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.

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.

这篇关于列表实现：LinkedList真的表现如此糟糕，而ArrayList和TreeList？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！