Java ArrayList 底层原理与核心方法手写实现

Java ArrayList 底层原理与核心方法手写实现

ArrayList 是 Java 集合框架中 List 接口的动态数组实现，它提供了便捷的增删查改操作。通过手写实现其核心逻辑，我们可以更透彻地理解顺序表在内存中的存储方式、扩容机制以及边界处理策略。

类结构定义

实现的核心在于维护一个内部数组和一个记录有效元素个数的变量。默认容量通常设为 10，当数据量超过当前容量时触发扩容。

import java.util.Arrays;

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

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

核心方法实现

1. 添加元素（末尾）

向列表末尾添加元素前，必须检查数组是否已满。如果 usedSize 等于数组长度，说明空间不足，需要调用扩容方法。

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

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

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

这里采用 2 倍扩容是为了平衡内存占用和频繁扩容带来的性能损耗。虽然会牺牲一定空间，但能减少数组复制的次数。

2. 指定位置插入

在指定位置插入元素时，除了检查容量，还需要验证索引合法性。如果插入位置在中间，需要将后续元素整体向后移动一位，腾出空位。

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 checkPos(int pos, String msg) {
    if (pos < 0 || pos > usedSize) {
        throw new PosIllegalityException(msg);
    }
}

注意循环的方向，必须从后向前移动，否则前面的数据会被覆盖导致丢失。

3. 查找与判断

判断是否包含某个元素或获取元素下标，本质上都是线性遍历。对于基本数据类型，直接比较值即可；如果是对象引用，则需使用 equals 方法。

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. 获取与修改

获取和修改操作都需要严格的边界校验。访问空列表或越界索引都会抛出异常，这是保证程序健壮性的关键。

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 boolean isEmpty() {
    return usedSize == 0;
}

5. 删除元素

删除指定值的元素时，先找到其索引。若存在，则将后续元素向前覆盖，最后将有效长度减一。对于引用类型，建议将最后一个元素置为 null 以便 GC 回收。

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--;
    // arr[usedSize] = null; // 引用类型建议手动置空
}

6. 工具方法

获取当前大小和清空列表相对简单，主要是重置计数器和清理数据。

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

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

总结

通过上述手写过程，我们不仅复现了 ArrayList 的基础功能，更理解了动态数组背后的设计权衡。无论是扩容时的内存分配，还是插入删除时的数据搬运，都直接影响着程序的运行效率。在实际开发中，了解这些底层细节有助于我们在面对大数据量场景时做出更合理的选择。