---
title: "01-ArrayList"
created: 2025-12-02
tags:
  - Java
---
# ArrayList

> [!note] 定位说明
> List 系列第 1 篇详篇（整体认知见 [[00-List总览|00-List总览]]）。ArrayList 是日常开发的**默认 List 实现**：底层动态数组、随机访问 O(1)、扩容 1.5 倍。本篇覆盖常用操作、扩容源码（`grow()`）、删除、序列化与 fail-fast 机制。

## 概念与本质

`ArrayList` 是 Java 中最常用的集合类之一，属于 `java.util` 包，是基于动态数组实现的可变长度顺序表。其特点是：

- 支持随机访问（O(1)），性能优于链表
- 插入、删除元素时可能涉及数组拷贝，效率相对较低（O(n)）
- 本质是对数组功能的封装与增强

源码结构：

```java
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, Serializable
```

其中的 `RandomAccess` 是一个标志性接口，表示支持快速随机访问。

## 常用功能与用法

### 创建与初始化

```java
List<String> list1 = new ArrayList<>();                  // 默认容量10
List<Integer> list2 = new ArrayList<>(100);              // 指定初始容量
List<String> list3 = new ArrayList<>(list1);             // 通过已有集合创建
```

### 增删改查

```java
list.add("a");                   // 尾部添加
list.add(1, "b");                // 指定位置插入
list.remove("a");                // 删除指定元素
list.remove(1);                  // 删除指定位置
list.set(0, "new");              // 修改元素
String s = list.get(0);          // 获取元素
```

### 遍历方式

```java
// 普通 for 循环
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 增强 for 循环
for (String s : list) {
    System.out.println(s);
}

// 迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

// ListIterator（支持双向遍历）
ListIterator<String> lit = list.listIterator();
while (lit.hasNext()) {
    System.out.println(lit.next());
}
```

## 扩容机制

当你向 `ArrayList` 添加新元素时，系统会先检查底层数组是否还有空间。比如当前已有 10 个元素，再插入第 11 个，就会发现容量已满。此时就会触发扩容机制，`ArrayList` 会调用 `grow()` 方法，将原数组扩容为原来的 1.5 倍（如从 10 扩到 15），然后通过 `Arrays.copyOf()` 将原数据复制到新数组中，再完成新元素的插入。这个过程虽然对你来说是"自动"的，但背后其实发生了一次数组复制，所以频繁扩容代价很高，**建议在构造时就尽可能预估初始容量**，避免反复扩容影响性能。

### 默认容量

`ArrayList` 底层是基于数组 `elementData[]` 实现的，默认初始容量为 10：

```java
private static final int DEFAULT_CAPACITY = 10;
```

在你使用无参构造创建 `ArrayList` 后，并不会立刻分配大小为 10 的数组，而是懒惰初始化——第一次添加元素时才初始化为默认容量：

```java
ArrayList<String> list = new ArrayList<>(); // 初始时 elementData = {}
list.add("a"); // 第一次添加，初始化为长度 10 的数组
```

### 添加元素时的扩容逻辑

每次添加元素，都会调用 `ensureCapacityInternal(size + 1)` 方法检查容量是否够用：

```java
public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 容量不足会触发扩容
    elementData[size++] = e;
    return true;
}
```

其内部流程如下：

```java
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity); // 触发扩容
    }
}
```

### 核心扩容方法 grow()

真正负责扩容的是 `grow()` 方法：

```java
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩为 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity; // 防止容量还是不够
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity); // 防止超大数组溢出
    elementData = Arrays.copyOf(elementData, newCapacity); // 拷贝到新数组
}
```

- `oldCapacity >> 1` 等价于 `oldCapacity / 2`
- 即 `newCapacity = oldCapacity + oldCapacity / 2`，约为 **1.5 倍**
- 用 `Arrays.copyOf()` 拷贝原数组内容到新数组

注意：拷贝数组是**代价很高的操作（O(n)）**，频繁扩容会严重影响性能。

## 删除操作

需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看到 ArrayList 删除元素的代价是非常高的。

```java
public E remove(int index) {
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // 避免内存泄漏
    return oldValue;
}
```

- 删除会造成后续元素整体前移
- 时间复杂度为 O(n)

## 序列化机制

