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

这里采用 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 的基础功能，更理解了动态数组背后的设计权衡。无论是扩容时的内存分配，还是插入删除时的数据搬运，都直接影响着程序的运行效率。在实际开发中，了解这些底层细节有助于我们在面对大数据量场景时做出更合理的选择。