什么时候使用LinkedList的ArrayList？ [英] When to use LinkedList over ArrayList?

问题描述

我一直都是使用：

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

我使用接口作为 portability 的类型名称，我问这样的问题，我可以重做我的代码。

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 -versa？

推荐答案

TL; DR ArrayList 与 LinkedList 相比， ArrayDeque 更适合在更多的用例中。不确定 —只需从 ArrayList 开始。

TL;DR ArrayList with ArrayDeque are preferable in much more use-cases than LinkedList. 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） is O（n / 4） average


• add（E element） is O（1）


• E元素）是 O（n / 4）平均
  
      index = 0 < --- LinkedList< E> / code>


• remove（int index）是 O（n / 4） average


• Iterator.remove（）是 O（1） code> LinkedList< E>


• ListIterator.add（E element） > O（1） <--- LinkedList< E>

• 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） O（n / 2）最坏情况（列表中间）}

^{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） is O（n / 2） average


• remove（int index）是 O（n / 2） average


• 迭代器。 remove（） is O（n / 2） average


• ListIterator.add / code>是 O（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/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） list）}

^{Note: O(n/2) is average, O(1) best case (end of list), O(n) worst case (start of list)}

LinkedList< E> 允许恒定时间插入或移除迭代器，但只有元素的顺序访问。换句话说，您可以向前或向后移动列表，但在列表中查找位置需要与列表大小成正比的时间。 Javadoc说：索引到列表中的操作将从开始或结束（以较接近的一个）遍历列表，因此这些方法是 O（n / 4） on对于 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/4) 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.

做，你应该选择相应的实现。迭代任何一种列表几乎同样便宜。 （迭代在 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）中的链接，而在 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), whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).

使用<$当从列表的头部添加或删除时，由于这些操作是 O（1），而它们是 O（n），所以c> c> LinkedList ）> ArrayList 。请注意， ArrayDeque 可能是 LinkedList 的一个很好的替代，用于添加和删除，但不是 List 。

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 - 1.8的10）。但是由于底层实现是一个数组，如果添加了很多元素，则必须调整数组的大小。为了避免在你知道要添加大量元素时调整大小的高成本，请构造具有更高初始容量的 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.

值得注意的是， Vector 也实现了List接口，与 ArrayList 几乎相同。区别是Vector是同步的，所以它是线程安全的。因此，它也比 ArrayList 稍慢。所以据我所知，大多数Java程序员避免使用Vector来支持 ArrayList ，因为如果他们关心它们，它们可能会显式同步。

It's worth noting that Vector also implements the List interface and is almost identical toArrayList. The difference is that Vector is synchronized, so it is thread-safe. Because of this, it is also slightly slower than ArrayList. So as far as I understand, most Java programmers avoid Vector in favor of ArrayList since they will probably synchronize explicitly anyway if they care about that.

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