手写 Java ArrayList：add() 方法与扩容机制实现

核心逻辑设计

1. 底层数据结构：使用 Object[] 数组存储元素
2. 关键变量：
   • elementData：存储元素的数组
   • size：当前元素数量
   • DEFAULT_CAPACITY = 10：默认初始容量
3. 扩容机制：
   • 当数组已满时，按 1.5 倍 扩容
   • 扩容公式：$$ \text{newCapacity} = \text{oldCapacity} + (\text{oldCapacity} \gg 1) $$
   • 首次扩容从 0 → 10

代码实现

public class MyArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData;
    private int size;

    // 构造方法
    public MyArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else {
            throw new IllegalArgumentException("非法容量: " + initialCapacity);
        }
    }

    // 核心add方法
    public boolean add(E e) {
        ensureCapacity(size + 1);  // 确保容量足够
        elementData[size++] = e;   // 添加元素并更新size
        return true;
    }

    // 扩容机制实现
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length) {
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5倍扩容
            
            // 处理首次扩容
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            // 处理初始容量为0的情况
            if (newCapacity < DEFAULT_CAPACITY) {
                newCapacity = DEFAULT_CAPACITY;
            }
            
            // 创建新数组并迁移数据
            Object[] newArray = new Object[newCapacity];
            System.arraycopy(elementData, 0, newArray, 0, size);
            elementData = newArray;
        }
    }

    // 获取元素数量
    public int size() {
        return size;
    }
}

关键逻辑解析

1. 添加元素流程：

   graph TD
   A[调用add方法] --> B{检查容量}
   B -->|不足| C[执行扩容]
   B -->|足够| D[存入数组]
   C --> D
   D --> E[size++]
   

2. 扩容触发条件：

   • 当 size + 1 > elementData.length 时触发
   • 例：初始容量10，添加第11个元素时扩容

3. 扩容计算示例：

   当前容量	位运算 >>1	新容量
   10	5	15
   15	7	22
   0	0	10（默认）

设计要点

1. 高效扩容：

   • 位运算 oldCapacity >> 1 比 * 0.5 更高效
   • System.arraycopy() 使用 native 方法实现高速复制

2. 边界处理：

   • 处理初始容量为0的情况
   • 首次扩容直接使用默认容量
   • 保证最小容量满足需求

3. 时间复杂度：

   • 普通添加：$O(1)$
   • 扩容操作：$O(n)$（均摊后仍为 $O(1)$）

通过此实现可掌握 ArrayList 核心设计思想：动态数组 + 按需扩容。实际 JDK 实现还包含快速失败机制、序列化优化等额外特性。