我一直习惯于简单地使用：
List<String> names = new ArrayList<>();
我使用接口作为类型名称来实现可移植性，这样当我像这样提问时，我可以重新组织我的代码。
在什么情况下应该使用 LinkedList 而不是 ArrayList？反之呢？
何时在Java中使用LinkedList而不是ArrayList？
3601
- sdellysse
3
34个回答
3861
摘要 在IT技术中，
简而言之，在
与标准链表和数组操作一样，各种方法将具有不同的算法运行时间。
对于
使用 LinkedList 的另一个好处是当你添加或删除列表头时，这些操作的时间复杂度为 O(1)，而对于 ArrayList 的时间复杂度为 O(n)。请注意，ArrayDeque 可能是添加或删除列表头的良好替代品，但它不是 List。
此外，如果您有大型列表，请记住内存使用情况也是不同的。LinkedList 的每个元素都有更多的开销，因为还存储了指向下一个和前一个元素的指针。ArrayList 没有这个开销。然而，ArrayList 占用的内存与分配的容量一样多，而不管实际上是否添加了元素。
ArrayList 的默认初始容量非常小(Java 1.4-1.8 为10)。但由于底层实现是一个数组，如果添加了很多元素，则必须调整数组的大小。为避免在知道将添加大量元素时需要调整大小的高成本，请使用更高的初始容量构造 ArrayList。
如果使用数据结构的角度来理解这两个结构，LinkedList 基本上是一个包含头节点的顺序数据结构。该节点是两个组件的包装器: 通过泛型接受的类型 T 的值和链接到它的另一个节点的引用。因此，我们可以断言它是一种递归数据结构(一个节点包含另一个节点，该节点又包含另一个节点，依此类推...)。如上所述，在 LinkedList 中添加元素需要线性时间。
ArrayList 是可增长数组。它就像一个常规数组。在实现中，当添加一个元素而 ArrayList 已满时，它会创建一个大小大于先前大小的新数组。然后将元素从以前的数组复制到新的数组中，并将要添加的元素也放置在指定的索引处。
ArrayList和ArrayDeque比LinkedList更适用于许多使用情况。如果您不确定，只需从ArrayList开始。
简而言之，在
ArrayList中，访问元素需要常数时间[O(1)]，添加元素需要O(n)时间[最坏情况]。在LinkedList中，插入元素需要O(n)时间，访问也需要O(n)时间，但是LinkedList使用的内存比ArrayList多。
LinkedList和ArrayList是List接口的两种不同实现方式。LinkedList使用双向链表实现它。ArrayList使用动态调整大小的数组实现它。与标准链表和数组操作一样，各种方法将具有不同的算法运行时间。
对于
LinkedList<E>
get(int index)的时间复杂度为 O(n)（平均需要执行 n/4 步），但当index = 0或index = list.size() - 1时，时间复杂度为 O(1)（此时也可以使用getFirst()和getLast()）。LinkedList<E>的主要优势之一。add(int index, E element)的时间复杂度为 O(n)（平均需要执行 n/4 步），但当index = 0或index = list.size() - 1时，时间复杂度为 O(1)（此时也可以使用addFirst()和addLast()/add()）。LinkedList<E>的主要优势之一。remove(int index)的时间复杂度为 O(n)（平均需要执行 n/4 步），但当index = 0或index = list.size() - 1时，时间复杂度为 O(1)（此时也可以使用removeFirst()和removeLast()）。LinkedList<E>的主要优势之一。Iterator.remove()的时间复杂度为 O(1)。LinkedList<E>的主要优势之一。ListIterator.add(E element)的时间复杂度为 O(1)。LinkedList<E>的主要优势之一。
注意：许多操作平均需要执行 n/4 步，最好情况下（例如 index = 0）需要恒定的步数，最坏情况下（列表中间）需要执行 n/2 步。
对于 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 element)是 O(n) 的（平均需要 n/2 步）。
注意：许多操作在平均情况下需要 n/2 步，最好的情况下需要恒定数量的步骤（列表末尾），最坏的情况下需要 n 步（列表开头）
LinkedList<E> 允许使用迭代器进行常数时间插入或删除，但只允许元素的顺序访问。换句话说，您可以向前或向后遍历列表，但查找列表中的位置需要与列表大小成比例的时间。Javadoc 表示“索引到列表的操作将从开始或结束处遍历列表，以较近者为准”，因此这些方法在平均情况下是 O(n)（n/4 步），但对于 index = 0 是 O(1)。
ArrayList<E> 允许快速随机读取访问，因此您可以在常数时间内获取任何元素。但是，从任何位置添加或删除都需要将所有后续元素移动，以创建空位或填充间隙。此外，如果添加的元素多于底层数组的容量，则会分配一个新数组（大小为原来的 1.5 倍），并将旧数组复制到新数组中，因此在最坏情况下，向 ArrayList 添加是 O(n) 的，但平均是恒定的。
因此，根据您想要执行的操作，应相应地选择实现。迭代两种类型的列表几乎同样便宜。（迭代 ArrayList 在技术上更快，但除非您正在做一些真正性能敏感的事情，否则不必担心——它们都是常数。）
使用 LinkedList 的另一个好处是当你添加或删除列表头时，这些操作的时间复杂度为 O(1)，而对于 ArrayList 的时间复杂度为 O(n)。请注意，ArrayDeque 可能是添加或删除列表头的良好替代品，但它不是 List。
此外，如果您有大型列表，请记住内存使用情况也是不同的。LinkedList 的每个元素都有更多的开销，因为还存储了指向下一个和前一个元素的指针。ArrayList 没有这个开销。然而，ArrayList 占用的内存与分配的容量一样多，而不管实际上是否添加了元素。
ArrayList 的默认初始容量非常小(Java 1.4-1.8 为10)。但由于底层实现是一个数组，如果添加了很多元素，则必须调整数组的大小。为避免在知道将添加大量元素时需要调整大小的高成本，请使用更高的初始容量构造 ArrayList。
如果使用数据结构的角度来理解这两个结构，LinkedList 基本上是一个包含头节点的顺序数据结构。该节点是两个组件的包装器: 通过泛型接受的类型 T 的值和链接到它的另一个节点的引用。因此，我们可以断言它是一种递归数据结构(一个节点包含另一个节点，该节点又包含另一个节点，依此类推...)。如上所述，在 LinkedList 中添加元素需要线性时间。
ArrayList 是可增长数组。它就像一个常规数组。在实现中，当添加一个元素而 ArrayList 已满时，它会创建一个大小大于先前大小的新数组。然后将元素从以前的数组复制到新的数组中，并将要添加的元素也放置在指定的索引处。
- Jonathan Tran
13
44许多人忽略的一件事是，ArrayList 在内存中更加紧凑，这意味着它比 LinkedList 更加缓存友好。LinkedList 可能分散在 RAM 中，而 ArrayList 总是紧密地打包在一起以利用空间局部性。这具有重要的现实影响。 - AminM
6只有对象引用是紧凑的，对象本身可能会分散... 直到我们获得值类型。 - swpalmer
5@swpalmer 当然。
然而，在LinkedList中，即使只是查找所需的项目，也需要遍历RAM布局。而使用ArrayList时，您可以使用很少的缓存未命中扫描它。缓存未命中对性能非常重要。 - AminM
5我的观点是，要找到你想要的东西，你可能仍然需要跟随那个引用，并且可能会遇到缓存未命中的情况。除非你只关心引用标识。我知道在链接的情况下，你只是为了到达引用本身而遭受缓存未命中的问题。我只是说，Java数组还有另一种方式受到缓存未命中的影响......直到Valhalla。 - swpalmer
4我的观点是，相比之下缓存未命中的情况显著减少。这一点可以从其他人在这里发布的性能比较中看出。使用链表时，通常情况下性能会明显降低。 - AminM
显示剩余8条评论
695
到目前为止，似乎没有人除了普遍认为LinkedList比ArrayList占用更多内存之外，对这些列表的内存占用量进行过详细说明，因此我进行了一些数字计算，以演示这两个列表在N个空引用时占用的确切空间。
由于引用在它们相应的系统上是32位或64位（即使为空），因此我包括了32位和64位LinkedLists和ArrayLists的4组数据。
注意：ArrayList行中显示的大小是针对修剪后的列表 - 实际上，在ArrayList中，支持数组的容量通常大于其当前元素计数。
注意2：（感谢BeeOnRope）由于从JDK6中期开始，默认情况下启用了CompressedOops，因此64位机器的下面的值基本上与它们的32位对应项相匹配，除非您明确关闭它。
结果清楚地显示，特别是在非常高的元素计数下，LinkedList比ArrayList占用更多的内存。如果内存是一个因素，请避免使用LinkedLists。
我使用的公式如下，如果我做错了什么，请告诉我，我会进行修正。'b'对于32位或64位系统，可以是4或8，'n'是元素数量。请注意，进行模运算的原因是因为Java中的所有对象都将占用8字节的空间，无论是否全部使用。
ArrayList：
ArrayList对象头 + 大小整数 + modCount整数 + 数组引用 + (数组对象头 + b * n) + MOD(数组对象, 8) + MOD(ArrayList对象, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)
LinkedList:
LinkedList对象头 + 大小整数 + modCount整数 + 头引用 + 尾引用 + (节点对象开销 + 前一个元素的引用 + 下一个元素的引用 + 对象引用) * n) + MOD(节点对象, 8) * n + MOD(LinkedList对象, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
- Numeron
2
280你的数学问题在于你的图表夸大了影响。你正在建模仅包含一个“int”即4或8字节数据的对象。在链表中，基本上有4个额外的“字”，因此你的图表给人的印象是链表使用比数组列表“五倍”的存储空间。这是错误的。开销是每个对象16或32字节，作为加法调整，而不是缩放因子。 - Heath Hunnicutt
此外，在许多情况下，对象将不是整数，而是一个大对象。比如说，你正在你的应用程序中实现撤销功能，所以对象就是所做的更改，可能是很多字节。因此，LinkedList仍然比ArrayList占用更多的内存，但只是微不足道的多一点。 - undefined
308
ArrayList是你所需要的，LinkedList几乎总是（性能）有问题。
为什么LinkedList不好：
- 它使用许多小内存对象，从而影响整个进程的性能。
- 许多小对象对于缓存局部性不利。
- 任何索引操作都需要遍历，即具有O(n)性能。这在源代码中不明显，导致算法比使用
ArrayList慢O(n)。 - 获得良好的性能很棘手。
- 即使大O性能与
ArrayList相同，它可能仍然会显着较慢。 - 在源代码中看到
LinkedList很刺眼，因为它可能是错误的选择。
- Tom Hawtin - tackline
190
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)
算法：大O符号 （已存档）
ArrayList适用于写一次读多次或者追加，但不适合在中间或开头添加或删除元素。
- Michael Munsey
12
55不考虑常数因素，不能直接比较大O值。对于小列表（大多数列表都是小的），ArrayList的O(N)比LinkedList的O(1)更快。 - Porculus
7我不关心小列表的性能，我的电脑也一样，除非它在某种循环中使用。 - Maarten Bodewes
64链表无法以
O(1) 的时间复杂度在中间插入元素。它需要遍历一半的链表以找到插入点。 - Thomas Ahle11链表：在中间插入 O(1) 是错误的！我发现，即使在链表长度的十分之一位置插入元素，速度也比在 ArrayList 中插入元素慢。更糟糕的是，在集合末尾插入元素。在 ArrayList 的最后位置（不是最后一个位置）插入元素比在 LinkedList 的最后位置（不是最后一个位置）插入元素更快。 - kachanov
23如果您有一个指向插入位置的迭代器，那么在
LinkedList 中进行插入操作确实是 O(1) 的，也就是说，对于 LinkedList 来说，ListIterator.add 操作应该是 O(1)。 - Has QUIT--Anony-Mousse显示剩余7条评论
158
以下是原作者在2021年8月27日的更新：
我写这篇答案时，我的关注点是系统的可用性和鲁棒性。但是随着时间的推移，针对Java的垃圾回收器和集合类的实现方式已经发生了很大变化。目前，对于所谓的“小对象”，G1垃圾回收器通常比CMS提供更好的低延迟。
另外，在性能方面，JDK 15中引入的ZGC收集器可能成为一个不错的选择。与G1相比，它可以处理更大的堆，并且具有更低的停顿时间；并且它还允许您在应用程序运行时动态更改堆大小。
最后，集合类的实现方式也发生了变化。例如，从Java 8开始，在某些情况下，ArrayList的性能可能优于LinkedList，因为它利用了CPU缓存的局部性。此外，Java 9引入了一种名为Compact Strings的新字符串编码格式，它可以显著减少String对象的内存占用量。
这个答案（我在stackoverflow上历史上点赞最多的答案）很可能是错误的（原因在下面的评论中概述）。我想补充说明ArrayList将优化顺序读取内存并最小化缓存行和TLB（翻译注：转换后备缓冲器）未命中等。当数组超过边界时，复制开销可能相对不重要（可以通过高效CPU操作完成）。随着硬件趋势的发展，这个答案也可能变得更糟糕。唯一需要LinkedList的情况可能是某些高度假设的情况，其中有数千个List之一可能会增长到GB大小，但在分配列表时无法做出良好的猜测，并且将它们全部设置为GB大小会使堆积累。如果您发现了这样的问题，那么确实需要重新设计您的解决方案（我不喜欢轻易建议重新设计旧代码，因为我自己维护着大量老代码，但这确实是一个非常好的情况，原始设计已经简单地耗尽了跑道，并且确实需要被扔掉）。我仍然会把我的几十年前的愚见留给你阅读。简单、逻辑和非常错误。
- lamont
7
9另一种解决方案不是使用ArrayList的ensureCapacity()方法通过编程管理列表大小吗？我的问题是为什么这么多东西都存储在脆弱的数据结构中，而它们可能更好地存储在缓存或数据库机制中？我前几天面试时，他们断言ArrayList的邪恶，但我来到这里发现复杂性分析全面更好！这是一个很好的讨论点，谢谢！ - ingyhere
30如果您使用10GB堆大小的Java应用程序，可能会在Full GC期间锁定应用程序长达25秒，从而导致超时。实际上，如果使用LinkedList数据结构，在Full GC期间，垃圾回收器会遇到性能问题，因为需要对过大的LinkedList进行迭代，并且每次节点访问都会发生缓存未命中。 - bestsss
7这个解决方案很糟糕。你基本上要依赖于垃圾回收器为你清理内存，这非常昂贵，而你只需在ArrayList上调用ensureCapacity()方法就可以避免这种情况。 - Philip Devine
3一个超过其容量的数组列表会分配一个新的列表，它的空间增加了50%。对于这个增量，你需要2.5倍的内存（之后可能需要进行完整的 gc 循环）。我不担心日常响应时间，我担心在高峰期比昨天更严重地袭击时，内存耗尽的情况发生，并且一些大型数组列表决定它们需要为自己的数量增加2.5倍的空间，持续一两秒钟。在高峰使用期间出现这种行为的一个实例就会炸掉我整个月的 sla。 - Andreas
9@Andreas: 一种
LinkedList比一个简单的引用数组总是分配五倍的内存，因此，即使在内存未被回收时，暂时需要2.5倍空间的ArrayList仍然消耗更少的内存。由于大型数组分配绕过了伊甸园空间，它们不会对垃圾回收行为产生任何影响，除非真的没有足够的内存，在这种情况下，LinkedList会更早地出现问题... - Holger显示剩余2条评论
135
LinkedList的作者Joshua Bloch曾说：
有人真正使用LinkedList吗？我写了它，但我从不使用它。
链接：https://twitter.com/joshbloch/status/583813919019573248
抱歉我的答案可能不像其他答案那么详细，但我觉得这是最自解释的答案，虽然没有透露更多信息。
- Ruslan
123
是的，我知道这是一个古老的问题，但我会提供我的意见：
LinkedList在大多数情况下从性能上来说都不是一个好的选择。有一些非常特殊的算法需要使用LinkedList，但这些情况非常罕见，而且算法通常需要利用LinkedList相对快速地插入和删除列表中间的元素，一旦你使用ListIterator导航到那里。
有一种常见的用例，LinkedList优于ArrayList：队列。然而，如果您的目标是性能，除了LinkedList之外，您还应该考虑使用ArrayBlockingQueue（如果您可以预先确定队列大小的上限，并且可以承受一次性分配所有内存），或者使用CircularArrayList实现。（是的，它来自2001年，所以您需要泛型化它，但我刚才在最近的JVM中得到了与文章中引用的可比性能比率）
- Daniel Martin
6
41从 Java 6 开始，你可以使用
ArrayDeque。http://docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html - Thomas Ahle1
ArrayDeque 比 LinkedList 慢，除非所有操作都在同一端。当用作堆栈时可以，但不适合用作队列。 - Jeremy List4至少对于Oracle在jdk1.7.0_60中的实现以及以下测试来说，这是不正确的。我创建了一个测试，在其中循环1000万次，并且有一个包含1000万个随机整数的双端队列。在循环内部，我从中poll出一个元素并offer一个常量元素。在我的电脑上，LinkedList比ArrayDeque慢10多倍，并且使用的内存更少）。原因是与ArrayList不同，ArrayDeque保留了对数组头的指针，因此在删除头时不必移动所有元素。 - Henno Vermeulen
这是对Jeremy的回复。Daniel是正确的。如果我在同一个测试中使用List作为队列，当我将循环和队列大小都减少到300_000时，ArrayList比LinkedList慢300倍。我甚至不会尝试1000万次。我猜所提到的CircularArrayList类似于ArrayDeque，它们都保持对头部指针的引用而不是移动元素。 - Henno Vermeulen
8当用作栈时，
ArrayDeque 比 Stack 更快，当用作队列时，比 LinkedList 更快。 - akhil_mittal8请注意，akhil_mittal的评论是从“ArrayDeque”文档中引用的。 - Stuart Marks
87
这是一个效率问题。对于在列表的末尾添加或删除大型元素，
LinkedList速度快，但访问特定元素较慢。对于访问特定元素，ArrayList速度快，但在两端添加元素可能较慢，尤其是在中间删除元素时更慢。
Array vs ArrayList vs LinkedList vs Vector提供了更深入的解释，Linked List也是如此。- dgtized
2
10值得一提的是，
LinkedList 在仅对第一个和最后一个位置进行添加/移除时速度很快-此时复杂度为O(1)，但是在中间添加则仍为O(n)，因为我们需要遍历大约n/2个LinkedList元素。 - Dmitriy Fialkovskiy1然而，这是真的吗？为什么ArrayList总是比LinkedList更快发现将10M个项目添加到ArrayList比将10M个项目添加到LinkedList更快。（即，在末尾添加时，ArrayList更快，摊销了有时需要重新分配的成本。） - Peter Cordes
61
正确或错误：请在本地执行测试，自己决定！
在LinkedList中，编辑/删除比ArrayList更快。
ArrayList由Array支持，需要将其大小加倍，在大容量应用程序中效果更差。
下面是每个操作的单元测试结果。计时以纳秒为单位。
Operation ArrayList LinkedList
AddAll (Insert) 101,16719 2623,29291
Add (Insert-Sequentially) 152,46840 966,62216
Add (insert-randomly) 36527 29193
remove (Delete) 20,56,9095 20,45,4904
contains (Search) 186,15,704 189,64,981
这是代码：
import org.junit.Assert;
import org.junit.Test;
import java.util.*;
public class ArrayListVsLinkedList {
private static final int MAX = 500000;
String[] strings = maxArray();
////////////// ADD ALL ////////////////////////////////////////
@Test
public void arrayListAddAll() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX);
watch.start();
arrayList.addAll(stringList);
watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
}
@Test
public void linkedListAddAll() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
watch.start();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(stringList);
watch.totalTime("Linked List addAll() = "); //2623,29291 Nanoseconds
}
//Note: ArrayList is 26 time faster here than LinkedList for addAll()
///////////////// INSERT /////////////////////////////////////////////
@Test
public void arrayListAdd() {
Watch watch = new Watch();
List<String> arrayList = new ArrayList<String>(MAX);
watch.start();
for (String string : strings)
arrayList.add(string);
watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
}
@Test
public void linkedListAdd() {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
watch.start();
for (String string : strings)
linkedList.add(string);
watch.totalTime("Linked List add() = "); //966,62216 Nanoseconds
}
//Note: ArrayList is 9 times faster than LinkedList for add sequentially
/////////////////// INSERT IN BETWEEN ///////////////////////////////////////
@Test
public void arrayListInsertOne() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
arrayList.addAll(stringList);
String insertString0 = getString(true, MAX / 2 + 10);
String insertString1 = getString(true, MAX / 2 + 20);
String insertString2 = getString(true, MAX / 2 + 30);
String insertString3 = getString(true, MAX / 2 + 40);
watch.start();
arrayList.add(insertString0);
arrayList.add(insertString1);
arrayList.add(insertString2);
arrayList.add(insertString3);
watch.totalTime("Array List add() = ");//36527
}
@Test
public void linkedListInsertOne() {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(stringList);
String insertString0 = getString(true, MAX / 2 + 10);
String insertString1 = getString(true, MAX / 2 + 20);
String insertString2 = getString(true, MAX / 2 + 30);
String insertString3 = getString(true, MAX / 2 + 40);
watch.start();
linkedList.add(insertString0);
linkedList.add(insertString1);
linkedList.add(insertString2);
linkedList.add(insertString3);
watch.totalTime("Linked List add = ");//29193
}
//Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.
////////////////// DELETE //////////////////////////////////////////////////////
@Test
public void arrayListRemove() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX);
arrayList.addAll(stringList);
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
arrayList.remove(searchString0);
arrayList.remove(searchString1);
watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
}
@Test
public void linkedListRemove() throws Exception {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(Arrays.asList(strings));
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
linkedList.remove(searchString0);
linkedList.remove(searchString1);
watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
}
//Note: LinkedList is 10 millisecond faster than ArrayList while removing item.
///////////////////// SEARCH ///////////////////////////////////////////
@Test
public void arrayListSearch() throws Exception {
Watch watch = new Watch();
List<String> stringList = Arrays.asList(strings);
List<String> arrayList = new ArrayList<String>(MAX);
arrayList.addAll(stringList);
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
arrayList.contains(searchString0);
arrayList.contains(searchString1);
watch.totalTime("Array List addAll() time = ");//186,15,704
}
@Test
public void linkedListSearch() throws Exception {
Watch watch = new Watch();
List<String> linkedList = new LinkedList<String>();
linkedList.addAll(Arrays.asList(strings));
String searchString0 = getString(true, MAX / 2 + 10);
String searchString1 = getString(true, MAX / 2 + 20);
watch.start();
linkedList.contains(searchString0);
linkedList.contains(searchString1);
watch.totalTime("Linked List addAll() time = ");//189,64,981
}
//Note: Linked List is 500 Milliseconds faster than ArrayList
class Watch {
private long startTime;
private long endTime;
public void start() {
startTime = System.nanoTime();
}
private void stop() {
endTime = System.nanoTime();
}
public void totalTime(String s) {
stop();
System.out.println(s + (endTime - startTime));
}
}
private String[] maxArray() {
String[] strings = new String[MAX];
Boolean result = Boolean.TRUE;
for (int i = 0; i < MAX; i++) {
strings[i] = getString(result, i);
result = !result;
}
return strings;
}
private String getString(Boolean result, int i) {
return String.valueOf(result) + i + String.valueOf(!result);
}
}
- Ash
13
1ArrayList不需要加倍，准确起见，请先检查源代码。 - Danubian Sailor
这也可能是为什么remove/contains之间的差异很小的原因。 - Centril
4"... is worse in large volume application": 这是一个误解。
LinkedList的内存开销更大，因为对于每个元素，都有一个具有五个字段的节点对象。在许多系统上，这会产生20字节的开销。ArrayList每个元素的平均内存开销是一个半字，即6字节，在最坏情况下是8字节。 - Lii2我已经做了一个更好的基准测试版本在这里，附带结果 - 你的ArrayList的append-on-end性能是人为地低于我的，因为addAll给出了一个刚好是初始大小的存储数组，所以第一次插入总是会触发arraycopy。此外，这包括预热周期，以允许JIT编译在收集数据之前进行。 - BobMcGee
5自Java 8起，您可以在适合的情况下使用
removeIf(element -> condition)，这对于ArrayList而言可以比通过迭代器循环和删除更快，因为不需要为每个元素移动整个剩余部分。这是否比LinkedList表现更好或更差取决于特定场景，因为LinkedList在理论上是O(1)，但仅删除一个节点就需要多次内存访问，这很容易超过删除大量元素时所需的数量。 - Holger显示剩余8条评论
57
ArrayList本质上是一个数组。 LinkedList是作为双向链表实现的。
get很清楚。对于ArrayList，它允许使用索引进行随机访问，因此为O（1）。对于LinkedList，由于需要先找到索引，因此为O（n）。注意：有不同版本的add和remove.
LinkedList在添加和删除方面更快，但在获取方面更慢。简而言之，如果：
- 没有大量对元素进行随机访问
- 有大量添加/删除操作
应该首选LinkedList。
=== ArrayList ===
- add（E e）
- 在ArrayList的末尾添加
- 需要内存调整成本。
- O(n)最坏情况下，O(1)摊销
- add（int index，E element）
- 添加到特定的索引位置
- 需要移位和可能的内存调整成本
- O(n)
- remove（int index）
- 移除指定的元素
- 需要移位和可能的内存调整成本
- O(n)
- remove（Object o）
- 从此列表中删除指定元素的第一个匹配项
- 需要先搜索元素，然后移位和可能的内存调整成本
- O(n)
=== LinkedList ===
add（E e）
- 添加到列表的末尾
- O(1)
add（int index，E element）
- 在指定位置插入
- 需要先找到位置
- O(n)
- 删除列表的第一个元素
- O(1)
- 删除指定索引位置的元素
- 需要先查找元素
- O(n)
- 删除指定元素的第一个出现位置
- 需要先查找元素
- O(n)
以下是来自 programcreek.com 的图片（add 和 remove 属于第一类，即在列表末尾添加元素并删除列表中指定位置的元素）：
- Ryan
1
4“LinkedList比add/remove更快”这句话是错误的。请查看上面的答案：https://dev59.com/Y3RC5IYBdhLWcg3wW_tk#7507740 - Abbas Gadhia
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 31 在Java中何时使用Map而不是List？
- 464 何时应该使用List而不是LinkedList？
- 39 在C#中何时使用ArrayList而不是array[]？
- 38 在Java中何时使用列表而不是数组？
- 6 何时在声明变量/参数时使用ArrayList或LinkedList而不是List才是正确的？
- 5 Java中如何实现LinkedList转换为ArrayList？
- 12 为什么在Java中LinkedList和ArrayList继承AbstractList？
- 14 为什么HashMap内部使用LinkedList而不是ArrayList？
- 8 何时在Java中使用expm1而不是exp
- 95 何时使用HashMap而不是LinkedList或ArrayList，反之亦然
std::vector（类似于Java的ArrayList）和std::list（类似于Java的LinkedList）。 - kevinarpe