Java ArrayList的自我实现：如何用数组实现O(1)随机访问与O(n)插入

说话的鲸鱼

417人浏览 · 2025-10-20 23:42:52

说话的鲸鱼 · 2025-10-20 23:42:52 发布

Java ArrayList的自我实现

要实现一个支持$O(1)$随机访问和$O(n)$插入的动态数组，核心是数组存储 + 动态扩容机制。以下是关键实现步骤：

1. 基础结构

public class MyArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData; // 底层数组
    private int size;             // 当前元素数量

    public MyArrayList() {
        elementData = new Object[DEFAULT_CAPACITY];
        size = 0;
    }
}

2. $O(1)$随机访问实现

public E get(int index) {
    rangeCheck(index); // 校验索引合法性
    return (E) elementData[index]; // 直接返回数组元素
}

private void rangeCheck(int index) {
    if (index < 0 || index >= size) 
        throw new IndexOutOfBoundsException();
}

时间复杂度分析：
直接通过索引访问数组元素，时间复杂度为$O(1)$。

3. $O(n)$插入实现

public void add(int index, E element) {
    rangeCheckForAdd(index); // 校验插入位置
    
    ensureCapacity(); // 确保容量充足
    // 移动元素：从插入位置开始后移
    System.arraycopy(elementData, index, 
                     elementData, index + 1, 
                     size - index);
    
    elementData[index] = element; // 插入新元素
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size) 
        throw new IndexOutOfBoundsException();
}

时间复杂度分析：

最坏情况：在数组头部插入，需移动全部$n$个元素，时间复杂度为$O(n)$
平均情况：需移动$\frac{n}{2}$个元素，时间复杂度为$O(n)$

4. 动态扩容机制

private void ensureCapacity() {
    if (size == elementData.length) {
        int newCapacity = elementData.length * 2; // 扩容为原容量2倍
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

扩容分析：

扩容操作时间复杂度为$O(n)$
均摊到每次插入操作，时间复杂度仍为$O(1)$（通过均摊分析证明）

完整实现代码

import java.util.Arrays;

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

    public MyArrayList() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    // O(1)随机访问
    public E get(int index) {
        if (index < 0 || index >= size) 
            throw new IndexOutOfBoundsException();
        return (E) elementData[index];
    }

    // O(n)插入
    public void add(int index, E element) {
        if (index < 0 || index > size) 
            throw new IndexOutOfBoundsException();
        
        ensureCapacity();
        System.arraycopy(elementData, index, 
                         elementData, index + 1, 
                         size - index);
        elementData[index] = element;
        size++;
    }

    // 动态扩容
    private void ensureCapacity() {
        if (size == elementData.length) {
            int newCapacity = elementData.length * 2;
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

    // 返回当前元素数量
    public int size() {
        return size;
    }
}