ArrayList与数组和列表

Question

我已经进行了很多编程工作，最近开始学习更多纯粹的计算机科学主题（用于工作面试）。

我知道Array和LinkedList数据结构之间的区别，但是现在我已经开始使用Java，我看到了这个ArrayList，在概念上我遇到了麻烦。

网络搜索仅真正向我展示了如何使用它们以及何时使用它们（每种优点），但是没有任何东西可以回答我的问题：

什么是ArrayList？我的假设是，它是一个维护对每个元素的内存引用的列表，使其也可以像数组一样工作。

自从Java开放以来，我也有一种感觉，我应该能够看一下Class的定义，但是还没有弄清楚该怎么做。

谢谢！

Answer 1

我喜欢将其视为一个数据结构，可以让您享受两个世界，快速访问索引（如数组）和列表的无限增长。当然，总会有取舍。

ArrayList实际上是数组的包装器。每次数组大小结束时，都会创建一个两倍大小的新数组，并将原始数组中的所有数据复制到新数组中。

从Java文档中：

List接口的可调整大小数组实现
。实现所有可选的列表操作，并允许所有元素，包括null。除了实现List接口之外，此类还提供一些方法来操纵内部用于存储列表的数组的大小。（该类大致上与Vector等效，但它是不同步的。）
size，isEmpty，get，set，iterator和listIterator操作在恒定时间内运行 。的
在分期常量时间，即增加操作运行时，添加N元素需要O（n）的时间
。所有其他操作均以线性时间运行（大致而言）。与LinkedList实现相比，常数因子较低。

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

应用程序可以通过使用sureCapacity操作在添加大量元素之前增加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个项目。在将数组填充为200个项目之前，所有操作都将采用 O（1） 。