ArrayList 底层实现：动态数组的秘密
核心结构：一句话概括
ArrayList 就是一个会自己扩容的数组。它内部维护了一个 Object[]，当空间不够时，自动扩容。
java
public class ArrayList<E> {
// 实际存储元素的数组
transient Object[] elementData;
// 实际元素个数
private int size;
}就这么简单。elementData 就是那个会不断扩容的数组，size 记录当前有多少个元素。
内部结构图
ArrayList 内部就像一个「会变长的盒子」：
┌─────────────────────────────────────────────────────┐
│ elementData（Object[] 数组） │
│ ┌───────┬───────┬───────┬───────┬───────┬───────┐ │
│ │ [0] │ [1] │ [2] │ [3] │ [4] │ ... │ │
│ ├───────┼───────┼───────┼───────┼───────┼───────┤ │
│ │ "A" │ "B" │ "C" │ "D" │ "E" │ null │ │
│ └───────┴───────┴───────┴───────┴───────┴───────┘ │
│ 0 1 2 3 4 5 │
│ │
│ size = 5（实际元素个数） │
│ elementData.length = 10（数组容量） │
└─────────────────────────────────────────────────────┘构造方法：3 种创建方式
java
// 1. 默认构造 → 空数组，首次添加才分配 10
ArrayList<String> list1 = new ArrayList<>();
// 2. 指定初始容量 → 预分配，避免扩容
ArrayList<String> list2 = new ArrayList<>(100);
// 3. 从已有集合创建
ArrayList<String> list3 = new ArrayList<>(Arrays.asList("A", "B", "C"));默认容量是 0，不是 10
注意：默认构造方法创建的 ArrayList 内部数组是空的。第一次 add() 时才会分配容量 10。这是为了节省内存——如果你创建了 100 个 ArrayList 但都没放元素，就不会占用 100 × 10 = 1000 个对象的空间。
java
// 源码逻辑（简化）
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 空数组，容量 0
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}添加元素：两步走
添加到末尾
java
public boolean add(E e) {
// 1. 确保容量够用（扩容逻辑在 ensureCapacityInternal 里）
ensureCapacityInternal(size + 1);
// 2. 放入数组，size++
elementData[size++] = e;
return true;
}添加到指定位置
java
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
// 将 index 及之后的元素向后移动一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}图示：
add(2, "X") 到 [A, B, C, D, E]：
操作前：
┌───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘
0 1 2 3 4
System.arraycopy(elementData, 2, elementData, 3, 3)
C, D, E 向后移动一位：
操作后：
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ X │ C │ D │ E │
└───┴───┴───┴───┴───┴───┘
0 1 2 3 4 5扩容机制：容量翻倍的秘密
ArrayList 容量不够时，会自动扩容。扩容公式：新容量 = 旧容量 + 旧容量 / 2 = 旧容量 × 1.5
java
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新容量 = 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 还不够？直接用 minCapacity
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
// 超过最大容量？用 Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0) {
newCapacity = hugeCapacity(minCapacity);
}
// 创建新数组，复制元素
elementData = Arrays.copyOf(elementData, newCapacity);
}容量增长轨迹：
容量 0 → 首次添加 → 10
容量 10 → 添加第 11 个 → 15
容量 15 → 添加第 16 个 → 22
容量 22 → 添加第 23 个 → 33
容量 33 → 添加第 34 个 → 49
...扩容是性能杀手
扩容需要：
- 分配新数组
- 复制所有元素
如果你知道大概要存多少元素，一开始就指定容量，避免扩容：
java
// ❌ 可能触发多次扩容
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
list.add("item" + i);
}
// ✅ 一步到位
ArrayList<String> list = new ArrayList<>(100000);
for (int i = 0; i < 100000; i++) {
list.add("item" + i);
}随机访问：O(1) 的秘密
ArrayList 随机访问极快，因为是直接用数组下标：
java
public E get(int index) {
rangeCheck(index);
return elementData[index]; // 直接返回，就是这么快
}这就是为什么 ArrayList 比 LinkedList 随机访问快 100 倍以上——LinkedList 需要从头或从尾遍历到目标位置。
删除元素：也要移动数组
java
public E remove(int index) {
rangeCheck(index);
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0) {
// 将 index+1 及之后的元素向前移动一位
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null; // 帮助 GC
return oldValue;
}删除中间的图示：
remove(2) 从 [A, B, C, D, E]：
操作前：
┌───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘
0 1 2 3 4
System.arraycopy(elementData, 3, elementData, 2, 2)
D, E 向前移动一位：
操作后：
┌───┬───┬───┬───┬───┐
│ A │ B │ D │ E │null│
└───┴───┴───┴───┴───┘
0 1 2 3 4性能总结
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
随机访问 get(i) | O(1) | 直接数组下标 |
尾部添加 add(e) | 均摊 O(1) | 大多数是 O(1)，扩容时 O(n) |
中间插入 add(i, e) | O(n) | 需要移动元素 |
按索引删除 remove(i) | O(n) | 需要移动元素 |
按对象删除 remove(Object) | O(n) | 查找 + 移动 |
contains | O(n) | 需要遍历 |
clear | O(n) | 需要逐个清空引用 |
线程安全：非线程安全
ArrayList 是非线程安全的。
java
// ❌ 多线程不安全
ArrayList<String> list = new ArrayList<>();
// 线程 A: list.add("A");
// 线程 B: list.add("B");
// 结果：可能只添加了一个元素，或者 size 不正确
// ✅ 线程安全的替代方案
List<String> safe1 = Collections.synchronizedList(new ArrayList<>());
List<String> safe2 = new CopyOnWriteArrayList<>(); // 读多写少场景总结口诀
ArrayList = 动态数组。随机访问最快，尾部操作高效，中间增删要移动元素。预知容量能省扩容，线程不安全是天生缺陷。