一、定义

ArrayList 是 Java 集合框架中最常用的动态数组实现，基于 Object[] 数组，支持自动扩容。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, Serializable {
    
    // 存储元素的数组缓冲区
    transient Object[] elementData;
    
    // 实际元素个数
    private int size;
    
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
}

默认初始容量：10

二、内存结构

在这里插入图片描述

三、构造方法

构造方法 说明
new ArrayList<>() 空列表，首次 add 时才分配容量 10（懒加载）
new ArrayList<>(20) 指定初始容量 20
new ArrayList<>(collection) 从其他集合构造 
// 默认构造：elementData 指向 EMPTY 数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  // {}
}

// 首次 add 时：
// minCapacity = max(10, 1) = 10
// 创建 new Object[10]

四、扩容机制

4.1 触发条件

private void ensureExplicitCapacity(int minCapacity) {
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);  // 需要扩容
    }
}

触发时机：当前 size + 1 > capacity（数组容量不够放下新元素）。

4.2 扩容公式

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    
    // 新容量 = 旧容量 + 旧容量 / 2 = 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 如果 1.5 倍还不够（比如 addAll 一次性加很多），直接用需求值
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    
    // 如果超过 MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8），用 Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }
    
    // 创建新数组 + 拷贝
    elementData = Arrays.copyOf(elementData, newCapacity);
}

为什么是 1.5 倍？

考量 说明
空间换时间 预留空间减少后续扩容频率
内存平衡 2 倍增长太快浪费内存，1.25 倍增长太慢频繁拷贝
经验值 1.5 倍是 JDK 团队长期实践的平衡点

4.3 扩容过程详解

在这里插入图片描述

4.4 扩容的性能代价

场景 代价
单次扩容 O(n) 数组拷贝
均摊到 n 次 add O(1) 均摊
频繁扩容 大量数组创建和 GC，性能下降

最佳实践：如果知道大致元素数量，直接指定初始容量：

// 避免多次扩容
List<String> list = new ArrayList<>(10000);

// 比下面这种快很多
List<String> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    list.add(...);  // 会触发 10 → 15 → 22 → 33 → 50 → 75 → 113 → ... 多次扩容
}

4.5 扩容上限

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
  • MAX_ARRAY_SIZE = 2^31 - 1 - 8 = 2147483639
  • 留 8 字节是为了避免某些 JVM 实现中的数组头开销溢出
  • 实际最大元素数受堆内存限制，通常远达不到这个值

五、数据结构

5.1 类继承体系

在这里插入图片描述

5.2 核心字段

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

    // 序列化兼容版本号
    private static final long serialVersionUID = 8683452581122892189L;

    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    // 空数组实例（用于空列表构造）
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 默认空数组（用于无参构造，区分 EMPTY_ELEMENTDATA）
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 存储元素的数组缓冲区（核心数据结构）
    transient Object[] elementData;

    // 实际元素数量
    private int size;

    // 结构修改次数（用于 fail-fast）
    protected transient int modCount = 0;
}

5.3 字段详解

字段 类型 作用
elementData Object[] 核心存储数组，所有元素存在这里
size int 实际存储的元素个数，size <= elementData.length
modCount int 结构修改次数（add/remove/clear 等会递增）
DEFAULT_CAPACITY static final int 默认容量 10
EMPTY_ELEMENTDATA static final Object[] 共享空数组（用于 new ArrayList<>(0)）
DEFAULTCAPACITY_EMPTY_ELEMENTDATA static final Object[] 共享默认空数组（用于 new ArrayList<>()）

5.4 为什么 elementData 是 transient

transient Object[] elementData;

transient 表示不参与默认序列化。原因：

  1. 容量可能大于实际元素数：序列化时不需要保存多余的 null 槽位
  2. 节省空间：只序列化 size 个有效元素
  3. 自定义序列化逻辑：writeObject() / readObject() 手动处理
private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    s.defaultWriteObject();
    s.writeInt(size);  // 写入元素个数
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);  // 只写入有效元素
    }
}

private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    s.defaultReadObject();
    int capacity = s.readInt();  // 读取容量
    if (capacity > 0) {
        elementData = new Object[capacity];
    }
    for (int i = 0; i < size; i++) {
        elementData[i] = s.readObject();  // 逐个读取
    }
}

5.5 内存布局

在这里插入图片描述

5.6 懒加载机制

// 无参构造：不分配数组，指向共享空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 首次 add 时才真正分配
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // ...
}

好处：创建大量空 ArrayList 时不浪费内存。

new ArrayList<>()  →  elementData = {}  (共享空数组, 0 开销)
add("a")           →  发现是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                   →  minCapacity = max(10, 1) = 10
                   →  elementData = new Object[10]
                   →  elementData[0] = "a"
                   →  size = 1

5.7 trimToSize()

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

作用：去掉多余容量，释放内存。

Before: elementData = Object[100], size = 5  (95 个 null 浪费)
After:  elementData = Object[5]   (精确匹配)

适用场景：一次性构建完成后，确定不再添加元素，可以 trimToSize() 节省内存。

六、扩容与数据结构的关系

