何时在Java中使用LinkedList over ArrayList？ [英] When to use LinkedList over ArrayList in Java?

问题描述

我一直只是一个人使用：

I've always been one to simply use:

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

我使用接口作为可移植性的类型名称，这样当我问这些问题我可以修改我的代码。

I use the interface as the type name for portability, so that when I ask questions such as these I can rework my code.

什么时候应该 LinkedList util / ArrayList.htmlrel =noreferrer> ArrayList ，反之亦然？

When should LinkedList be used over ArrayList and vice-versa?

推荐答案

摘要 ArrayList 包含 ArrayDeque 多比 LinkedList 更多的用例。如果你不确定 —只需从 ArrayList 开始。

Summary ArrayList with ArrayDeque are preferable in much more use-cases than LinkedList. If you're not sure — just start with ArrayList.

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

LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.

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

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

对于 LinkedList< E>

• get（int index） O（n）（平均 n / 4 步骤）


• add（E element） O（1）


• add（int index，E element） O（n）（平均 n / 4 步骤） ，
  但 O（1）当 index = 0 < --- 的主要好处> LinkedList< E>


• remove（int index） O（n） （平均 n / 4 步骤）


• Iterator.remove（）是 O （1）。 < --- 的主要好处LinkedList< E>


• ListIterator.add（E element）是 O（1）这是 LinkedList< E>
$ b $的主要好处之一b

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

^{注意：许多操作平均需要 n / 4 步骤，常量最坏情况下的步骤（例如索引= 0），最坏情况下的 n / 2 步骤（列表中间）}

^{Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. index = 0), and n/2 steps in 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）（带 n / 2 平均步数）


• remove（int index）是 O（n）（平均 n / 2 步骤）


• Iterator。 remove（）是 O（n）（平均 n / 2 步骤）


• ListIterator.add（E元素）是 O（n）（平均 n / 2 步骤）

• 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) (with n/2 steps on average)
• remove(int index) is O(n) (with n/2 steps on average)
• Iterator.remove() is O(n) (with n/2 steps on average)
• ListIterator.add(E element) is O(n) (with n/2 steps on average)

^{注意：许多操作平均需要 n / 2 步骤，常量最佳情况下的步骤数（列表末尾），最坏情况下的 n 步骤（列表开头）}

^{Note: Many of the operations need n/2 steps on average, constant number of steps in the best case (end of list), n steps in the worst case (start of list)}

LinkedList< E> 允许使用迭代器进行常量时间插入或删除，但只允许顺序访问元素。换句话说，您可以向前或向后遍历列表，但在列表中查找位置需要的时间与列表的大小成比例。 Javadoc说索引到列表中的操作将从开头或结尾遍历列表，以较近者为准，因此这些方法是 O（n）（ n / 4 步骤，但 O（1） index = 0 。

LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n) (n/4 steps) on average, though O(1) for index = 0.

ArrayList< E> ，另一方面，允许快速随机读取访问，因此您可以在恒定时间内获取任何元素。但是，除了末端之外的任何地方添加或移除都需要将所有后面的元素移位，以便打开或填补空白。此外，如果添加的元素多于底层数组的容量，则会分配一个新数组（大小的1.5倍），并将旧数组复制到新数组，因此添加到 ArrayList 在最坏的情况下是 O（n）但平均是恒定的。

ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

因此，取决于您打算的操作你应该相应地选择实现。迭代任何一种List实际上同样便宜。 （迭代 ArrayList 在技术上更快，但除非你做的事情对性能非常敏感，否则你不应该担心这一点 - 它们都是常量。）

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

当您重用现有的迭代器来插入和删除元素时，会出现使用 LinkedList 的主要好处。然后，可以通过仅在本地更改列表，在 O（1）中完成这些操作。在数组列表中，数组的其余部分需要移动（即复制）。另一方面，在 LinkedList 中寻找意味着遵循 O（n）（ n / 2 步骤中的链接）对于最坏的情况，而在 ArrayList 中，可以在数学上计算所需位置并在 O（1）中访问。

The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n) (n/2 steps) for worst case, whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).

当您从列表的头部添加或删除时，会出现使用 LinkedList 的另一个好处，因为这些操作是 O（ 1），而 O（n） ArrayList 。请注意， ArrayDeque 可能是 LinkedList 的一个很好的替代品，用于添加和删除头部，但它不是列表。

Another benefit of using a LinkedList arise when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList. Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head, but it is not a List.

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

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

ArrayList 的默认初始容量非常小（Java 1.4中的10个 - 1.8）。但由于底层实现是一个数组，因此如果添加大量元素，则必须调整数组大小。为了避免在您知道要添加大量元素时调整大小的高成本，请构建具有更高初始容量的 ArrayList 。

The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.

这篇关于何时在Java中使用LinkedList over ArrayList？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！