何时在Java中通过ArrayList使用LinkedList？

摘要

ArrayList

用

ArrayDeque

在最好许多更多使用情况比

linkedList

。如果不确定，请从开始

ArrayList

。

linkedList

并且

ArrayList

是List接口的两种不同的实现。

linkedList

用双向链表实现它。ArrayList用动态调整大小的数组实现它。

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

对于

linkedList<E>

get(int index)

是O（n）（平均为n/4步），但是当或时为O（1）（在这种情况下，您也可以使用和）。的主要好处之一

index = 0index = list.size() - 1getFirst()getLast() linkedList<E>add(int index, E element)

是O（n）（平均n / 4步），但是当或时为O（1）（在这种情况下，您也可以使用和/）。的主要好处之一

index = 0index = list.size() - 1addFirst()addLast()add() linkedList<E>remove(int index)

是O（n）（平均为n/4步），但是当或时为O（1）（在这种情况下，您也可以使用和）。的主要好处之一

index = 0index = list.size() - 1removeFirst()removeLast() linkedList<E>

Iterator.remove()

是O（1）。的主要好处之一 linkedList

ListIterator.add(E element)

是O（1）。的主要好处之一

linkedList<E>

注意：许多操作平均需要

n / 4

步，在最佳情况下（例如，索引= 0）需要恒定的步数，在最坏情况下（列表的中间）需要

n / 2

步

对于

ArrayList<E>

注意：许多操作平均需要n / 2步，在最佳情况下（列表结尾）需要恒定的步数，在最坏情况下（列表开头）需要n步

linkedList<E>

允许使用迭代器进行固定时间的插入或删除，但只能顺序访问元素。换句话说，您可以向前或向后浏览列表，但是在列表中查找位置所花费的时间与列表的大小成正比。Javadoc说：“索引到列表中的操作将从开头或结尾遍历列表，以较近者为准”，因此，这些方法的平均值为O（n）（n / 4步），尽管O（1）为

index = 0

。

ArrayList<E>

另一方面，允许快速随机读取访问，因此您可以在固定时间内抓取任何元素。但是，从末端开始的任何地方添加或删除，都需要将后面的所有元素移开，以形成开口或填补空白。同样，如果添加的元素多于基础数组的容量，则会分配一个新数组（大小的1.5倍），并将旧数组复制到新数组中，因此在最坏的情况下将a添加

ArrayList

为O（n）情况，但平均保持不变。

因此，根据您打算执行的操作，您应该相应地选择实现。在任何一种List上进行迭代实际上都非常便宜。（从

ArrayList

技术上讲，迭代速度更快，但是除非您执行的操作确实对性能敏感，否则您不必为此担心-它们都是常量。）

linkedList

当您重复使用现有迭代器来插入和删除元素时，使用

generic

的主要好处。然后可以通过仅在本地更改列表在O（1）中完成这些操作。在阵列列表中，阵列的其余部分需要移动（即复制）。另一方面，在最坏的情况下

linkedList

以O（n）（n / 2步）的链接寻找均值，而在

ArrayList

所需位置可以数学计算并在O（1）中访问。

使用的另一个好处

linkedList

出现当您从列表的头部添加或删除，因为这些操作是O（1），而他们是为O（n）进行

ArrayList

。请注意，这

ArrayDeque

可能是

linkedList

添加和删除头部的好选择，但不是

List

。

另外，如果列表很大，请记住，内存使用情况也有所不同。a的每个元素

linkedList

都有更多开销，因为还存储了指向下一个和上一个元素的指针。

ArrayLists

没有这个开销。但是，

ArrayLists

无论是否实际添加了元素，占用的内存都应为该容量分配的内存。

的默认初始容量

ArrayList

很小（Java 1.4-1.8中为10）。但是由于底层实现是一个数组，所以如果添加很多元素，则必须调整数组的大小。为了避免在确定要添加很多元素时调整大小的高成本，请构建

ArrayList

具有较高初始容量的。