数据结构特性 对扩容的影响
连续数组存储 扩容必须创建新数组 + 拷贝，无法原地扩展
引用类型数组 拷贝的是引用（4/8 字节），不是对象本身，拷贝较快
Object[] 泛型擦除 实际存储 Object，取出时强转，类型安全由编译器保证
容量与大小分离 capacity（数组长度）>= size（实际元素），预留空间减少扩容

七、add

7.1 add(E e) — 尾部追加

public boolean add(E e) {
    // 1. 确保容量足够（可能触发扩容）
    ensureCapacityInternal(size + 1);
    
    // 2. 元素放到数组末尾
    elementData[size++] = e;
    
    return true;
}

7.2 ensureCapacityInternal — 容量检查

private void ensureCapacityInternal(int minCapacity) {
    // 如果是首次添加（无参构造后的空数组）
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  // max(10, 1) = 10
    }
    
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  // 修改次数 +1
    
    // 如果所需容量 > 当前数组长度，需要扩容
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

7.3 grow — 扩容

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    
    // 新容量 = 旧容量的 1.5 倍
    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);
}

7.4 完整流程

在这里插入图片描述

7.5 add(int index, E element) — 指定位置插入

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], size=5
│
├── ensureCapacityInternal(6) // 容量够，不扩容
│
├── System.arraycopy(elementData, 2, elementData, 3, 3)
│ // 从 index=2 开始，拷贝 3 个元素到 index=3
│ // [A][B][C][D][E] → [A][B][C][C][D][E] (C、D、E 右移)
│
├── elementData[2] = “X”
│ // [A][B][X][C][D][E]
│
└── size = 6

7.6 流程对比

方法 步骤 复杂度
add(E e) 检查容量 → 扩容(如需) → 尾部赋值 → size++ O(1) 均摊
add(int, E) 检查容量 → 扩容(如需) → System.arraycopy 右移 → 插入 → size++ O(n)

7.8 细节

细节 说明
modCount++ 每次 add 都递增，用于迭代器的 fail-fast 检测
System.arraycopy 本地方法，C 实现，比 Java 循环拷贝快
首次 add 分配 10 无参构造的懒加载策略，避免空列表浪费内存
1.5 倍扩容 平衡空间浪费和扩容频率的经验值
Arrays.copyOf 内部调用 System.arraycopy + new Object[]

八、get() / set() — O(1) 随机访问

public E get(int index) {
    rangeCheck(index);           // 边界检查
    return elementData(index);   // 直接数组访问
}

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;  // 直接数组写入
    return oldValue;
}

为什么快：数组在内存中连续存储，CPU 缓存友好，直接通过 base + index * size 计算地址。

九、remove() — O(n) 移位

public E remove(int index) {
    rangeCheck(index);
    E oldValue = elementData(index);
    
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        // 将 index 后面的元素整体左移一位
        System.arraycopy(elementData, index + 1,
                         elementData, index, numMoved);
    }
    
    elementData[--size] = null;  // 末尾置空，帮助 GC
    return oldValue;
}

删除示意图：

Before:  [A][B][C][D][E]   remove(2)
              ↑
After:   [A][B][D][E][null]
              (C 被覆盖，D、E 左移)

十、迭代器与 fail-fast

private class Itr implements Iterator<E> {
    int cursor;        // 下一个元素索引
    int lastRet = -1; // 上次返回的索引
    int expectedModCount = modCount;  // 快照
    
    public E next() {
        checkForComodification();
        return elementData[lastRet = cursor++];
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

fail-fast 机制：

  • 迭代时记录 modCount 快照
  • 如果外部修改了列表（add/remove），modCount 变化 → 抛出 ConcurrentModificationException
  • 不是线程安全机制，只是快速失败检测

十一、时间复杂度总结

操作 复杂度 说明
get(index) O(1) 直接数组访问
set(index, e) O(1) 直接数组写入
add(e) O(1) 均摊 通常 O(1)，扩容时 O(n)
add(index, e) O(n) 需要右移元素
remove(index) O(n) 需要左移元素
remove(Object) O(n) 先查找再移位
contains(Object) O(n) 线性搜索
indexOf(Object) O(n) 线性搜索

十二、与 LinkedList 对比

特性 ArrayList LinkedList
底层结构 Object[] 数组 Node {prev, data, next} 链表
get(index) O(1) O(n)
add(index, e) O(n) 移位 O(n) 查找位置
add(e) 尾部 O(1) 均摊 O(1)
remove(index) O(n) 移位 O(n) 查找
内存占用 更少（仅数组） 更多（每个 Node 对象 + 两个指针）
缓存友好 是（连续内存） 否（节点分散）
适用场景 随机访问、 mostly read 频繁在两端插入删除

十三、总结

默认用 ArrayList，预估容量初始化，遍历用索引，删除用迭代器或倒序，多线程用 CopyOnWriteArrayList 或 synchronizedList，频繁查找用 HashSet。

# java # 开发语言 # android
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

一个 API 入口调用多个大模型：AiiOnly客户端 + CC Switch 打通 Codex AI编程流程

avatar AI编程社区
cover

VSCode Claude Code + MiMo 中转免登录完整配置教程（解决原生登录弹窗 + 模型报错）

avatar AI编程社区
cover

从零开始做一个属于自己的 Skill（保姆级教程）

avatar AI编程社区