问题

我一直都是使用:

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

我使用接口作为可移植性的类型名称,所以当我提出这样的问题,我可以重做我的代码.

LinkedList 何时应用于 ArrayList ,反之亦然?



解决方法

ArrayList 相比,在个更多的用例中</>> </> .不确定 - 只需从 ArrayList 开始.


LinkedList ArrayList 是List接口的两个不同实现. LinkedList 使用双向链表实现它. ArrayList 使用动态调整大小的数组来实现它.

与标准链接列表和数组操作一样,各种方法将具有不同的算法运行时.

对于 LinkedList&lt; E&gt;

  • get(int index) is O(n/4) average
  • add(E element) is O(1)
  • add(int index, E element) is O(n/4) average
         but O(1) when index = 0 <--- main benefit of LinkedList<E>
  • remove(int index) is O(n/4) average
  • Iterator.remove() is O(1) <--- main benefit of LinkedList<E>
  • ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>

注意: O(n / 4)是平均值, O(1)最坏情况(列表中间)

对于 ArrayList&lt; E&gt;

  • get(int index) is O(1) <--- main benefit of ArrayList<E>
  • add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
  • add(int index, E element) is O(n/2) average
  • remove(int index) is O(n/2) average
  • Iterator.remove() is O(n/2) average
  • ListIterator.add(E element) is O(n/2) average

注意:最好的情况(列表结尾), O(n) 最差情况(列表的开始)

LinkedList&lt; E&gt; 允许使用迭代器进行常时插入或移除,但只允许元素的顺序存取.换句话说,您可以向前或向后移动列表,但在列表中查找位置所需的时间与列表的大小成正比. Javadoc说"索引到列表中的操作将从开始或结束(以较接近的方式")遍历列表,因此这些方法是 O(n / 4)平均,但 index = 0 O(1)允许快速随机读取访问,因此您可以在恒定时间内获取任何元素.但是,除了端部之外的任何地方添加或移除,需要将所有后面的元件移位,以形成开口或填充间隙.另外,如果添加的元素多于底层数组的容量,则会分配一个新数组(大小的1.5倍),并将旧数组复制到新数组,因此添加到 ArrayList 在最坏的情况下是 O(n),但是平均是常数

因此,根据您打算执行的操作,您应该相应地选择实现.迭代任何一种列表几乎同样便宜. (迭代一个 ArrayList 在技术上更快,但除非你做的事情真的对性能敏感,你不应该担心 - 他们都是常数.)

当您重复使用现有的迭代器来插入和删除元素时,使用 LinkedList 的主要好处.这些操作然后可以在 O(1)中通过仅在本地更改列表来完成.在数组列表中,数组的其余部分需要移动(即复制).另一方面,在 LinkedList 中寻找在 O(n)中的链接,而在 ArrayList 中,可以计算期望的位置在数学上并在 O(1)中访问.

当您从列表的头部添加或删除时,使用 LinkedList 会产生另一个好处,因为这些操作是 O(1),而 > O(n)用于 ArrayList .注意, ArrayDeque 可能是用于添加和删除头的 LinkedList 的一个很好的替代,但它不是一个 List .

此外,如果您有大量列表,请记住内存使用情况也不同. LinkedList 的每个元素具有更多的开销,因为还存储了指向下一个和前一个元素的指针. ArrayLists 没有这个开销.但是, ArrayLists 占用与为容量分配的内存一样多的内存,无论元素是否实际已添加.

ArrayList 的默认初始容量相当小(来自Java 1.4 - 1.8的初始容量为10).但由于底层实现是一个数组,如果添加了很多元素,则必须调整数组的大小.为了避免在你知道要添加大量元素时调整大小的高成本,请构造具有更高初始容量的 ArrayList .




相关问题推荐