ArrayList 与数组和列表的比较

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

我知道数组和 LinkedList 数据结构之间的区别，但现在我已经开始使用 Java，我看到了这个 ArrayList，但我很难概念化它。

网络搜索只真正向我展示了如何使用它们以及何时使用它们（各自的好处），但没有任何东西可以回答我的问题：

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

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

Thanks!

我喜欢将其视为一种数据结构，让您享受两个世界：像数组一样快速访问索引，以及列表的无限增长。当然，总是需要权衡。

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

来自java文档：

List 接口的可调整大小的数组实现。实现所有 可选列表操作，并允许所有元素，包括 null。在 除了实现 List 接口之外，该类还提供 操作内部使用的数组大小的方法 存储列表。 （这个类大致相当于 Vector，除了 它是不同步的。）大小、isEmpty、get、set、迭代器和 listIterator 操作以恒定时间运行. The 添加操作运行 在摊余常数时间内，即添加n个元素需要O(n) 时间。所有其他操作都以线性时间运行（大致为 请讲）。与常数因子相比，常数因子较低 链表实现。

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

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

这允许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).