【注】正文翻译： https://www.baeldung.com/Java -阵列列表-链接列表

Java ArrayList 与 LinkedList

对于

1.概述

集合，Java标准库有很多选择。 这些选项有两个有名的列表实现： ArrayList和LinkedList，每个列表都有自己的属性和用例。

在本教程中，我们将看一下这两者是如何实现的。 然后，评估各APP之间的差异。

在

2.ArrayList

内部，ArrayList使用数组实现List接口。 由于数组在Java中大小固定，因此ArrayList将创建具有初始容量的数组。 如果在此过程中需要存储比缺省值更多的项目，请将数组替换为新的大数组。

为了更好地了解属性，让我们根据以下三个主要操作来评估此数据结构：添加条目、从索引中获取条目和从索引中删除条目。

2.1. 添加

创建空的ArrayList时，将使用默认容量(当前为10 )初始化备份数组。

在数组未满的情况下添加新项目就像将项目指定给特定的数组索引一样简单。 该数组索引实际上是添加到列表中的，因此由当前数组大小决定。

烘焙阵列=网络；

大小；

因此，在最优和一般情况下，加法操作的时间复杂度为o(1)，这非常快。 但是，如果备份数组已满，则添加实现的效率会下降。

要添加新项目，必须首先初始化新的大型数组，然后将所有现有项目复制到新数组中。 只有在复制当前元素之后，才能添加新项目。 因此，最坏的情况是，时间的复杂度为o(n )。 因为必须先复制n个元素。

理论上，增加新元素的执行时间是摊销常数。 也就是说，添加n个元素需要o(n )时间。 但是，由于复制的开销，一次添加可能不会成功。

从

2.2.按索引访问

索引访问条目是ArrayList的真正亮点。 要获取下标为I的项目，只需返回备份数组第I个下标中的项目。 因此，通过索引操作进行访问的时间复杂度总是o(1)。

假设要从

2.3. 通过索引删除

数组列表中删除索引6。 它对应于备份数组的元素15。

将所需元素标记为已删除后，所有后续元素都必须向后移动一个索引。 很明显，元素越接近数组的开头，需要移动的元素就越多。 因此，时间复杂度在最合适的情况下为o(1)，在平均和最坏的情况下为o ) ) n )。

2.4.应用和限制

.通常，在需要实现List的情况下，ArrayList是许多开发人员的默认选择。 事实上，如果读取次数远远超过写入次数，这实际上是明智的选择。

有时需要进行同样频繁的读取和写入。 如果您确实估计了可能的最大项目数，使用ArrayList还是有意义的。 在这种情况下，可以使用初始容量初始化ArrayList。

可承诺上行链路=10 _ 000；

liststringitems=新阵列列表(可移植上行链路；

这样的估计可以防止大量不必要的复制和数组分配。

此外，数组按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 中实现。

我们还评估了其中每一个的不同用例。