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

image

1. 概述

对于 collections （集合），Java 标准库提供了大量可供选择的选项。在这些选项中，有两个著名的 List 实现，称为 ArrayList 和 LinkedList，每个实现都有自己的属性和用例。
在本教程中，我们将看到这两者是如何实现的。然后，我们将为评估每个应用的不同。

2. ArrayList

在内部，ArrayList 使用数组来实现 List 接口。由于数组在 Java 中是固定大小的，因此 ArrayList 创建一个具有一些初始容量的数组。在此过程中，如果我们需要存储比默认容量更多的项，它将用一个新的、更大的数组替换该数组。
为了更好地理解它的属性，让我们根据它的三个主要操作来评估这个数据结构：添加项、通过索引获取项和通过索引删除项。

2.1. 添加

当我们创建一个空的 ArrayList 时，它会使用默认容量（当前为 10）初始化其后备数组：

image

在该数组尚未满时添加新项目就像将该项分配给特定数组索引一样简单。这个数组索引由当前数组大小决定，因为我们实际上是附加到列表中：

backingArray[size] = newItem;
size++;

因此，在最佳和一般情况下，加法操作的时间复杂度为 O(1)，这非常快。但是，随着后备数组变满，添加实现的效率会降低：

image

要添加新项目，我们应该首先初始化一个容量更大的全新数组，并将所有现有项目复制到新数组中。只有在复制当前元素后，我们才能添加新项目。因此，在最坏的情况下时间复杂度为 O(n)，因为我们必须先复制 n 个元素。
从理论上讲，添加新元素的运行时间为摊销常数。也就是说，添加 n 个元素需要 O(n) 时间。但是，由于复制开销，某些单次添加可能表现不佳。

2.2. 按索引访问

通过索引访问项是 ArrayList 的真正亮点。要检索下标为 i 的项，我们只需要返回位于后备数组中第 i 个下标的项。因此，通过索引操作访问的时间复杂度始终为 O(1)。

2.3. 通过索引删除

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

image

将所需元素标记为已删除后，我们应该将其后的所有元素向后移动一个索引。显然，元素越靠近数组的开头，我们应该移动的元素就越多。因此，时间复杂度在最佳情况下为 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 实现：

image

每个节点维护两个指针：一个指向下一个元素，另一个指向前一个元素。对此进行扩展，双向链表有两个指向第一项和最后一项的指针。
同样，让我们根据相同的基本操作来评估这个实现。

3.1. 添加

为了添加新节点，首先，我们应该将当前最后一个节点链接到新节点：

image

然后更新最后一个指针：

image

由于这两个操作都很简单，因此加法操作的时间复杂度始终为 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 中实现。
我们还评估了其中每一个的不同用例。