Java 中 Arraylist和LinkedList

1. 概述

当涉及到集合 时，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. 按索引删除

为了[删除](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedList.html#remove(int) 一个项目，我们应该首先找到请求的项目，然后从列表中取消链接。因此，访问时间决定了时间复杂度——也就是说，在最佳情况下为O(1)，在最坏情况下平均为O(n)。

3.4. 应用

当添加率远高于读取率时，LinkedLists更适合。

此外，当大多数时候我们想要第一个或最后一个元素时，它可以用于读取繁重的场景。值得一提的是，LinkedList还实现了*Deque *接口——支持对集合两端的高效访问。

一般来说，如果我们知道它们的实现差异，那么我们可以很容易地为特定的用例选择一个。

例如，假设我们将在类似列表的数据结构中存储大量时间序列事件。我们知道我们每秒都会收到突发的事件。

此外，我们需要定期检查所有事件并提供一些统计数据。对于这个用例，LinkedList是更好的选择，因为添加率远高于读取率。

此外，我们会读取所有项目，因此我们无法超过*O(n)*上限。