什么时候在 Java 中使用 LinkedList 而不是 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 用于 ArrayList 反之亦然?

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

推荐答案

Summary ArrayList 和 ArrayDeque 在很多 比 LinkedList 更多的用例.如果您不确定 - 只需从 ArrayList 开始.

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

TLDR，在 ArrayList 中访问一个元素需要常数时间 [O(1)]，而添加一个元素需要 O(n) 时间 [最坏情况].在 LinkedList 中，添加元素需要 O(n) 时间，访问也需要 O(n) 时间，但 LinkedList 使用的内存比 ArrayList 多.

TLDR, in ArrayList accessing an element takes constant time [O(1)] and adding an element takes O(n) time [worst case]. In LinkedList adding an element takes O(n) time and accessing also takes O(n) time but LinkedList uses more memory than 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

• get(int index) 是 O(n)(平均有 n/4 步)，但是 O(1) 当 index = 0 或 index = list.size() - 1 (在这种情况下，你也可以使用 getFirst() 和 getLast()). LinkedList
的主要好处之一
• add(int index, E element) 是 O(n)(平均有 n/4 步)，但是 O(1) 当 index = 0 或 index = list.size() - 1 (在这种情况下，你也可以使用 addFirst() 和 addLast()/add()). LinkedList
的主要好处之一
• remove(int index) 是 O(n)(平均有 n/4 步)，但是 O(1) 当 index = 0 或 index = list.size() - 1 (在这种情况下，你也可以使用 removeFirst() 和 removeLast()). LinkedList
的主要好处之一
• Iterator.remove() 是 O(1). LinkedList
的主要好处之一
• ListIterator.add(E element) 是 O(1). LinkedList
的主要好处之一

• get(int index) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use getFirst() and getLast()). One of the main benefits of LinkedList<E>
• add(int index, E element) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use addFirst() and addLast()/add()). One of the main benefits of LinkedList<E>
• remove(int index) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use removeFirst() and removeLast()). One of the main benefits of LinkedList<E>
• Iterator.remove() is O(1). One of the main benefits of LinkedList<E>
• ListIterator.add(E element) is O(1). One of the main benefits of LinkedList<E>

^{注意:许多操作平均需要 n/4 步，在最佳情况下需要 恒定 步数(例如 index = 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

• get(int index) 是 O(1).的主要好处 ArrayList
• 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 element) 是 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 允许使用迭代器进行恒定时间插入或删除，但只能对元素进行顺序访问.换句话说，您可以向前或向后遍历列表，但在列表中查找位置所需的时间与列表的大小成正比.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 另一方面，允许快速随机读取访问，因此您可以在恒定时间内获取任何元素.但是，除了结尾之外的任何地方添加或删除都需要将后面的所有元素都移过来，以形成开口或填补空白.此外，如果添加的元素多于底层数组的容量，则会分配一个新数组(大小的 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)，而它们是 ArrayList 的 >O(n).请注意，ArrayDeque 可能是 LinkedList 的一个很好的替代方案，用于从头部添加和删除，但它不是 List.

Another benefit of using a LinkedList arises 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.

如果从数据结构的角度来理解这两种结构，LinkedList基本上就是一个包含头节点的顺序数据结构.Node 是两个组件的包装器:一个 T 类型的值 [通过泛型接受] 和另一个对链接到它的 Node 的引用.因此，我们可以断言它是一个递归数据结构(一个节点包含另一个节点，该节点具有另一个节点等等......).如上所述，在 LinkedList 中添加元素需要线性时间.

If the data structures perspective is used to understand the two structures, a LinkedList is basically a sequential data structure which contains a head Node. The Node is a wrapper for two components : a value of type T [accepted through generics] and another reference to the Node linked to it. So, we can assert it is a recursive data structure (a Node contains another Node which has another Node and so on...). Addition of elements takes linear time in LinkedList as stated above.

一个ArrayList，是一个可增长的数组.它就像一个常规数组.在幕后，当一个元素被添加到索引 i 时，它会创建另一个大小比先前大小大 1 的数组(因此，通常，当 n 个元素要添加到 ArrayList 时，大小为先前大小的新数组加上 n 被创建).然后将元素从前一个数组复制到新数组，并且要添加的元素也放置在指定的索引处.

An ArrayList, is a growable array. It is just like a regular array. Under the hood, when an element is added at index i, it creates another array with a size which is 1 greater than previous size (So in general, when n elements are to be added to an ArrayList, a new array of size previous size plus n is created). The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices.

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