Java ArrayList

学习目标

理解 ArrayList 的底层实现原理与动态扩容机制
掌握 ArrayList 的核心操作（增删改查、遍历、初始化）
熟悉常用构造方法与性能优化技巧
了解线程安全问题及解决方案
能够根据场景合理使用 ArrayList 并避免常见陷阱

ArrayList 概述

ArrayList 是 Java 中最常用的集合类之一，位于 java.util 包。它本质上是一个可自动扩容的动态数组，克服了传统数组长度固定的限制。

核心特性

支持索引访问：通过整数下标快速获取或修改元素（O(1)）
允许重复元素：同一个对象可多次存储
维护插入顺序：元素按添加顺序排列
非线程安全：多线程环境下需手动同步
自动扩容：当容量不足时，内部数组会自动增长

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println(numbers); // [1, 2]

继承体系

ArrayList 实现了 List 接口，因此具备所有列表操作能力，并继承了 RandomAccess、Cloneable、Serializable 等标记接口。

构造方法

Java 提供三种构造方式，满足不同初始化需求：

1. 无参构造

ArrayList<String> list = new ArrayList<>();
// JDK 8+：初始容量为 0，首次添加时扩容至 10
// JDK 7 及更早：直接初始化为容量 10

2. 指定初始容量

ArrayList<Integer> nums = new ArrayList<>(100);
// 预分配足够空间，避免频繁扩容（适用于已知数据量的场景）

3. 从现有集合初始化

List<String> source = Arrays.asList("A", "B", "C");
ArrayList<String> copy = new ArrayList<>(source);
// 复制所有元素，保持顺序

性能建议：若能预估元素数量，优先使用带容量参数的构造器，减少扩容带来的内存拷贝开销。

核心操作

增：添加元素

ArrayList<String> al = new ArrayList<>();
al.add("Java");           // 尾部添加 → [Java]
al.add(0, "Python");      // 索引 0 插入 → [Python, Java]
al.addAll(Arrays.asList("C++", "Go")); // 批量添加 → [Python, Java, C++, Go]

删：删除元素

al.remove(0);             // 按索引删除 → [Java, C++, Go]
al.remove("C++");         // 按值删除（首次匹配）→ [Java, Go]
al.clear();               // 清空所有元素 → []

改：更新元素

al.set(0, "JavaScript");  // 替换索引 0 的元素

查：访问与搜索

String first = al.get(0);                // 获取元素
boolean hasJS = al.contains("JavaScript"); // 是否包含
int index = al.indexOf("Go");            // 首次出现位置

注意：在中间位置插入或删除会导致后续元素整体移动，时间复杂度为 O(n)。

底层实现与扩容机制

内部结构

transient Object[] elementData; // 存储元素的底层数组
private int size;               // 实际元素数量

扩容策略（JDK 8+）

当 size == elementData.length 时触发扩容

新容量 = 旧容量 + (旧容量 >> 1) → 扩容 50%

int newCapacity = oldCapacity + (oldCapacity >> 1); // 相当于 *1.5

若仍不足，则直接使用所需最小容量
使用 Arrays.copyOf() 创建新数组并复制元素

示例：
初始容量 10 → 满后扩容至 15 → 再满扩容至 22 → 33 → 49 …

内存优化

list.trimToSize(); // 将底层数组容量缩减至当前 size，释放多余内存

性能复杂度

操作	时间复杂度	说明
尾部 add()	O(1)（均摊）	扩容时 O(n)，但均摊后仍为 O(1)
中间 add(index)	O(n)	需移动后续所有元素
get(index)	O(1)	直接数组访问
set(index, e)	O(1)	直接赋值
remove(index)	O(n)	删除后需左移后续元素
remove(value)	O(n)	先线性查找，再移动
contains()/ indexOf()	O(n)	线性遍历

线程安全问题

ArrayList 不是线程安全的。在多线程并发修改时，可能出现：

ConcurrentModificationException（遍历时被修改）
数据不一致（如丢失更新）

解决方案

使用同步包装器

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
// 所有操作自动加锁，但需注意迭代时仍需手动同步：
synchronized (syncList) {
    for (String s : syncList) { /* ... */ }
}

使用并发集合

推荐

若需高并发读写 → 考虑 CopyOnWriteArrayList（写时复制，适合读多写少）
若需队列行为 → ConcurrentLinkedQueue

Vector 虽线程安全，但因全方法加锁导致性能差，不推荐在新项目中使用。

常用方法

方法	描述
`add(E e)` / `add(int i, E e)`	添加元素
`get(int index)`	获取指定索引元素
`set(int index, E e)`	替换元素，返回旧值
`remove(int index)` / `remove(Object o)`	删除元素
`indexOf(Object o)` / `lastIndexOf(Object o)`	搜索元素位置
`contains(Object o)`	判断是否包含
`size()` / `isEmpty()`	查询状态
`clear()`	清空
`subList(int from, int to)`	返回子列表视图（左闭右开）
`ensureCapacity(int min)`	预扩容，避免多次扩容
`trimToSize()`	缩容，节省内存
`clone()`	浅拷贝（新 ArrayList，共享元素引用）
`toArray()`	转为数组

与其他实现对比

特性	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)	O(n)
首尾插入 / 删除	O(1)（尾部） O(n)（头部）	O(1)
中间插入 / 删除	O(n)	O(n)（需遍历定位）
内存开销	低（仅数组）	高（每个节点存前后指针）
适用场景	频繁读取、尾部操作	频繁首尾增删

默认选择 ArrayList，除非明确需要链表特性。

重点总结

ArrayList 是基于动态数组实现的 List
支持快速随机访问（O(1)），但中间增删较慢（O(n)）
自动扩容（1.5 倍），可通过预设容量优化性能
非线程安全，并发场景需额外处理
提供丰富的操作方法，是日常开发中最常用的集合类型

思考题

ArrayList 的 elementData 字段为何被声明为 transient？这对其序列化有何影响？
在什么情况下 ArrayList 的 add(index, element) 操作比 LinkedList 更快？请结合两者底层结构分析。
假设你有一个包含 100 万个 Integer 对象的 ArrayList，调用 list.remove(0) 会发生什么？如何高效地从头部移除大量元素？