什么时候在 Java 中使用 LinkedList 而不是 ArrayList？

When to use LinkedList over ArrayList in Java?

提问by sdellysse

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.

我使用接口作为可移植性的类型名称，这样当我提出诸如此类的问题时，我可以重新编写我的代码。

When should LinkedListbe used over ArrayListand vice-versa?

什么时候应该LinkedList再次使用，ArrayList反之亦然？

采纳答案by Jonathan Tran

SummaryArrayListwith ArrayDequeare preferable in manymore use-cases than LinkedList. If you're not sure — just start with ArrayList.

摘要ArrayList用ArrayDeque在最好许多更多使用情况比LinkedList。如果您不确定 - 只需从ArrayList.

---

---

LinkedListand ArrayListare two different implementations of the List interface. LinkedListimplements it with a doubly-linked list. ArrayListimplements it with a dynamically re-sizing array.

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

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

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

For LinkedList<E>

为了 LinkedList<E>

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

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

^{Note: Many of the operations need n/4steps on average, constantnumber of steps in the best case (e.g. index = 0), and n/2steps in worst case (middle of list)}

^{注意：许多操作平均需要n/4步，在最好的情况下（例如索引 = 0）的步数保持不变，在最坏的情况下（列表的中间）需要n/2步}

For ArrayList<E>

为了 ArrayList<E>

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

• 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 element)是O(n)（平均有n/2步）

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

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

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/4steps) on average, though O(1)for index = 0.

LinkedList<E>允许使用 iterators进行恒定时间插入或删除，但只能对元素进行顺序访问。换句话说，您可以向前或向后遍历列表，但在列表中查找位置所需的时间与列表的大小成正比。Javadoc 说“索引到列表中的操作将从开始或结束遍历列表，以较近者为准”，因此这些方法平均为O(n)（n/4步），尽管O(1)为index = 0.

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 ArrayListis O(n)in the worst case but constant on average.

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

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 ArrayListis technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

因此，根据您打算执行的操作，您应该相应地选择实现。迭代任何一种 List 实际上同样便宜。（在ArrayList技术上迭代速度更快，但除非您正在做一些真正对性能敏感的事情，否则您不必担心这一点——它们都是常量。）

The main benefits of using a LinkedListarise 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 LinkedListmeans following the links in O(n)(n/2steps) for worst case, whereas in an ArrayListthe desired position can be computed mathematically and accessed in O(1).

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

Another benefit of using a LinkedListarise 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 ArrayDequemay be a good alternative to LinkedListfor adding and removing from the head, but it is not a List.

LinkedList当您从列表的头部添加或删除时，使用 a 的另一个好处是，因为这些操作是O(1)，而它们是O(n)for ArrayList。请注意，这ArrayDeque可能是LinkedList从头部添加和删除的一个很好的替代方法，但它不是List.

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

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

The default initial capacity of an ArrayListis 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 ArrayListwith a higher initial capacity.

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

回答by dgtized

It's an efficiency question. LinkedListis fast for adding and deleting elements, but slow to access a specific element. ArrayListis fast for accessing a specific element but can be slow to add to either end, and especially slow to delete in the middle.

这是一个效率问题。LinkedList添加和删​​除元素很快，但访问特定元素很慢。ArrayList访问特定元素的速度很快，但添加到任一端可能会很慢，尤其是在中间删除时会很慢。

Array vs ArrayList vs LinkedList vs Vectorgoes more in depth, as does Linked List.

Array vs ArrayList vs LinkedList vs Vector更深入， 链接列表也是如此。

回答by Dustin

ArrayListis randomly accessible, while LinkedListis really cheap to expand and remove elements from. For most cases, ArrayListis fine.

ArrayList是随机访问的，而LinkedList扩展和删除元素非常便宜。对于大多数情况，没问题ArrayList。

Unless you've created large lists and measured a bottleneck, you'll probably never need to worry about the difference.

除非您创建了大型列表并测量了瓶颈，否则您可能永远不需要担心差异。

回答by Matthew Schinckel

It depends upon what operations you will be doing more on the List.

这取决于您将在 List 上执行更多操作。

ArrayListis faster to access an indexed value. It is much worse when inserting or deleting objects.

ArrayList访问索引值更快。插入或删除对象时更糟。

To find out more, read any article that talks about the difference between arrays and linked lists.

要了解更多信息，请阅读任何讨论数组和链表区别的文章。

回答by PhiLho

In addition to the other good arguments above, you should notice ArrayListimplements RandomAccessinterface, while LinkedListimplements Queue.

