1. 概述
在集合方面，Java 标准库提供了许多选项供您选择。在这些选项中，有两个著名的List实现，称为ArrayList和LinkedList，每个都有自己的属性和用例。
在本教程中，我们将看到这两个是如何实际实现的。然后，我们将为每个应用程序评估不同的应用程序。
2.数组列表
在内部，ArrayList正在使用数组来实现List接口。由于数组在 Java 中是固定大小的，因此 ArrayList会创建一个具有一定初始容量的数组。在此过程中，如果我们需要存储比默认容量更多的项目，它将用一个新的、更宽敞的数组替换该数组。
为了更好地理解它的属性，让我们根据它的三个主要操作来评估这个数据结构：添加项目、按索引获取项目和按索引删除。以下是它的继承与实现链关系图
2.1. 添加
当我们创建一个空的ArrayList 时，它会用默认容量（当前为 10）初始化其后备数组：
在该数组尚未满时添加新项就像将该项分配给特定的数组索引一样简单。此数组索引由当前数组大小决定，因为我们实际上是附加到列表中：
backingArray[size] = newItem;
size++;
因此，在最佳和平均情况下，添加操作的时间复杂度为O（1），这非常快。但是，当后备阵列已满时，add 实现的效率会降低：
要添加一个新项目，我们应该首先初始化一个容量更大的全新数组，并将所有现有项目复制到新数组中。只有在复制当前元素后，我们才能添加新项目。因此，在最坏的情况下，时间复杂度为O（n），因为我们必须首先复制n 个元素。
从理论上讲，添加新元素在摊销常数时间内运行。也就是说，添加 n个元素需要O（n） 时间。但是，由于副本开销，某些单个添加可能会表现不佳。
2.2. 按索引访问
通过索引访问项目是ArrayList真正闪耀的地方。要检索索引 i 处的项目，我们只需要返回驻留在我千后备阵列中的索引。因此，索引操作访问的时间复杂度始终为O（1）。
2.3. 按索引删除
假设我们要从ArrayList 中删除索引 6，它对应于后备数组中的元素 15：
将所需元素标记为已删除后，我们应该将其之后的所有元素移回一个索引。显然，元素越靠近数组的开头，我们应该移动的元素就越多。因此，在最佳情况下，时间复杂度为 O（1），在平均和最差情况下为O（n）。
2.4. 应用和限制
通常，ArrayList是许多开发人员在需要List实现时的默认选择。事实上，当读取次数远远超过写入次数时，这实际上是一个明智的选择。
有时我们需要同样频繁的读取和写入。如果我们确实估计了可能项目的最大数量，那么使用ArrayList 仍然有意义。如果是这种情况，我们可以使用初始容量初始化ArrayList：
int possibleUpperBound = 10_000;
List
这种估计可以防止大量不必要的复制和数组分配。
此外数组在 Java 中按int值进行索引。因此，不可能存储超过232元素在 Java 数组中，因此在ArrayList 中.
3.链接列表
顾名思义，LinkedList使用链接节点的集合来存储和检索元素。例如，以下是添加四个元素后 Java 实现的外观：
每个节点维护两个指针：一个指向下一个元素，另一个指向前一个元素。在此基础上展开，双向链表有两个指向第一个和最后一个项目的指针。
同样，让我们根据相同的基本操作来评估此实现。以下是它的继承与实现链关系图
3.1. 添加
为了添加一个新节点，首先，我们应该将当前最后一个节点链接到新节点：
然后更新最后一个指针：
由于这两个操作都是微不足道的，因此添加操作的时间复杂度始终为O（1）。
3.2. 按索引访问
与ArrayList 相反，LinkedList 不支持快速随机访问。因此，为了按索引查找元素，我们应该手动遍历列表的某些部分。
在最好的情况下，当请求的项目接近列表的开头或结尾时，时间复杂度将与O（1） 一样快。但是，在平均和最坏的情况下，我们最终可能会得到O（n） 访问时间，因为我们必须一个接一个地检查许多节点。
3.3. 按索引删除
为了删除一个项目，我们应该首先找到请求的项目，然后将其从列表中取消链接。因此，访问时间决定了时间复杂度——即在最佳情况下为 O（1），在平均情况下和最坏情况下为O（n）。
3.4. 应用
当添加率远高于读取率时，LinkedLists更合适。
此外，当大多数时候我们需要第一个或最后一个元素时，它可以在读取密集型场景中使用。值得一提的是，LinkedList还实现了Deque接口——支持对集合两端的高效访问。
通常，如果我们知道它们的实现差异，那么我们可以轻松地为特定用例选择一个。
例如，假设我们要在类似列表的数据结构中存储大量时间序列事件。我们知道我们每秒都会收到突发事件。
此外，我们需要定期一个接一个地检查所有事件并提供一些统计数据。对于这个用例，LinkedList是更好的选择，因为添加率远高于读取率。
此外，我们将读取所有项目，因此我们无法超越O（n） 上限。
好文阅读
发表评论