ArrayList 为了避免序列化冗余空间、提升效率和数据一致性，通过 `transient` + 自定义的 `writeObject()` / `readObject()` 方法，仅对有效元素进行精准序列化。这是对默认序列化机制的**精细化控制**，体现了 Java 对容器类序列化的高度优化与兼容性设计。

### 为什么要特殊处理序列化？

`ArrayList` 是基于数组实现的，并具有**动态扩容**特性，比如你初始化了一个容量为 100 的 ArrayList，但实际只放了 3 个元素。此时底层的数组 `elementData` 仍然有 97 个 null 空位。

如果不处理，直接把整个数组都序列化，会浪费大量空间；更严重的是，可能会暴露未使用或敏感数据。

### transient 修饰 elementData

```java
transient Object[] elementData;
```

关键点：`elementData` 是 **transient 修饰的成员变量**，表示它不会被 Java 默认序列化机制处理。

这意味着：**JVM 不会自动保存这个数组的内容**，但我们可以自己手动决定哪些元素需要序列化、如何序列化。

### 手动控制序列化过程（核心）

`ArrayList` 实现了 `writeObject()` 和 `readObject()` 方法，用来**自定义序列化逻辑**。这两个方法是 Serializable 接口的"钩子"，在序列化或反序列化时由 JVM 自动反射调用。

#### writeObject() —— 序列化过程

```java
private void writeObject(ObjectOutputStream s) throws IOException {
    int expectedModCount = modCount;
    s.defaultWriteObject();          // 序列化非 transient 字段（如 size）
    s.writeInt(size);                // 再写入当前实际元素个数 size

    // 只序列化已有的元素，忽略空位
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }

    // 结构变更校验，防止并发修改
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
```

解释：

- `s.defaultWriteObject()`：序列化默认字段（如 size）
- `writeInt(size)`：记录有几个元素需要反序列化回来
- 循环只序列化前 `size` 个有效元素
- 最后校验 modCount 是否变化，防止并发修改时状态不一致

#### readObject() —— 反序列化过程

```java
private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    s.defaultReadObject();        // 反序列化非 transient 字段（如 size）
    s.readInt();                  // 读取并丢弃 capacity（只是为了兼容 clone）

    if (size > 0) {
        ensureCapacityInternal(size);      // 确保底层数组够用
        Object[] a = elementData;

        for (int i = 0; i < size; i++) {
            a[i] = s.readObject();         // 恢复元素数据
        }
    }
}
```

解释：

- `defaultReadObject()` 读取默认字段（如 size）
- `readInt()` 是为了向前兼容某些版本中的 capacity 记录
- 如果 size > 0，就初始化 elementData，并填入反序列化的元素

### 使用示例（序列化和反序列化）

```java
ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");

// 序列化到文件
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("list.ser"));
oos.writeObject(list);
oos.close();

// 反序列化
ObjectInputStream ois = new ObjectInputStream(new FileInputStream("list.ser"));
ArrayList<String> result = (ArrayList<String>) ois.readObject();
ois.close();

System.out.println(result); // [apple, banana]
```

### 补充说明：为什么使用 modCount？

`modCount` 是 ArrayList 的一个结构修改计数器，用于检测并发修改（fail-fast）。在 `writeObject()` 中，序列化前后 modCount 不一致，说明期间被修改过，立刻抛出异常，防止写入脏数据。

## Fail-Fast 机制

内部维护一个 `modCount` 变量，记录结构修改次数（结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化）：

```java
protected transient int modCount = 0;
```

如在迭代时修改结构，`modCount` 不一致，将抛出 `ConcurrentModificationException`：

```java
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("a")) {
        list.remove("a"); // 会抛异常
    }
}
```

正确做法应使用迭代器自身的 `remove()` 方法。

## 总结特点

| 特性 | 说明 |
| --- | --- |
| 底层结构 | 动态数组（Object[]） |
| 查找效率 | 快速随机访问，O(1) |
| 插入删除效率 | 插入、删除慢，O(n)，尤其是头部和中间位置 |
| 线程安全 | 非线程安全，可用 `Collections.synchronizedList()` 包装 |
| 扩容策略 | 容量不足时扩为原来的 1.5 倍 |
| 迭代方式 | for、foreach、iterator、listIterator |
| 典型应用 | 查找频繁，插入删除较少的场景，如缓存、索引表等 |

---
⬅️ [[00-List总览|00-List总览]] 🏠 [[00-Java|00-Java]] ➡️ [[02-LinkedList|LinkedList]]