Java数据结构之ArrayList
一、ArrayList 是什么？
ArrayList是一个可动态扩容的数组容器，实现了List接口，底层基于对象数组实现。
它解决了普通数组长度固定的问题，允许你在运行时动态添加、删除元素。
import java.util.ArrayList;ArrayList<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
System.out.println(list); // [Java, Python]二、核心特性
| 特性 | 说明 |
|---|---|
| 有序 | 元素按插入顺序存储 |
| 可重复 | 允许重复元素 |
| 索引访问 | 支持通过索引（0-based）快速访问 |
| 线程不安全 | 非同步，多线程需手动同步或使用 Collections.synchronizedList |
| 允许 null | 可以存储 null 值 |
| 自动扩容 | 当容量不足时自动增长（通常1.5倍） |
三、底层结构：基于数组
ArrayList 的本质是一个动态数组。
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {transient Object[] elementData; // 存储元素的底层数组（非私有是为了序列化优化）private int size; // 当前元素个数
}elementData：是一个Object[]数组，用来存放元素。size：记录当前实际存储的元素个数，不等于数组长度（elementData.length）。
所以
ArrayList支持随机访问（Random Access），时间复杂度 O(1)。
四、构造方法
1. 无参构造（最常用）
ArrayList<String> list = new ArrayList<>();
// 初始容量为 0，第一次 add 时才扩容为 10（JDK 1.8+ 懒加载）2. 指定初始容量
ArrayList<String> list = new ArrayList<>(20); // 初始容量为203. 从集合构造
List<String> copy = new ArrayList<>(otherList);提示：如果预估元素数量，建议指定初始容量，避免频繁扩容带来的性能开销。
五、添加元素：add(E e)
list.add("Hello");执行流程：
- 检查是否需要扩容
ensureCapacityInternal(size + 1)
- 将元素放入
elementData[size] - size++
扩容机制（关键！）
// 扩容公式：新容量 = 旧容量 + 旧容量右移1位（即 1.5倍）
int newCapacity = oldCapacity + (oldCapacity >> 1);例如：
- 从 10 → 15 → 22 → 33 → 49 → ...
扩容会触发
Arrays.copyOf()，创建新数组并复制数据，时间复杂度 O(n)，所以应尽量避免频繁扩容。
六、随机访问 vs 插入/删除
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
get(index) | O(1) | 直接通过数组下标访问 |
set(index, e) | O(1) | 修改指定位置元素 |
add(e) | 均摊 O(1) | 尾部添加，偶尔扩容 O(n) |
add(index, e) | O(n) | 需要移动后续元素 |
remove(index) | O(n) | 需要移动后续元素 |
contains(e) | O(n) | 需要遍历查找 |
所以：ArrayList 适合读多写少、尾部操作多的场景。
七、删除元素
list.remove(0); // 按索引删除
list.remove("Java"); // 按对象删除（删除第一个匹配项）- 删除后会将后面的元素向前移动。
- 不会自动缩容（除非手动调用
trimToSize()）。
八、遍历方式（推荐与陷阱）
推荐方式：
// 1. 增强for（最常用）
for (String s : list) { ... }// 2. 迭代器（安全删除）
Iterator<String> it = list.iterator();
while (it.hasNext()) {if (it.next().equals("delete")) {it.remove(); // 安全删除}
}// 3. Stream（函数式）
list.stream().forEach(System.out::println);错误方式（并发修改异常）：
for (int i = 0; i < list.size(); i++) {if (list.get(i).equals("bad")) {list.remove(i); // 可能出错或漏删}
}问题：删除后索引错位，且会触发
ConcurrentModificationException（fail-fast 机制）。
九、fail-fast 机制
ArrayList 在迭代过程中如果被其他线程或当前线程修改，会抛出 ConcurrentModificationException。
modCount++; // 修改次数计数器迭代器在每次 next() 前会检查 modCount == expectedModCount，不一致就抛异常。
解决方案：使用
Iterator.remove()或CopyOnWriteArrayList（并发场景）。
十、ArrayList vs 数组 vs LinkedList（下期说LinkedList）
| 对比项 | 数组 | ArrayList | LinkedList |
|---|---|---|---|
| 大小 | 固定 | 动态 | 动态 |
| 访问速度 | O(1) | O(1) | O(n) |
| 插入/删除 | O(n) | O(n) | O(1)（已知位置） |
| 内存开销 | 小 | 中等 | 大（双向指针） |
| 底层结构 | 连续数组 | 对象数组 | 双向链表 |
| 是否支持随机访问 | 是 | 是 | 是（但慢） |
十一、一些理论知识
ArrayList 扩容机制？
答：初始容量10（懒加载），每次扩容为
1.5倍，使用Arrays.copyOf复制。如何实现线程安全的 ArrayList？
答：
Collections.synchronizedList(new ArrayList<>())或使用CopyOnWriteArrayList。ArrayList 和 Vector 的区别？
Vector是线程安全的（方法加synchronized），但性能差；ArrayList非线程安全。如何删除 ArrayList 中的重复元素？
List<String> distinct = new ArrayList<>(new LinkedHashSet<>(list));
总结：ArrayList 是：
- 底层是
Object[]数组，支持随机访问。 - 自动扩容（1.5倍），但扩容成本高。
- 线程不安全，适合单线程场景。
- 尾部操作高效，中间插入/删除慢。
- 是
List接口最常用实现。