在 Java 中何时使用 LinkedList 而不是 ArrayList？
https://stackoverflow.com/questions/322715
-
11-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我一直是一个简单地使用的人：
List<String> names = new ArrayList<>();
我使用接口作为类型名称 可移植性, ，这样当我提出诸如此类的问题时，我就可以修改我的代码。
什么时候应该 LinkedList 被使用过 ArrayList 反之亦然？
解决方案
概括 ArrayList 和 ArrayDeque 最好在 许多 更多用例 LinkedList. 。如果您不确定 - 只需从 ArrayList.
LinkedList 和 ArrayList 是 List 接口的两种不同实现。 LinkedList 用双向链表来实现它。 ArrayList 使用动态调整大小的数组来实现它。
与标准链表和数组操作一样，各种方法将具有不同的算法运行时。
get(int index)是 在） （和 n/4 平均步数）add(E element)是 复杂度(1)add(int index, E element)是 在） （和 n/4 平均步骤），但是 复杂度(1) 什么时候index = 0<--- 主要好处LinkedList<E>remove(int index)是 在） （和 n/4 平均步数）Iterator.remove()是 复杂度(1). 。<--- 主要好处LinkedList<E>ListIterator.add(E element)是 复杂度(1) 这是主要好处之一LinkedList<E>
笔记：很多操作都需要 n/4 平均步数， 持续的 最佳情况下的步骤数（例如索引 = 0), 以及 n/2 最坏情况下的步骤（列表中间）
为了 ArrayList<E>
get(int index)是 复杂度(1) <--- 主要好处ArrayList<E>add(E element)是 复杂度(1) 摊销，但是 在） 最坏的情况，因为必须调整数组大小并复制add(int index, E element)是 在） （和 n/2 平均步数）remove(int index)是 在） （和 n/2 平均步数）Iterator.remove()是 在） （和 n/2 平均步数）ListIterator.add(E element)是 在） （和 n/2 平均步数）
笔记：很多操作都需要 n/2 平均步数， 持续的 最佳情况下的步骤数（列表末尾）， n 最坏情况下的步骤（列表开头）
LinkedList<E> 允许恒定时间插入或删除 使用迭代器, ，但仅限于元素的顺序访问。换句话说，您可以向前或向后遍历列表，但在列表中查找位置所需的时间与列表的大小成正比。Javadoc 说 “索引到列表的操作将从头或尾遍历列表，以较接近的为准”, ，所以这些方法是 在） (n/4 步）平均而言，虽然 复杂度(1) 为了 index = 0.
ArrayList<E>, 另一方面，允许快速随机读取访问，因此您可以在恒定时间内抓取任何元素。但是，从除末尾以外的任何地方添加或删除都需要将后面的所有元素移过来，要么形成一个开口，要么填补空白。另外，如果添加的元素多于基础数组的容量，则会分配一个新数组（大小的 1.5 倍），并将旧数组复制到新数组，因此添加到 ArrayList 是 在） 在最坏的情况下，但平均而言是恒定的。
因此，根据您打算执行的操作，您应该相应地选择实现。迭代任何一种列表实际上都同样便宜。（迭代一个 ArrayList 从技术上来说更快，但除非你正在做一些真正对性能敏感的事情，否则你不应该担心这一点——它们都是常量。）
使用的主要好处 LinkedList 当您重新使用现有迭代器插入和删除元素时会出现这种情况。这些操作可以在 复杂度(1) 仅在本地更改列表。在数组列表中，数组的其余部分需要是 搬家了 （IE。复制）。另一方面，寻找 LinkedList 意味着点击以下链接 在） (n/2 步骤）对于最坏的情况，而在 ArrayList 所需的位置可以通过数学计算并访问 复杂度(1).
使用的另一个好处是 LinkedList 当您在列表的头部添加或删除时会出现，因为这些操作是 复杂度(1), ，虽然他们是 在） 为了 ArrayList. 。注意 ArrayDeque 可能是一个很好的替代品 LinkedList 用于添加和删除头部，但它不是 List.
另外，如果您有很大的列表，请记住内存使用情况也是不同的。a 的每个元素 LinkedList 由于还存储了指向下一个和上一个元素的指针，因此开销更大。 ArrayLists 没有这个开销。然而， ArrayLists 占用与分配给容量一样多的内存，无论是否实际添加了元素。
默认初始容量 ArrayList 非常小（Java 1.4 - 1.8 中为 10）。但由于底层实现是一个数组，如果添加大量元素，则必须调整数组的大小。当您知道要添加大量元素时，为了避免调整大小的高成本，请构造 ArrayList 具有较高的初始容量。
其他提示
到目前为止，似乎没有人解决过每个列表的内存占用问题，除了普遍的共识： LinkedList 比一个“多得多” ArrayList 所以我做了一些数字运算来准确演示两个列表占用 N 个空引用的量。
由于引用在其相关系统上要么是 32 位，要么是 64 位（即使为空），所以我包含了 4 组 32 位和 64 位的数据 LinkedLists 和 ArrayLists.
笔记： 显示的尺寸为 ArrayList 线路是为了 修剪列表 - 在实践中，后备阵列的容量 ArrayList 通常大于其当前元素数。
笔记2： （感谢 BeeOnRope） 由于 CompressedOops 现在是 JDK6 中期及以上版本的默认值，因此以下 64 位计算机的值基本上与 32 位计算机的值相匹配，当然，除非您专门将其关闭。
结果清楚地表明 LinkedList 比 ArrayList, ，尤其是元素数量非常高的情况下。如果内存是一个因素，请避开 LinkedLists.
我使用的公式如下，如果我做错了什么，请告诉我，我会修复它。对于 32 位或 64 位系统，“b”是 4 或 8，“n”是元素数量。注意mods的原因是因为java中的所有对象无论是否全部使用都会占用8字节的倍数空间。
数组列表：
ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 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 object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 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)
ArrayList 就是你想要的。 LinkedList 几乎总是一个（性能）错误。
为什么 LinkedList 很糟糕：
- 它使用大量小内存对象，因此会影响整个进程的性能。
- 许多小对象不利于缓存局部性。
- 任何索引操作都需要遍历，即具有 O(n) 性能。这在源代码中并不明显，导致算法比 if 慢 O(n)
ArrayList被使用了。 - 获得良好的性能是很棘手的。
- 即使大 O 性能与
ArrayList, ，无论如何它可能会明显变慢。 - 看到它很刺耳
LinkedList在源代码中，因为它可能是错误的选择。
作为一个在超大规模 SOA Web 服务上进行操作性能工程大约十年的人，我更喜欢 LinkedList 的行为而不是 ArrayList。虽然 LinkedList 的稳态吞吐量较差，因此可能会导致购买更多硬件，但 ArrayList 在压力下的行为可能会导致集群中的应用程序几乎同步地扩展其数组，而对于大数组可能会导致缺乏响应能力在应用程序中并且在压力下发生中断，这是灾难性的行为。
同样，您可以通过默认吞吐量终身垃圾收集器在应用程序中获得更好的吞吐量，但是一旦您获得具有 10GB 堆的 Java 应用程序，您可能会在 Full GC 期间将应用程序锁定 25 秒，这会导致 SOA 应用程序超时和失败如果这种情况发生得太频繁，就会破坏您的 SLA。尽管 CMS 收集器占用更多资源并且无法实现相同的原始吞吐量，但它是一个更好的选择，因为它具有更可预测和更小的延迟。
仅当性能指的是吞吐量并且可以忽略延迟时，ArrayList 才是性能更好的选择。根据我的工作经验，我不能忽视最坏情况下的延迟。
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)
ArrayList 适合一次写入多次读取或附加程序，但不适合从前面或中间添加/删除。
是的，我知道，这是一个古老的问题，但我会提出我的两分钱：
链表是 几乎总是 从性能角度来看，这是错误的选择。有一些非常具体的算法需要使用 LinkedList，但这些算法非常非常罕见，并且该算法通常具体取决于 LinkedList 在导航到列表中间后相对快速地插入和删除元素的能力使用 ListIterator。
在一种常见的用例中，LinkedList 的性能优于 ArrayList：队列的那个。但是，如果您的目标是性能，那么您还应该考虑使用 ArrayBlockingQueue 而不是 LinkedList（如果您可以提前确定队列大小的上限，并且可以负担得起预先分配所有内存），或者这个 CircularArrayList 实现. 。（是的，它是 2001 年的，所以你需要对其进行泛化，但我在最近的 JVM 中获得了与刚才文章中引用的性能比相当的性能比）
这是一个效率问题。 LinkedList 添加和删除元素的速度很快，但访问特定元素的速度很慢。 ArrayList 访问特定元素很快，但添加到任一端可能很慢，尤其是在中间删除很慢。
数组、ArrayList、LinkedList、Vector 更深入，就像链表.
正确或不正确：请在本地进行测试并自行决定！
编辑/删除速度更快 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);
}
}
ArrayList 本质上是一个数组。 LinkedList 被实现为双链表。
这 get 很清楚。O(1) 对于 ArrayList, ， 因为 ArrayList 允许使用索引进行随机访问。对 LinkedList, ，因为它需要先找到索引。笔记：有不同的版本 add 和 remove.
LinkedList 添加和删除速度更快，但获取速度较慢。简单来说， LinkedList 如果满足以下条件，应优先考虑：
- 没有大量元素的随机访问
- 有大量的添加/删除操作
=== 数组列表 ===
- 添加(E e)
- 添加到ArrayList的末尾
- 需要内存调整大小成本。
- O(n) 最坏，O(1) 摊销
- 添加（int索引，E元素）
- 添加到特定索引位置
- 需要转移和可能的内存大小调整成本
- 在）
- 删除（整数索引）
- 删除指定元素
- 需要转移和可能的内存大小调整成本
- 在）
- 删除（对象o）
- 从此列表中删除第一次出现的指定元素
- 需要先搜索元素，然后移动和可能的内存大小调整成本
- 在）
=== 链表 ===
添加(E e)
- 添加到列表末尾
- 复杂度(1)
添加（int索引，E元素）
- 在指定位置插入
- 需要先找到位置
- 在）
- 消除（）
- 删除列表的第一个元素
- 复杂度(1)
- 删除（整数索引）
- 删除指定索引的元素
- 需要先找到元素
- 在）
- 删除（对象o）
- 删除第一次出现的指定元素
- 需要先找到元素
- 在）
这是一张来自 程序溪网 (add 和 remove 是第一种类型，即在列表末尾添加一个元素并删除列表中指定位置的元素。）：
Joshua Bloch，LinkedList 的作者：
有人真正使用LinkedList吗？我写了它，但我从来没有使用过它。
关联： https://twitter.com/joshbloch/status/583813919019573248
我很抱歉这个答案不像其他答案那样信息丰富，但我认为这将是最有趣且不言自明的。
ArrayList 是随机可访问的，同时 LinkedList 扩展和删除元素确实很便宜。对于大多数情况， ArrayList 很好。
除非您创建了大型列表并测量了瓶颈，否则您可能永远不需要担心差异。
我知道这是一篇旧文章，但老实说我不敢相信没有人提到这一点 LinkedList 实施 Deque. 。只需查看其中的方法即可 Deque （和 Queue）；如果你想要一个公平的比较，请尝试运行 LinkedList 反对 ArrayDeque 并进行逐个功能的比较。
这是两者中的 Big-O 表示法 ArrayList 和 LinkedList 并且 CopyOnWrite-ArrayList:
数组列表
get O(1)
add O(1)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
链表
get O(n)
add O(1)
contains O(n)
next O(1)
remove O(1)
iterator.remove O(1)
写时复制-ArrayList
get O(1)
add O(n)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
基于这些，你必须决定选择什么。:)
长话短说 由于现代计算机体系结构， ArrayList 对于几乎任何可能的用例来说，效率都会显着提高 - 因此 LinkedList 除了一些非常独特和极端的情况外，应该避免。
理论上，LinkedList 的 O(1) add(E element)
在列表中间添加元素应该非常有效。
实践是非常不同的，因为 LinkedList 是一个 缓存敌对 数据结构。从性能 POV 来看 - 很少有情况 LinkedList 可能会比 缓存友好 ArrayList.
以下是在随机位置插入元素的基准测试结果。正如您所看到的 - 数组列表效率更高，尽管理论上在列表中间的每个插入都需要“移动” n 数组后面的元素（值越低越好）：
使用新一代硬件（更大、更高效的缓存）——结果更加明确：
LinkedList 需要更多的时间来完成同样的工作。 来源 源代码
这有两个主要原因：
主要是 - 的节点
LinkedList随机分散在内存中。RAM（“随机存取存储器”）并不是真正随机的，需要提取内存块以进行缓存。这个操作需要时间，当这样的取操作频繁发生时——缓存中的内存页面需要一直被替换——>缓存未命中——>缓存效率不高。ArrayList元素存储在连续内存中 - 这正是现代 CPU 架构正在优化的目的。中学
LinkedList需要保留后退/前进指针，这意味着存储每个值的内存消耗是ArrayList.
动态整数数组, 顺便说一句，是一个自定义的 ArrayList 实现，其中包含 Int （原始类型）而不是对象 - 因此所有数据实际上都是相邻存储的 - 因此效率更高。
要记住的一个关键要素是，获取内存块的成本比访问单个内存单元的成本更重要。这就是为什么读取 1MB 顺序内存的速度比从不同内存块读取如此数量的数据快 400 倍：
Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference 0.5 ns
Branch mispredict 5 ns
L2 cache reference 7 ns 14x L1 cache
Mutex lock/unlock 25 ns
Main memory reference 100 ns 20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy 3,000 ns 3 us
Send 1K bytes over 1 Gbps network 10,000 ns 10 us
Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD
Read 1 MB sequentially from memory 250,000 ns 250 us
Round trip within same datacenter 500,000 ns 500 us
Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory
Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip
Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD
Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms
来源： 每个程序员都应该知道的延迟数字
为了让这一点更清楚，请检查将元素添加到列表开头的基准。这是一个用例，理论上， LinkedList 应该真的闪闪发光，并且 ArrayList 应该呈现糟糕甚至更糟糕的结果：
笔记：这是 C++ Std lib 的基准测试，但我之前的经验表明 C++ 和 Java 结果非常相似。 源代码
复制大量连续内存是现代 CPU 优化的操作 - 改变了理论，实际上再次， ArrayList/Vector 更有效率
让我们比较一下 LinkedList 和 ArrayList。以下参数：
1.执行
数组列表 是 list 接口的可调整大小的数组实现，而
链表 是列表接口的双向链表实现。
2.表现
get(int index) 或搜索操作
数组列表 get(int index) 操作以恒定时间运行，即 O(1) 而
链表 get(int index) 操作运行时间为 O(n) 。
背后的原因 数组列表 比 LinkedList 更快的是 ArrayList 为其元素使用基于索引的系统，因为它内部使用数组数据结构，另一方面，
链表 不为其元素提供基于索引的访问，因为它从开头或结尾（以较接近者为准）进行迭代以检索指定元素索引处的节点。
insert() 或 add(Object) 操作
插入于 链表 与 ArrayList 相比通常更快。在 LinkedList 中添加或插入是 O(1) 操作。
而在 数组列表, ，如果数组已满，即最坏情况，则需要调整数组大小和将元素复制到新数组的额外成本，这使得 ArrayList 中的添加操作的运行时间为 O(n)，否则为 O(1)。
删除(int)操作
LinkedList 中的删除操作通常与 ArrayList 相同，即在）。
在 链表, ，有两个重载的remove方法。一种是不带任何参数的remove()，它删除列表的头部并以恒定时间O(1)运行。LinkedList 中的另一个重载remove 方法是remove(int) 或remove(Object)，它删除作为参数传递的Object 或int。此方法遍历 LinkedList，直到找到该对象并将其从原始列表中取消链接。因此这个方法的运行时间是 O(n)。
而在 数组列表 remove(int) 方法涉及将元素从旧数组复制到新的更新数组，因此其运行时间为 O(n)。
3.反向迭代器
链表 可以使用 DescendingIterator() 反向迭代，而
中没有递减迭代器() 数组列表 ，所以我们需要编写自己的代码来反向迭代ArrayList。
4.初始容量
如果构造函数没有重载，那么 数组列表 创建一个初始容量为 10 的空列表，同时
链表 仅构造空列表，没有任何初始容量。
5.内存开销
内存开销 链表 与ArrayList相比，LinkedList中的节点需要维护下一个和上一个节点的地址。尽管
在 数组列表 每个索引只保存实际的对象（数据）。
除了上述其他好的论点之外，您还应该注意到 ArrayList 实施 RandomAccess 接口，同时 LinkedList 实施 Queue.
因此，他们以某种方式解决略有不同的问题，效率和行为有所不同（请参阅他们的方法列表）。
数组列表本质上是一个具有添加项目等方法的数组。（您应该使用通用列表来代替）。它是可以通过索引器访问的项目集合（例如 [0]）。它意味着从一个项目到下一个项目的进展。
链表指定从一项到下一项的进展（项 a -> 项 b）。您可以使用数组列表获得相同的效果，但是链接列表绝对说明了前一项应该跟随哪一项。
这取决于您将在列表上执行更多操作。
ArrayList 访问索引值的速度更快。当插入或删除对象时情况会更糟。
要了解更多信息，请阅读任何讨论数组和链表之间差异的文章。
我通常根据在该特定列表上执行的操作的时间复杂性来使用其中一种。
|---------------------|---------------------|--------------------|------------|
| Operation | ArrayList | LinkedList | Winner |
|---------------------|---------------------|--------------------|------------|
| get(index) | O(1) | O(n) | ArrayList |
| | | n/4 steps in avg | |
|---------------------|---------------------|--------------------|------------|
| add(E) | O(1) | O(1) | LinkedList |
| |---------------------|--------------------| |
| | O(n) in worst case | | |
|---------------------|---------------------|--------------------|------------|
| add(index, E) | O(n) | O(n) | LinkedList |
| | n/2 steps | n/4 steps | |
| |---------------------|--------------------| |
| | | O(1) if index = 0 | |
|---------------------|---------------------|--------------------|------------|
| remove(index, E) | O(n) | O(n) | LinkedList |
| |---------------------|--------------------| |
| | n/2 steps | n/4 steps | |
|---------------------|---------------------|--------------------|------------|
| Iterator.remove() | O(n) | O(1) | LinkedList |
| ListIterator.add() | | | |
|---------------------|---------------------|--------------------|------------|
|--------------------------------------|-----------------------------------|
| ArrayList | LinkedList |
|--------------------------------------|-----------------------------------|
| Allows fast read access | Retrieving element takes O(n) |
|--------------------------------------|-----------------------------------|
| Adding an element require shifting | o(1) [but traversing takes time] |
| all the later elements | |
|--------------------------------------|-----------------------------------|
| To add more elements than capacity |
| new array need to be allocated |
|--------------------------------------|
链表的一个重要特征（我在另一个答案中没有读到）是两个列表的串联。对于数组，这是 O(n) （+一些重新分配的开销），对于链表，这只是 O(1) 或 O(2) ;-)
重要的: ：对于Java来说它的 LinkedList 这不是真的！看 Java中有链表的快速连接方法吗？
我已阅读了回复，但在一种情况下，我总是使用 LinkedList 而不是 ArrayList，我想分享以听取意见：
每次我有一个返回从数据库获取的数据列表的方法时，我总是使用 LinkedList。
我的理由是，因为不可能确切地知道我得到了多少结果，所以不会浪费内存（就像在 ArrayList 中，容量和元素的实际数量之间存在差异），并且不会浪费时间尝试复制容量。
就 ArrayList 而言，我同意至少应该始终使用具有初始容量的构造函数，以尽可能减少数组的重复。
ArrayList和LinkedList各有优缺点。
与使用指向下一个节点的指针的 LinkedList 相比，ArrayList 使用连续的内存地址。因此，当您想要在 ArrayList 中查找元素时，比使用 LinkedList 进行 n 次迭代要快。
另一方面，LinkedList 中的插入和删除要容易得多，因为您只需更改指针，而 ArrayList 则意味着对任何插入或删除都使用移位操作。
如果您的应用程序中有频繁的检索操作，请使用 ArrayList。如果频繁插入和删除，请使用 LinkedList。
ArrayList 和 LinkedList 两者都实现 List interface 他们的方法和结果几乎相同。然而，它们之间几乎没有什么区别，根据要求，它们会比另一种更好。
ArrayList 与 LinkedList
1) Search: ArrayList 与搜索操作相比，搜索操作相当快 LinkedList 搜索操作。 get(int index) 在 ArrayList 给出的性能 O(1) 尽管 LinkedList 性能是 O(n).
Reason: ArrayList 为其元素维护基于索引的系统，因为它隐式使用数组数据结构，这使得搜索列表中的元素更快。另一方面 LinkedList 实现双向链表，需要遍历所有元素来查找元素。
2) Deletion: LinkedList 删除操作给出 O(1) 性能同时 ArrayList 给出可变的性能： O(n) 在最坏的情况下（同时删除第一个元素）和 O(1) 在最好的情况下（删除最后一个元素时）。
结论：与ArrayList相比，LinkedList元素删除速度更快。
原因：LinkedList 的每个元素都维护两个指针（地址），它们指向列表中的两个邻居元素。因此，删除只需要更改要删除的节点的两个邻居节点（元素）中的指针位置。而在 ArrayList 中，所有元素都需要移动以填充删除元素创建的空间。
3) Inserts Performance: LinkedList 添加方法给出 O(1) 性能同时 ArrayList 给出 O(n) 在最坏的情况下。原因与删除的解释相同。
4) Memory Overhead: ArrayList 维护索引和元素数据，同时 LinkedList 维护元素数据和邻居节点的两个指针
因此 LinkedList 的内存消耗相对较高。
这些类之间有一些相似之处，如下所示：
- ArrayList和LinkedList都是List接口的实现。
- 它们都维护元素插入顺序，这意味着在显示 ArrayList 和 LinkedList 元素时，结果集将具有与元素插入列表相同的顺序。
- 这两个类都是非同步的，可以使用 Collections.synchronizedList 方法显式地使其同步。
- 这
iterator和listIterator这些类返回的是fail-fast（如果在创建迭代器后的任何时间对列表进行结构修改，除了通过iterator’s自己的删除或添加方法，迭代器将throwAConcurrentModificationException).
什么时候使用LinkedList，什么时候使用ArrayList？
- 如上所述，插入和删除操作提供了良好的性能
(O(1))在LinkedList相比ArrayList(O(n)).因此，如果应用中有频繁添加和删除的需求，那么LinkedList是最好的选择。
- 搜索 （
get method）操作速度很快Arraylist (O(1))但不在LinkedList (O(n))因此，如果添加和删除操作较少，而搜索操作较多，则 ArrayList 将是您的最佳选择。
ArrayList 中的 get(i) 操作比 LinkedList 更快，因为：
数组列表： List 接口的可调整大小的数组实现
链表： List 和 Deque 接口的双向链表实现
对列表进行索引的操作将从开头或结尾遍历列表，以更接近指定索引的为准。
1）底层数据结构
ArrayList 和 LinkedList 之间的第一个区别在于 ArrayList 由 Array 支持，而 LinkedList 由 LinkedList 支持。这将导致性能的进一步差异。
2）LinkedList实现Deque
ArrayList 和 LinkedList 的另一个区别是，除了 List 接口之外，LinkedList 还实现了 Deque 接口，该接口为 add() 和 poll() 以及其他几个 Deque 函数提供先进先出操作。3) 在 ArrayList 中添加元素 在 ArrayList 中添加元素，如果不触发 Array 的大小调整，则为 O(1) 操作，此时则变为 O(log(n))，另一方面，在 ArrayList 中追加元素LinkedList 是 O(1) 操作，因为它不需要任何导航。
4) 从某个位置删除一个元素
为了从特定索引中删除元素，例如通过调用remove(index)，ArrayList执行复制操作，使其接近O(n)，而LinkedList需要遍历到该点，这也使其O(n/2)，因为它可以根据邻近度从任一方向遍历。
5) 迭代ArrayList或LinkedList
对于 LinkedList 和 ArrayList 来说，迭代都是 O(n) 操作，其中 n 是元素的编号。
6) 从某个位置检索元素
get(index) 操作在 ArrayList 中是 O(1)，而在 LinkedList 中是 O(n/2)，因为它需要遍历直到该条目。不过，在 Big O 表示法中，O(n/2) 只是 O(n)，因为我们忽略了其中的常数。
7) 记忆
LinkedList 使用一个包装对象 Entry，它是一个静态嵌套类，用于存储数据以及 next 和 previous 两个节点，而 ArrayList 仅将数据存储在 Array 中。
因此，ArrayList 的内存需求似乎比 LinkedList 少，除非 Array 在将内容从一个 Array 复制到另一个 Array 时执行重新调整大小操作。
如果数组足够大，此时可能会占用大量内存并触发垃圾收集，这会减慢响应时间。
从 ArrayList 与 LinkedList 之间的所有上述差异来看，几乎在所有情况下 ArrayList 都是比 LinkedList 更好的选择，除非您执行频繁的 add() 操作而不是 remove() 或 get() 操作。
修改链表比 ArrayList 更容易，特别是当您从头或尾添加或删除元素时，因为链表内部保留了这些位置的引用，并且可以在 O(1) 时间内访问它们。
换句话说，你不需要遍历链表来到达你想要添加元素的位置，这样的话，加法就变成了 O(n) 操作。例如，在链表中间插入或删除元素。
在我看来，对于 Java 中的大多数实际用途，使用 ArrayList 而不是 LinkedList。
对于 ArrayList 和 LinkedList，remove() 和 insert() 的运行时效率均为 O(n)。然而，线性处理时间背后的原因来自两个截然不同的原因：
在 ArrayList 中，您可以在 O(1) 中获取元素，但实际上删除或插入某些内容会使其变为 O(n)，因为后面的所有元素都需要更改。
在 LinkedList 中，实际到达所需元素需要 O(n) 时间，因为我们必须从头开始，直到到达所需索引。实际上删除或插入是不变的，因为我们只需要更改remove()的1个引用和insert()的2个引用。
两者中哪一个插入和删除速度更快取决于发生的位置。如果我们更接近开头，LinkedList 会更快，因为我们必须遍历相对较少的元素。如果我们更接近末尾，ArrayList 会更快，因为我们在恒定时间内到达那里，并且只需要更改后面的几个剩余元素。当精确地在中间完成时，LinkedList 会更快，因为遍历 n 个元素比移动 n 个值更快。
奖金：虽然 ArrayList 无法使这两个方法的复杂度为 O(1)，但在 LinkedList 中实际上有一种方法可以做到这一点。假设我们想要遍历整个 List，以我们的方式删除和插入元素。通常，您会使用 LinkedList 从每个元素的开头开始，我们也可以使用迭代器“保存”我们正在处理的当前元素。在 Iterator 的帮助下，在 LinkedList 中工作时，remove() 和 insert() 的效率为 O(1)。这是我所知道的 LinkedList 总是比 ArrayList 更好的唯一性能优势。
ArrayList 扩展了 AbstractList 并实现了 List 接口。ArrayList是动态数组。
可以说它基本上是为了克服数组的缺点而创建的
LinkedList 类扩展了 AbstractSequentialList 并实现了 List、Deque 和 Queue 接口。
表现
arraylist.get() 是 O(1) 而 linkedlist.get() 是 O(n)
arraylist.add() 是 O(1) 并且 linkedlist.add() 是 0(1)
arraylist.contains() 是 O(n) 并且linkedlist.contains() 是 O(n)
arraylist.next() 是 O(1) 并且 linkedlist.next() 是 O(1)
arraylist.remove() 是 O(n) 而 linkedlist.remove() 是 O(1)
在数组列表中iterator.remove() 是 O(n)
而在链表中 iterator.remove()是 O(1)
我在这里看到的一个测试只进行一次测试。但我注意到，您需要多次运行这些测试，最终它们的时间会收敛。基本上 JVM 需要预热。对于我的特定用例，我需要添加/删除项目，最后增加到大约 500 个项目。在我的测试中 LinkedList 出来得更快，有链接 LinkedList 大约 50,000 NS 和 ArrayList 大约 90,000 NS...给予或接受。请参阅下面的代码。
public static void main(String[] args) {
List<Long> times = new ArrayList<>();
for (int i = 0; i < 100; i++) {
times.add(doIt());
}
System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}
static long doIt() {
long start = System.nanoTime();
List<Object> list = new LinkedList<>();
//uncomment line below to test with ArrayList
//list = new ArrayList<>();
for (int i = 0; i < 500; i++) {
list.add(i);
}
Iterator it = list.iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
long end = System.nanoTime();
long diff = end - start;
//uncomment to see the JVM warmup and get faster for the first few iterations
//System.out.println(diff)
return diff;
}
