Java动态数组实现（模拟ArrayList）

目标：手动实现一个动态数组，模拟ArrayList

ArrayList会自动扩容，先来看一下ArrayList扩容规律，size()方法只能得到存储元素的个数，得不到List的容量大小，我们要想办法：

public static void main(String[] args) throws Exception {
        //构建一个初始容量为3的ArrayList对象
        List<Integer> list = new ArrayList<>(3);
        //通过源码可知ArrayList的元素存储在Object[] elementData成员数组中，通过反射可得到该成员变量
        Class<? extends List> clazz = list.getClass();
        Field f = clazz.getDeclaredField("elementData");
        f.setAccessible(true);
        
        //循环增加添加元素，同时通过反射得到elementData成员，并将每一次遍历的所得到的elementData数组长度添加到Set集合中（利用Set去重）
        Set<Integer> addSet = new HashSet<>();
        for (int i = 0; i < 100; i++) {
            list.add(i);
            Object[] objects = (Object[]) f.get(list);
            addSet.add(objects.length);
        }
        //循环遍历Set，将Set元素转动到一个List中（因Set存储的元素无序，不方便查看）
        List<Integer> addList = new ArrayList<>();
        for (Integer i : addSet) {
            addList.add(i);
        }
        //List排序并打印
        Collections.sort(addList);
        for (Integer i : addList) {
            System.out.print(i + " ");
        }
        System.out.println();
        //移除元素，查看elementData长度变化，思路同上
        Set<Integer> removeSet = new HashSet<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            list.remove(i);
            Object[] objects = (Object[]) f.get(list);
            removeSet.add(objects.length);
        }
        List<Integer> removeList = new ArrayList<>();
        for (Integer i : removeSet) {
            removeList.add(i);
        }
        Collections.sort(removeList);
        for (Integer i : removeList) {
            System.out.print(i + " ");
        }
    }

运行得到结果：

3 4 6 9 13 19 28 42 63 94 141 
141

规律：

1. 添加元素时，容量变化规律：扩容后容量 = 当前容量 * 3 / 2，再向下取整；改变初始容量后，发现规律相同
2. 移除元素时，容量不会缩减

根据上面规律，实现一个具备相同扩容规律的动态数组（由于实现List接口，需重写方法太多，这里就不实现List接口了，只模拟增删改查的方法）：

public class MyList<E> {
    //当前List的元素个数
    private int size;
    //默认容量
    private static final int DEFAULT_INIT_CAPACITY = 10;
    //数组
    private Object[] elementData;

    //默认构造器
    public MyList() {
        elementData = new Object[DEFAULT_INIT_CAPACITY];
    }
    //可指定容量的构造器
    public MyList(int initCapacity) {
        elementData = new Object[initCapacity];
    }

    //添加元素
    public void add(E e) {
        //添加元素前判断当前元素个数和数组长度是否相同，相同则需要扩容
        if (size == elementData.length) {
            Object[] dest = new Object[elementData.length * 3 / 2];
            System.arraycopy(elementData, 0, dest, 0, elementData.length);
            elementData = dest;
        }
        elementData[size++] = e;
    }

    //移除元素
    public void remove(int index) {
        System.arraycopy(elementData, index + 1, elementData, index, elementData.length - index - 1);
        elementData[--size] = null;
    }

    //修改元素
    public void modify(int index, E e) {
        //检查下标是否超出范围
        rangeCheck(index);
        elementData[index] = e;
    }

    //查找元素
    public E get(int index) {
        //检查下标是否超出范围
        rangeCheck(index);
        return (E) elementData[index];
    }

    //范围检查
    private void rangeCheck(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("下标越界,index：" + index);
        }
    }

    //获取当前存储元素个数
    public int size() {
        return size;
    }

    //打印（用于测试）
    public void print() {
        System.out.print("[");
        for (int i = 0; i < size; i++) {
            if (elementData[i] != null) {
                if (i != size - 1) {
                    System.out.print(elementData[i] + ", ");
                } else {
                    System.out.print(elementData[i]);
                }
            }
        }
        System.out.println("]");
    }
}

测试结果：

public static void main(String[] args) {
        MyList<String> myList = new MyList<>(10);
        myList.add("a");
        myList.add("b");
        myList.add("c");
        System.out.println(myList.size());//3

        myList.print();//[a, b, c]
        myList.remove(myList.size() - 1);
        myList.print();//[a, b]
        myList.modify(0, "aa");
        myList.print();//[aa, b]
        System.out.println(myList.get(1));//b
    }