ArrayList 与数组和列表
ArrayList vs Array and List
我已经进行了相当多的编程，最近开始学习更多纯计算机科学主题（用于工作面试）。
我知道 Array 和 LinkedList 数据结构之间的区别，但现在我已经开始使用 Java 我看到这个 ArrayList，但我在概念化时遇到了困难。
网络搜索只真正告诉我如何使用它们以及何时使用它们（每个的好处），但没有任何东西可以回答我的问题：
什么是 ArrayList？我的假设是它是一个列表，维护每个元素的内存引用，使其也可以像数组一样工作。
自从Java开放以来，我也有一种感觉，我应该可以查看Class的定义，但也没有想出如何去做。
谢谢！
ArrayList 是一个直接由数组支持的列表。更具体地说，它由一个动态调整大小的数组支持。您可以在 its source code 中阅读更多相关信息；有一些很好的评论。
之所以如此重要，是因为 LinkedList 是如何实现的——作为传统的节点集合和对其他节点的引用。这对索引和遍历的性能有影响，而对于 ArrayList，因为它由数组支持，所以需要做的就是索引到特定数组以检索值。
我喜欢将它视为一种数据结构，让您享受两个世界，像使用数组一样快速访问索引和列表的无限增长。当然，总有取舍。
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).
我已经进行了相当多的编程，最近开始学习更多纯计算机科学主题（用于工作面试）。
我知道 Array 和 LinkedList 数据结构之间的区别，但现在我已经开始使用 Java 我看到这个 ArrayList，但我在概念化时遇到了困难。
网络搜索只真正告诉我如何使用它们以及何时使用它们（每个的好处），但没有任何东西可以回答我的问题：
什么是 ArrayList？我的假设是它是一个列表，维护每个元素的内存引用，使其也可以像数组一样工作。
自从Java开放以来，我也有一种感觉，我应该可以查看Class的定义，但也没有想出如何去做。
谢谢！
ArrayList 是一个直接由数组支持的列表。更具体地说，它由一个动态调整大小的数组支持。您可以在 its source code 中阅读更多相关信息；有一些很好的评论。
之所以如此重要，是因为 LinkedList 是如何实现的——作为传统的节点集合和对其他节点的引用。这对索引和遍历的性能有影响，而对于 ArrayList，因为它由数组支持，所以需要做的就是索引到特定数组以检索值。
我喜欢将它视为一种数据结构，让您享受两个世界，像使用数组一样快速访问索引和列表的无限增长。当然，总有取舍。
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).