【重学数据结构】数组 ArrayList

程序员三明治

发布于 2025-12-18 20:02:11

1320

文章被收录于专栏：码力up码力up

数组是什么？

数组是一种线性表的数据结构，是一个存储相同数据类型的集合，每个相邻元素的物理内存地址也相邻。

实现一个ArrayList

内部属性

    // 默认的初始化空间
    private static final int DEFAULT_CAPACITY = 10;
    // 默认的空元素数组
    private static final Object[] DEFAULT_EMPTY_ELEMENTDATA = {};
    // 元素数组缓冲区
    private Object[] elementData;
    // 元素个数
    private int size;

在我们初始化ArrayList的时候，如果指定了容量大小的话，那它就会创建一个指定容量大小的数组；如果没指定，默认会初始化一个空的数组，等add第一个元素的时候，容量扩充为10。

添加元素

    @Override
    public boolean add(E e) {
        // 确保最小容量
        int minCapacity = size + 1;
        if (elementData == DEFAULT_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 判断扩容操作
        if (minCapacity > elementData.length) {
            int oldCapacity = elementData.length;
            // 扩容1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 例如添加单个元素但当前容量为 0，则直接使用minCapacity
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
        // 添加元素
        elementData[size++] = e;
        return true;
    }

判断当前容量与初始化容量，使用 Math.max 函数取最大值最为最小初始化空间。
接下来是判断 minCapacity 和元素的数量，是否达到了扩容。首次创建 ArrayList 是一定会扩容的，也就是初始化 DEFAULT_CAPACITY = 10 的容量。
Arrays.copyOf 实际上是创建一个新的空间数组，之后调用的 System.arraycopy 迁移到新创建的数组上。这样后续所有的扩容操作，也就都保持统一了。
使用 elementData[size++] = e添加元素

删除元素

    public E remove(int index) {
        E oldValue = (E) elementData[index];
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;
        return oldValue;
    }

首先需要计算出删除此元素所要移动的元素数，也就是numMoved
使用System.arraycopy拷贝数据的方式去移动数据，把删除掉的元素的位置覆盖掉
然后把末尾的数据（移动后为脏数据）置为null

获取元素

    @Override
    public E get(int index) {
        return (E) elementData[index];
    }

    @Override
    public String toString() {
        return "ArrayList{" +
                "elementData=" + Arrays.toString(elementData) +
                ", size=" + size +
                '}';
    }

自测

    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<>();
        list.add("01");
        list.add("02");
        list.add("03");
        list.add("04");
        list.add("05");
        list.add("06");
        list.add("07");
        list.add("08");
        list.add("09");
        list.add("10");
        list.add("11");
        list.add("12");

        System.out.println(list);

        list.remove(9);

        System.out.println(list);
    }

测试结果