除了上面的其他好的参数，你应该注意到ArrayListimplementsRandomAccess接口，而LinkedListimplements Queue。

So, somehow they address slightly different problems, with difference of efficiency and behavior (see their list of methods).

因此，他们以某种方式解决了略有不同的问题，效率和行为有所不同（请参阅他们的方法列表）。

回答by Tom Hawtin - tackline

ArrayListis what you want. LinkedListis almost always a (performance) bug.

ArrayList是你想要的。LinkedList几乎总是一个（性能）错误。

Why LinkedListsucks:

为什么LinkedList烂：

• It uses lots of small memory objects, and therefore impacts performance across the process.
• Lots of small objects are bad for cache-locality.
• Any indexed operation requires a traversal, i.e. has O(n) performance. This is not obvious in the source code, leading to algorithms O(n) slower than if ArrayListwas used.
• Getting good performance is tricky.
• Even when big-O performance is the same as ArrayList, it is probably going to be significantly slower anyway.
• It's jarring to see LinkedListin source because it is probably the wrong choice.

• 它使用大量小内存对象，因此会影响整个进程的性能。
• 许多小对象不利于缓存局部性。
• 任何索引操作都需要遍历，即具有 O(n) 性能。这在源代码中并不明显，导致算法 O(n) 比使用 if 慢ArrayList。
• 获得良好的性能是很棘手的。
• 即使 big-O 性能与 相同ArrayList，它也可能会明显变慢。
• LinkedList在源代码中看到令人不快，因为它可能是错误的选择。

回答by Jesse Wilson

If your code has add(0)and remove(0), use a LinkedListand it's prettier addFirst()and removeFirst()methods. Otherwise, use ArrayList.

如果您的代码有add(0)and remove(0)，请使用 a LinkedListand 它更漂亮addFirst()和removeFirst()方法。否则，使用ArrayList.

And of course, Guava's ImmutableListis your best friend.

当然，Guava的ImmutableList是你最好的朋友。

回答by Daniel Martin

Yeah, I know, this is an ancient question, but I'll throw in my two cents:

是的，我知道，这是一个古老的问题，但我会投入我的两分钱：

LinkedList is almost alwaysthe wrong choice, performance-wise. There are some very specific algorithms where a LinkedList is called for, but those are very, very rare and the algorithm will usually specifically depend on LinkedList's ability to insert and delete elements in the middle of the list relatively quickly, once you've navigated there with a ListIterator.

LinkedList在性能方面几乎总是错误的选择。有一些非常具体的算法需要使用 LinkedList，但这些算法非常非常罕见，并且该算法通常特别依赖于 LinkedList 在列表中间相对快速地插入和删除元素的能力，一旦你导航到那里使用 ListIterator。

There is one common use case in which LinkedList outperforms ArrayList: that of a queue. However, if your goal is performance, instead of LinkedList you should also consider using an ArrayBlockingQueue (if you can determine an upper bound on your queue size ahead of time, and can afford to allocate all the memory up front), or this CircularArrayList implementation. (Yes, it's from 2001, so you'll need to generify it, but I got comparable performance ratios to what's quoted in the article just now in a recent JVM)

LinkedList 优于 ArrayList 的一个常见用例是：队列的用例。但是，如果您的目标是性能，那么您还应该考虑使用 ArrayBlockingQueue（如果您可以提前确定队列大小的上限，并且可以预先分配所有内存），或者这个CircularArrayList 实现. （是的，它是从 2001 年开始的，因此您需要对其进行泛化，但是我在最近的 JVM 中获得了与文章中引用的性能比相当的性能比）

回答by Karussell

An important feature of a linked list (which I didn't read in another answer) is the concatenation of two lists. With an array this is O(n) (+ overhead of some reallocations) with a linked list this is only O(1) or O(2) ;-)

链表的一个重要特性（我在另一个答案中没有读到）是两个列表的连接。对于数组，这是 O(n)（+ 一些重新分配的开销），对于链表，这只是 O(1) 或 O(2) ;-)

Important: For Java its LinkedListthis is not true! See Is there a fast concat method for linked list in Java?

重要提示：对于 Java，LinkedList这不是真的！请参阅Java 中的链表是否有快速连接方法？

回答by Michael Munsey

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algorithms: Big-Oh Notation

算法：大哦符号

ArrayLists are good for write-once-read-many or appenders, but bad at add/remove from the front or middle.

ArrayLists 适用于一次写入多次读取或 appender，但不适合从前面或中间添加/删除。