何时在ArrayList上使用LinkedList?

问题:

我一直是一个简单的使用:

List<String> names = new ArrayList<String>();

我使用界面作为portability的类型名称,所以当我提出这样的问题时,我可以重写我的代码。
LinkedList何时应用ArrayList,反之亦然?

回答:

 TL; DR ArrayListArrayDequemuch更多的使用案例优于LinkedList。不确定xa0-从ArrayList开始
 LinkedListArrayList是List接口的两个不同实现。 LinkedList用双向链表实现。 ArrayList使用动态重新调整大小的数组实现。
与标准链表和阵列操作一样,各种方法将具有不同的算法运行时。
对于LinkedList<E>

  •  get(int index)O(n/4)的平均值
  •  add(E element)O(1)
  •  add(int index, E element)是平均
    O(n/4)
    xa0 xa0 xa0but O(1)index = 0 <--- LinkedList<E>的主要好处
  •  remove(int index)O(n/4)的平均值
  •  Iterator.remove()O(1) <--- LinkedList<E>的主要优点
  •  ListIterator.add(E element)O(1) <--- LinkedList<E>的主要优点

 Note: O(n/4) is average, O(1) best case (e.g. index = 0), O(n/2) worst case (middle of list)
对于ArrayList<E>

  •  get(int index)O(1) <--- ArrayList<E>的主要优点
  •  add(E element)O(1)摊销,但O(n)最坏的情况是因为数组必须调整大小并复制
  •  add(int index, E element)O(n/2)的平均值
  •  remove(int index)O(n/2)的平均值
  •  Iterator.remove()O(n/2)的平均值
  •  ListIterator.add(E element)O(n/2)的平均值

 Note: O(n/2) is average, O(1) best case (end of list), O(n) worst case (start of list)
 LinkedList<E>允许持续时间插入或删除using iterators,但只能顺序访问元素。换句话说,您可以向前或向后移动列表,但是在列表中找到位置需要与列表的大小成正比。 Javadoc说“operations that index into the list will traverse the list from the beginning or the end, whichever is closer”,所以这些方法平均O(n/4)index = 0 index = 0
 另一方面,ArrayList<E>允许快速随机读取访问,因此您可以在不间断的时间内获取任何元素。但是,从任何地方添加或删除,但最终需要将所有后面的元素都移开,以打开或弥补差距。另外,如果添加的元素多于底层数组的容量,则会分配一个新数组(1.5倍大小),并将旧数组复制到新的数组,因此添加到ArrayListO(n)最坏的情况,但平均不变。
因此,根据您打算做的操作,您应该相应地选择实施。迭代任何一种列表实际上同样便宜。 (迭代超过ArrayList在技术上更快,但除非你做一些真正的性能敏感的事情,否则你不必担心这些 – 它们都是常量。)
当您重新使用现有的迭代器插入和删除元素时,会出现使用LinkedList的主要优点。然后可以在O(1)中通过仅在本地更改列表来完成这些操作。在数组列表中,数组的其余部分需要为moved(即复制)。另一方面,寻求LinkedList意味着在最坏情况下遵循O(n/2)中的链接,而在ArrayList中,所需的位置可以在数学上计算并在O(1)中访问
当您从列表的头部添加或删除时,会出现使用LinkedList的另一个好处,因为这些操作为O(1),而ArrayListO(n)。请注意,ArrayDeque可能是添加和删除头部LinkedList的一个很好的替代方法,但它不是List
另外,如果您有大列表,请记住,内存使用情况也不尽相同。 LinkedList的每个元素都有更多的开销,因为还存储了指向下一个和前一个元素的指针。 ArrayLists没有这个开销。然而,ArrayLists占用的容量占用的内存多少,无论是否实际添加了元素。
ArrayList的默认初始容量非常小(来自Java 1.4 – 1.8中的10个)。但是由于底层实现是一个数组,所以如果添加了很多元素,则必须调整数组的大小。为了避免在您知道要添加大量元素时调整大小的高成本,请构建具有较高初始容量的ArrayList

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: When to use LinkedList over ArrayList?

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

84 − 75 =