java - ArrayList 与数组和列表的比较

Question

我已经编程很长时间了，最​​近开始学习更多纯粹的计算机科学主题(用于工作面试)。

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

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

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

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

谢谢!

Answer 1

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

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

来自java文档:

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.) The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

这允许 O(1) 访问大多数操作，就像使用数组一样。有时您需要为这种性能付出代价，因为插入操作需要花费更长的时间。

这称为amortized复杂。当您需要将数组大小加倍时，每个操作仅需要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)。