JavaArrayList和LinkedList

【注】本文翻译自：JavaArrayListvsLinkedList|贝尔东1。概述对于集合（collections），Java标准库提供了大量可供选择的选项。在这些选项中有两个著名的列表实现，称为ArrayList和LinkedList，每个都有自己的属性和用例。在本教程中，我们将看到这两者是如何实现的。然后，我们将评估每个应用程序的差异。2.ArrayListArrayList在内部使用数组来实现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：intpossibleUpperBound=10_000;Listitems=newArrayList<>(possibleUpperBound);这种估计可以防止很多不必要的复制和数组分配。还有，数组在Java中是通过int值来索引的。因此，不可能在Java数组中存储超过232个元素，因此在ArrayList中也是如此。3.LinkedListLinkedList，顾名思义，就是用一组相互链接的节点来存储和检索元素。例如，这是添加四个元素后的Java实现：每个节点维护两个指针：一个指向下一个元素，一个指向前一个元素。对此进行扩展，双向链表有两个指向第一项和最后一项的指针。同样，让我们??根据相同的基本操作评估此实现。3.1.添加为了添加一个新节点，首先，我们应该将当前最后一个节点链接到新节点：然后更新最后一个指针：由于这两个操作都很简单，所以加法操作的时间复杂度总是O(1)。3.2.通过索引访问LinkedList与ArrayList不同，它不支持快速随机访问。因此，为了通过索引查找元素，我们应该手动遍历列表的某些部分。在最好的情况下，当请求的项目接近列表的开头或结尾时，时间复杂度将与O(1)一样快。然而，在平均和最坏的情况下，我们可能会以O(n)的访问时间结束，因为我们必须一个接一个地检查许多节点。3.3.按索引删除要删除一个项目，我们应该首先找到请求的项目，然后将其从列表中取消链接。因此，访问时间决定了时间复杂度——即最好情况下为O(1)，平均和最坏情况下为O(n)。3.4.当添加速率远高于读取速率时，应用程序链表更合适。此外，当大多数时候我们需要第一个或最后一个元素时，它可以用于读取密集型场景。值得一提的是，LinkedList还实现了Deque接口——支持对集合两端的高效访问。通常，如果我们知道它们的实现差异，那么我们可以轻松地为特定用例选择一个。例如，假设我们要将大量时间序列事件存储在类似列表的数据结构中。我们知道我们每秒都会爆发。此外，我们需要定期检查所有事件并提供一些统计信息。LinkedList是此用例的更好选择，因为添加速率远高于读取速率。此外，我们读取了所有项目，因此我们不能超过O(n)界限。4.结论在本教程中，我们首先深入探讨了ArrayList和LinkLists是如何在Java中实现的。我们还评估了它们每个的不同用例。