ArrayList与Array和List的区别

Question

我一直在编程，最近开始学习更纯粹的计算机科学知识（为了面试）。我知道数组和链表数据结构之间的区别，但现在我开始使用Java时看到了这个ArrayList，我很难理解它。

网络搜索只是向我展示如何使用它们和何时使用它们（每个的好处），但没有回答我的问题：

什么是ArrayList？ 我的假设是它是一个列表，维护着每个元素的内存引用，使其也能像数组一样运行。

我还有一种感觉，既然Java是开放的，我应该能够查看类定义，但我还没弄清楚如何做到这一点。

谢谢！

- Doug Mead

---

你试过谷歌搜索ArrayList吗？ - Eran

是的，我只得到了有关如何使用它、何时使用它以及方法/属性是什么的结果。我想知道底层数据结构是什么样子的。它是一个数组还是一个列表或者两者都有？ - Doug Mead

根据逻辑，我认为ArrayList是List的更具体版本。它结构上类似于List，但具有类似于数组方法的方法。 - user4529954

你可以在你的IDE中查看ArrayList源代码（例如在IntelliJ中，选中代码中的ArrayList，然后按CTRL + 左键单击）。你会发现ArrayList本质上是一个包装过的Object[]，并且还有很多方便的插入、删除等方法。 - Paul Boddington

谢谢 @pbabcdefp!! 这就是我在找的东西！ - Doug Mead

Answer 1

一个ArrayList是一个由数组直接支持的列表。更具体地说，它是由可动态调整大小的数组支持的。您可以在源代码中了解更多信息; 有一些相当不错的注释。

这很重要的原因是因为 LinkedList 的实现方式 - 作为节点和其他节点的引用的传统集合。这对索引和遍历产生性能影响，而对于ArrayList，由于它是由数组支持的，所有需要做的就是索引到特定的数组中以检索值。

- Makoto

---

那么，如果它由数组支持，这是否意味着添加/插入/删除问题标签很耗费成本，还是有一些优化？我猜动态数组是我接下来要学习的主题！谢谢！ - Doug Mead

取决于您的容量所在的位置。如果数组需要调整大小（如果您超出容量或接近阈值），则可能会产生O(n)的成本，但如果您处于中间某个位置，则为O(1)。删除将是O(n-i)，因为您必须将剩余的值向左移动以填充缺失的值。 - Makoto

在数组末尾插入新元素的摊销成本是恒定的，删除它们也是如此。然而，如果您从数组中间插入/删除元素，则需要支付线性成本，因为您平均需要移动n / 2个元素。 - 5gon12eder

谢谢！我喜欢这个解释每个方法的方式。 - Doug Mead

是的 - 这是Javadoc，它正在从与API使用相同的源中提取信息（https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html）。这显示了行内注释，因为它们包含更多有关实现细节的信息。 - Makoto

Answer 2

我喜欢把它看作是一种数据结构，让你既能享受数组的快速访问索引，又能享受列表的无限增长。当然，总会有一些权衡需要考虑。 ArrayList 实际上是一个数组的包装器。每当数组大小到达末尾时，都会创建一个新的大小为原来两倍的数组，并将原始数组中的所有数据复制到新数组中。

来自 Java 文档： List接口的可调整大小数组实现。实现了所有可选列表操作，并允许包括null在内的所有元素。除了实现List接口外，该类还提供了用于操作内部用于存储列表的数组大小的方法。（该类大致相当于Vector，但不同的是它是非同步的）size、isEmpty、get、set、iterator和listIterator操作以常数时间运行。添加操作以摊销常数时间运行，即添加n个元素需要O(n)时间。所有其他操作均以线性时间运行（粗略地说）。与LinkedList实现相比，常数因子较低。

每个ArrayList实例都有一个容量。容量是用于存储列表中元素的数组的大小。它始终至少与列表大小一样大。当元素添加到ArrayList时，其容量会自动增长。增长策略的详细信息未指定，除了添加元素具有固定的摊销时间成本之外。

应用程序可以使用ensureCapacity操作在添加大量元素之前增加ArrayList实例的容量。这可能会减少增量重新分配的数量。

这使得大多数操作像使用数组一样具有O(1)的访问速度。但是，偶尔需要通过插入操作来支付这种性能，这需要花费更长的时间。

这被称为摊销复杂度。每个操作只需要O(1)，除了那些需要将数组大小加倍的时候。在这些时候，您需要支付O(n)，但如果您平均n次操作，平均所需的时间只有O(1)而不是O(n)。

让我们举个例子:

我们有一个大小为100（n=100）的数组。您进行了100次插入操作（到不同的索引），每个操作仅需要 O(1)，当然，所有通过索引获取元素的操作也需要 O(1)（因为这是一个数组）。在第101次插入时，数组已经没有更多的容量，所以ArrayList将创建一个新的大小为200的数组，将所有值复制到其中（O(n) 操作），然后再插入第101个项目。直到填满数组为止，所有操作都需要 O(1)。

- Avi

---

谢谢！我以前没听说过分摊分析。不过这很有道理。看起来在时间复杂度中使用它是有意义的，但在空间方面，你经常会得到O(2n)吧？这是假设对象不是非常大且设备可以处理吗？我想我读的书更多的是理论而不是实践。我不打算在我的移动应用程序中拥有10^20个元素，而计算机科学书籍则避免使用2倍内存。 - Doug Mead

在复杂度分析中，O(2n) 和 O(n) 是相同的。如果你正在谈论 Android 应用程序，你不应该担心 ArrayList 的开销内存，你很可能有足够的空间。除非你正在创建数十亿个对象。 - Avi

那很有道理。再次感谢！有点脱离主题，但是在面试中O(n)是发音为“大写字母O与n”还是其他方式呢？ - Doug Mead

我认为你会说Oh-En。但是我不是以英语为母语的人，所以我真的不确定 :) - Avi