List实现：不LinkedList的真正执行如此糟糕与ArrayList和的TreeList？ [英] List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

问题描述

从 href=\"http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/list/TreeList.html\"相对=nofollow> Apache的的TreeList DOC ：

  

下面的相对性能统计数据均显示出这
  类：

 获得加插入删除迭代
 3的TreeList 5 1 2 1
 ArrayList的1 1 40 1 40
 LinkedList的5800 1 350 325 2
 

它接着说：

  

的LinkedList 很少实现的一个不错的选择。 的TreeList 几乎总是一个很好的替代，尽管它确实使用sligtly更多的内存。

我的问题是：

• 什么是与的ArrayList 添加，
  插入和删除次破碎
  的LinkedList ？我们应该期待，对于
  之一，即现实世界插入和去除的情况下
  大大有利于的ArrayList ？




• 这是否的TreeList 简单地把钉子在棺材古老的LinkedList ？

我倾向于认为他们已经摊销或忽略的ArrayList 的阵痛，并没有考虑到插入和移除时间在一个项目的LinkedList 一个已经定位。

解决方案

这里的关键是插入的复杂性/三个List实现删除操作。的ArrayList为O（n）的插入/删除任意指数倍，但它是O（1）如果操作是在列表的末尾。 ArrayList中也有O（1）在任何地点访问的便利性。 LinkedList的是同样为O（n），但为O（1）操作在列表的两端（开始和结束），O代表​​任意位置（n）的访问。的TreeList对所有操作O（LOGN）的复杂性在任何位置。

这清楚地表明的TreeList是足够大名单更快尽可能插入/删除任意位置有关。但据我所知，TreeLists被实现为二叉搜索树，与它的O（LOGN）比的ArrayList这仅仅是围绕着一个阵列封装类似的操作操作有关一个更大的常量。这使得为​​的TreeList小列表实际上慢。另外，如果你正在做的是附加元素放入一个List，ArrayList中/链表的O（1）表现显然更快。此外，经常插入/删除的数量比访问的数字，这往往使ArrayList的许多情况下，更快的整体少得多。 LinkedList的常数时间插入/删除在列表的两端使得它更快的执行就像队列，栈和双端数据结构。

在一天结束的时候，这一切都取决于正是你需要一个列表。没有一个放之四海而皆准的解决办法。你必须选择最适合你的工作的落实。

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.

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