ArrayList：简介

ArrayList 是 List 接口最广泛使用的实现类。ArrayList 的一些主要特性包括：

1. 元素按照插入顺序存储。
2. 允许存储重复元素。
3. ArrayList 也支持存储 null 元素。

ArrayList 的内部实现

ArrayList 使用可动态扩容的数组来存储数据。在 Java 8 之前，创建 ArrayList 时会默认在内部创建一个大小为 10 的数组；而现在，创建 ArrayList 时初始会创建一个大小为 0 的数组，只有当插入第一个元素时，数组才会扩容至大小为 10。这种机制称为延迟初始化（lazy initialization），能够有效节省内存。

在向 ArrayList 添加元素前，会先检查其容量。如果内部数组已满，则会创建一个新的数组，其大小为原数组大小的 $\lgroup n+\frac{n}{2}+1\rgroup$（例如，若原容量为 10，则新数组大小为 16）。随后，旧数组中的所有元素会被复制到新数组中。这一扩容过程耗时较长。

ArrayList 操作的时间复杂度

下面我们来看 ArrayList 各种操作的时间复杂度。

添加元素

由于 ArrayList 底层基于数组实现，大多数情况下添加元素的时间复杂度为 $O(1)$。但如果 ArrayList 容量已满需要扩容，则需创建新数组并复制元素，此时时间开销较大。

删除元素

删除操作在最坏情况下的时间复杂度为 $O(n)$，最好情况下为 $O(1)$。ArrayList 提供了两个重载版本的 remove() 方法：

1. 第一个方法接收待删除元素的索引作为参数。通过索引查找元素的时间复杂度为 $O(1)$，但删除后需要将后续元素向前移动。因此，若删除的是最后一个元素，则时间复杂度为 $O(1)$；否则为 $O(n)$。
2. 第二个方法接收待删除的具体元素作为参数。该方法会从数组起始位置开始遍历，查找该元素的第一次出现位置并删除，整个过程的时间复杂度为 $O(n)$。

获取元素

通过索引从数组中获取元素是一个 $O(1)$ 的常数时间操作，因此从 ArrayList 中根据索引获取元素也是常数时间。

创建 ArrayList 的方式

创建 ArrayList 有三种方法：

使用无参构造函数

无参构造函数不接受任何参数，创建一个初始大小为 0 的列表。使用默认构造函数创建 ArrayList 的语法如下：

1List list = new ArrayList();

使用指定初始容量的构造函数

可以在创建 ArrayList 时指定初始容量。这样做的好处是，如果我们预知 ArrayList 至少要存储 100 个元素，就可以直接初始化容量为 100，从而避免频繁扩容带来的性能开销。

1List list = new ArrayList(50);

基于已有集合创建

还可以通过已有的集合来创建 ArrayList。新创建的 ArrayList 将按原有集合中的顺序包含其全部元素。

1List list = new ArrayList(oldList);