何时使用LinkedList的过的ArrayList？ [英] When to use LinkedList over ArrayList?

问题描述

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

I've always been one to simply use:

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

我使用接口作为类型名的可移植性的，所以，当我问这样的问题，这些我可以返工我的code。

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 在的ArrayList 使用，反之亦然？

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

推荐答案

TL; DR 的ArrayList 与 ArrayDeque 是多的更多使用情况preferable比的LinkedList 。不知道＆NBSP;＆MDASH;刚开始用的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.

有关<一个href=\"http://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html\"><$c$c>LinkedList<E>

• GET（INT指数）是的 O（N）的


• 添加（E元素）是的 O（1）的


• 添加（INT指数，E元素）是的 O（N）的


• 删除（INT指数）是的 O（N）的


• Iterator.remove（）是的 O（1）的＆LT; --- 的LinkedList＆LT的主要好处; E＆GT ;


• ListIterator.add（E元素）是的 O（1）的＆LT; --- 的LinkedList＆LT的主要好处; E＆GT;

• get(int index) is O(n)
• add(E element) is O(1)
• add(int index, E element) is O(n)
• remove(int index) is O(n)
• Iterator.remove() is O(1) <--- main benefit of LinkedList<E>
• ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>

有关<一个href=\"http://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html\"><$c$c>ArrayList<E>

• GET（INT指数）是的 O（1）的＆LT; --- 的ArrayList＆LT的主要好处; E＆GT ;


• 添加（E元素）是的 O（1）的摊销，但的 O（N）的最坏情况因为数组必须调整大小和复制


• 添加（INT指数，E元素）是O（n - 指数）摊销，但的 O（N）的最坏情况（如以上）


• 删除（INT指数）是O（n - 指数）（即去掉最后是的 O（1）的）


• Iterator.remove（）是O（n - 指数）


• ListIterator.add（E元素）是O（n - 指数）

• 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 - index) amortized, but O(n) worst-case (as above)
• remove(int index) is O(n - index) (i.e. removing last is O(1))
• Iterator.remove() is O(n - index)
• ListIterator.add(E element) is O(n - index)

的LinkedList＆LT; E＆GT; 允许固定时间插入或清除的使用迭代器的，但只有元素的顺序访问。换句话说，你可以向前或向后行走之列，但发现在列表中的位置需要时间成正比列表的大小。

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.

的ArrayList＆LT; E＆GT; ，从另一方面，允许快速随机读取访问，所以你可以抢在常数时间的任何元素。但是，添加或从任何地方卸下但最终要求对所有转移后的元素，无论是做一个开口，或填补了国内空白。此外，如果添加比底层阵列的容量更多的元素，新的数组（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 出现，当您重新利用现有的迭代器插入和删除元素的主要好处。这些操作然后可以在 0 的通过局部改变只列表（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).

另外，如果你有大的列表，请记住，内存使用量也不同。因为指针下和previous元素的的LinkedList 有更多的开销每个元素也存储。 的ArrayList 不具备这方面的开销。然而，的ArrayList 作为分配的容量，无论实际已添加的元素占据尽可能多的内存。

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 的默认初始容量为pretty小（10从Java 1.4 - 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.

这是值得注意的是，矢量也实现了List接口，几乎等同于的ArrayList 。所不同的是载体是同步的，所以它是线程安全的。正因为如此，它也比的ArrayList 稍微慢一些。因此，作为据我所知，大多数Java程序员避免矢量赞成的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屋！