【注】本文译自：Java ArrayList vs LinkedList | Baeldung

1. 概述

对于 collections（汇合），Java 规范库提供了大量可供选择的选项。在这些选项中，有两个驰名的 List 实现，称为 ArrayList 和 LinkedList，每个实现都有本人的属性和用例。
在本教程中，咱们将看到这两者是如何实现的。而后，咱们将为评估每个利用的不同。

2. ArrayList

在外部，ArrayList 应用数组来实现 List 接口 。因为数组在 Java 中是固定大小的，因而 ArrayList 创立一个具备一些初始容量的数组。在此过程中，如果咱们须要存储比默认容量更多的项，它将用一个新的、更大的数组替换该数组。
为了更好地了解它的属性，让咱们依据它的三个次要操作来评估这个数据结构：增加项、通过索引获取项和通过索引删除项。

2.1. 增加

当咱们创立一个空的 ArrayList 时，它会应用默认容量（以后为 10）初始化其后备数组：

在该数组尚未满时增加新我的项目就像将该项调配给特定数组索引一样简略。这个数组索引由以后数组大小决定，因为咱们实际上是附加到列表中：

backingArray[size] = newItem;
size++;

因而，在最佳和个别状况下，加法操作的工夫复杂度为 O(1)，这十分快。然而，随着后备数组变满，增加实现的效率会升高：

要增加新我的项目，咱们应该首先初始化一个容量更大的全新数组，并将所有现有我的项目复制到新数组中 。只有在复制以后元素后，咱们能力增加新我的项目。因而，在最坏的状况下工夫复杂度为 O(n)，因为咱们必须先复制 n 个元素。
从实践上讲，增加新元素的运行工夫为摊销常数。也就是说，增加 n 个元素须要 O(n) 工夫。然而，因为复制开销，某些单次增加可能体现不佳。

2.2. 按索引拜访

通过索引拜访项是 ArrayList 的真正亮点。要检索下标为 i 的项，咱们只须要返回位于后备数组中第 i 个下标的项。因而，通过索引操作拜访的工夫复杂度始终为 O(1)。

2.3. 通过索引删除

假如咱们要从 ArrayList 中删除索引 6，它对应于咱们的后备数组中的元素 15：

将所需元素标记为已删除后，咱们应该将其后的所有元素向后挪动一个索引。显然，元素越凑近数组的结尾，咱们应该挪动的元素就越多。因而，工夫复杂度在最佳状况下为 O(1)，在均匀和最坏状况下为 O(n)。

2.4. 利用和限度

. 通常，当须要 List 实现时，ArrayList 是许多开发人员的默认抉择。事实上，当读取次数远远超过写入次数时，这实际上是一个理智的抉择 。
有时咱们须要同样频繁的读取和写入。如果咱们的确预计了可能我的项目的最大数量，那么应用 ArrayList 依然有意义。如果是这种状况，咱们能够应用初始容量初始化 ArrayList：

int possibleUpperBound = 10_000;
List<String> items = new ArrayList<>(possibleUpperBound);

这种预计能够避免大量不必要的复制和数组调配。

此外，数组由 Java 中的 int 值索引。因而，在 Java 数组中存储超过 2 的 32 次方个元素是不可能的，因而，在 ArrayList 中也是如此。

3. LinkedList

LinkedList，顾名思义，应用链接节点的汇合来存储和检索元素。例如，以下是增加四个元素后的 Java 实现：

每个节点保护两个指针：一个指向下一个元素，另一个指向前一个元素。对此进行扩大，双向链表有两个指向第一项和最初一项的指针 。
同样，让咱们依据雷同的基本操作来评估这个实现。

3.1. 增加

为了增加新节点，首先，咱们应该将以后最初一个节点链接到新节点：

而后更新最初一个指针：

因为这两个操作都很简略，因而加法操作的工夫复杂度始终为 O(1)。

3.2. 通过索引拜访

LinkedList 与 ArrayList 不同，不反对疾速随机拜访。因而，为了按索引查找元素，咱们应该手动遍历列表的某些局部。

在最好的状况下，当申请的我的项目靠近列表的结尾或结尾时，工夫复杂度将与 O(1) 一样快。然而，在均匀和最坏状况下，咱们可能会以 O(n) 的拜访工夫完结，因为咱们必须一个接一个地查看许多节点。

3.3. 通过索引删除

为了删除一项，咱们应该首先找到申请的项，而后从列表中勾销它的链接。因而，拜访工夫决定了工夫复杂度——即在最佳状况下为 O(1)，在均匀和最坏状况下为 O(n)。

3.4. 利用

当增加率远高于读取率时，LinkedLists更适宜。
此外，当大多数时候咱们想要第一个或最初一个元素时，它能够用于读取密集的场景。值得一提的是，LinkedList 还实现了 Deque 接口——反对对汇合两端的高效拜访。
通常，如果咱们晓得它们的实现差别，那么咱们能够轻松地为特定用例抉择一个。
例如，假如咱们将在相似列表的数据结构中存储大量工夫序列事件。咱们晓得咱们每秒都会收到突发事件。
此外，咱们须要定期检查所有事件并提供一些统计数据。对于此用例，LinkedList 是更好的抉择，因为增加速率远高于读取速率。
此外，咱们会读取所有我的项目，因而咱们无奈超过 O(n) 下限。

4. 论断

在本教程中，咱们首先深入研究了 ArrayList 和 LinkLists 如何在 Java 中实现。
咱们还评估了其中每一个的不同用例。