Java ArrayList 底层原理与手动实现

Java ArrayList 底层原理与手动实现

ArrayList 是 Java 集合框架中 List 接口的动态数组实现，能够方便地存储和操作数据。通过从零开始手写 ArrayList 的核心方法，我们可以更深度地理解顺序表（Dynamic Array）的内存模型、扩容机制以及时间复杂度。

一、类定义与初始化

首先定义核心字段：

• arr：整型数组，用于存储数据。
• usedSize：记录当前有效数据的个数。
• DEFAULT_CAPACITY：默认初始容量，通常设为 10。

构造方法负责初始化数组空间。

import java.util.Arrays;

public class MyArrayList implements IList {
    private int[] arr;      // 存储数据
    private int usedSize;   // 有效数据个数
    public static final int DEFAULT_CAPACITY = 10; // 默认数组容量

    public MyArrayList() {
        this.arr = new int[DEFAULT_CAPACITY];
    }
}

二、核心方法实现

1. 添加元素 add(int data)

向列表末尾追加元素时，首要任务是检查数组是否已满。如果满了，需要触发扩容逻辑。

public void add(int data) {
    if (isFull()) {
        grow();
    }
    this.arr[this.usedSize] = data;
    this.usedSize++;
}

private boolean isFull() {
    return this.usedSize == this.arr.length;
}

private void grow() {
    // 扩容策略：新容量为原容量的 2 倍
    this.arr = Arrays.copyOf(this.arr, 2 * this.arr.length);
}

注意：这里采用 2 倍扩容是为了平衡空间利用率和扩容频率。虽然每次扩容涉及数组拷贝，但均摊下来插入操作的复杂度仍接近 O(1)。

2. 指定位置添加 add(int pos, int data)

在中间位置插入元素时，除了检查容量，还需要将目标位置及之后的元素向后移动，腾出空位。

public void add(int pos, int data) {
    if (isFull()) {
        grow();
    }
    checkPos(pos, "add 方法执行的时候 pos 位置不合法");

    if (pos == usedSize) {
        arr[pos] = data;
        usedSize++;
        return;
    }

    // 从后往前移动数据，避免覆盖未处理的数据
    for (int i = usedSize - 1; i >= pos; i--) {
        arr[i + 1] = arr[i];
    }
    arr[pos] = data;
    usedSize++;
}

private void checkPosAdd(int pos, String msg) {
    if (pos < 0 || pos > usedSize) {
        throw new PosIllegalityException(msg);
    }
}

关键点：移动数据时必须从后向前遍历。如果从前向后，后面的数据会覆盖前面的数据，导致信息丢失。

3. 查找与判断 contains / indexOf

这两个方法都依赖于线性遍历。对于基本数据类型，直接比较值即可。

public boolean contains(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (arr[i] == toFind) {
            return true;
        }
    }
    return false;
}

public int indexOf(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (arr[i] == toFind) {
            return i;
        }
    }
    return -1;
}

4. 获取与修改 get / set

访问和修改操作都需要严格的边界检查，防止索引越界。

public int get(int pos) {
    if (isEmpty()) {
        throw new EmptyListException("当前顺序表为空");
    }
    checkPos(pos, "get 方法的 pos 位置不合法");
    return arr[pos];
}

public void set(int pos, int value) {
    if (isEmpty()) {
        throw new EmptyListException("当前顺序表为空");
    }
    checkPos(pos, "set 方法执行的时候 pos 位置不合法" + pos);
    arr[pos] = value;
}

private void checkPos(int pos, String msg) {
    if (pos < 0 || pos >= usedSize) {
        throw new PosIllegalityException(msg);
    }
}

public boolean isEmpty() {
    return usedSize == 0;
}

5. 删除 remove

删除指定元素时，先找到其索引，然后将该索引之后的所有元素向前移动一位覆盖它。

public void remove(int toRemove) {
    if (isEmpty()) {
        throw new EmptyListException("当前顺序表为空");
    }

    int index = indexOf(toRemove);
    if (index == -1) {
        System.out.println("没有你要删除的数据");
        return;
    }

    // 从被删除元素的下一个位置开始，向前移动
    for (int i = index; i < usedSize - 1; i++) {
        arr[i] = arr[i + 1];
    }
    usedSize--;
    // 如果是引用类型数组，建议将最后一个元素置为 null 以便 GC 回收
    // arr[usedSize] = null;
}

6. 辅助方法 size / clear

public int size() {
    return this.usedSize;
}

public void clear() {
    for (int i = 0; i < this.usedSize; i++) {
        arr[i] = 0;
    }
    usedSize = 0;
}

三、总结

通过手动实现 ArrayList，我们不仅掌握了增删改查的具体代码逻辑，更重要的是理解了动态数组背后的设计权衡：

1. 连续内存：保证了随机访问的高效性（O(1)），但也导致了插入删除时的元素移动开销（O(n)）。
2. 扩容机制：2 倍扩容策略在空间浪费和时间成本之间取得了较好的平衡。
3. 边界安全：完善的异常抛出机制是健壮性的基础。

这种底层视角的理解，有助于在实际开发中更合理地选择数据结构，优化程序性能。