ArrayList源码分析

ArrayList是日常开发中经常使用到的集合，其底层采用数组实现，因此元素按序存放。其优点是可以使用下标来访问元素，时间复杂度是O(1)。其缺点是删除和增加操作需要使用System.arraycopy()来移动部分受影响的元素，时间复杂度为O(N)。同时ArrayList由于是采用数组来存放数据，因此会有容量限制，在使用时需要扩容，当插入操作超出数组长度，就会进行扩容，扩容后数组的长度为原来的1.5倍，默认的数组长度是10。

为了更好的掌握ArrayList，因此阅读并仿照ArrayList源代码，实现一个具有增删改查以及自动扩容功能的简易版MyArrayList（代码几乎与ArrayList源码一致）。

首先新建一个class，命名为MyArrayList。

public class MyArrayList<E> {
}

由于ArrayList是通过数组来存储元素的，因此我们定义一个Object类型的数组elementData来存储数据，再定义一个变量size，用来记录数组中的元素个数，其默认值为0。

public class MyArrayList<E> {
	private Object[] elementData; //ArrayList存储元素的对象数组
	private int size; //ArrayList存储元素的个数
	
}

接下来就是构造函数，有两种，第一种是未指定初始容量的构造函数，默认容量为10；第二种是在构造函数中传入指定容量。

先说第一种构造函数，ArrayList在默认情况下，其容量为10。因此我们定义一个常量DEFAULT_CAPACITY = 10作为默认容量。同时，还定义一个常量数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}用于对elementData进行初始赋值。

public class MyArrayList<E> {
	private Object[] elementData; //ArrayList存储元素的对象数组
	private int size; //ArrayList存储元素的个数

	private final static int DEFAULT_CAPACITY = 10; //ArrayList的对象数组的默认初始容量
	private final static Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList对象数组的默认初始化

	/**
     * 不指定初始容量的构造函数
     */
    public MyArrayList(){
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
}

需要注意的是这里的默认容量10并不是在构造函数中直接使用，而是在第一次插入进行扩容时才会使用。

第二种构造函数，传入指定的容量。根据传入的容量参数，我们有以下三种结果：
①传入的容量参数大于0：则以该参数为容量创建对象数组
②存入的容量参数等于0：则需要创建一个空的对象数组，因此定义一个常量数组EMPTY_ELEMENTDATA = {}用于传入容量为0时的初始化。
③传入的容量参数小于0：明显这是非法的，因此抛出参数异常IllegalArgumentException()

public class MyArrayList<E> {
	private Object[] elementData; //ArrayList存储元素的对象数组
	private int size; //ArrayList存储元素的个数

	private final static int DEFAULT_CAPACITY = 10; //ArrayList的对象数组的默认初始容量
	private final static Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList对象数组的默认初始化
	private static final Object[] EMPTY_ELEMENTDATA = {}; //传入容量为0时的初始化

	/**
     * 不指定初始容量的构造函数
     */
    public MyArrayList(){
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 传入指定初始容量的构造函数
     * @param initialCapacity 传入的初始化容量
     */
    public MyArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("非法的容量: "+
                    initialCapacity);
        }
    }
}

好了，构造函数构建完毕，接下来就是增删改查功能的实现，实现的方法如下：

//增，将元素放到数组末尾元素的后面，e为待插入元素，返回boolean
boolean add(E e)

//删，删除指定位置的元素，index为待删除元素的位置，返回被删除的元素
E remove(int index)

//改，替换指定位置的元素，index为被替换元素的位置，e为替换的元素，返回被替换的元素
E set(int index, E e)

//查，查询指定位置的元素，index为查询的位置，返回查到的元素
E get(int index)

首先是add(E e)方法，由于数组容量有限制，因此我们新增一个元素，都有可能要进行扩容，所以我们需要编写一个函数ensureCapacityInternal来判断是否需要自动扩容，若需要则进行扩容。

 	/**
     * ArrayList的add方法
     * 将元素放到数组末尾元素的后面
     * @param e 待插入的元素
     * @return 
     */
    boolean add(E e){
        //1、自动扩容机制，传入的是目前需要的最小容量
        ensureCapacityInternal(size + 1);
    }

在ensureCapacityInternal函数中，需要传入目前需要的最小容量。同时我们还要判断对象数组elementData是否为空数组，若是，则将传入的目前需要的最小容量与默认容量10进行对比，取其中的最大值作为本次扩容的容量。

/**
     * 判断原数组是否为空数组
     * 是：则选默认容量和目前需要的最小容量二者中的最小值
     * 否：则继续往下判断
     * @param minCapacity 目前需要的最小容量
     */
    void ensureCapacityInternal(int minCapacity){
        // elementData 为空数组，则将传入的minCapacity与默认的初始容量DEFAULT_CAPACITY进行对比，取两者中最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
        }

        //接着往下判断
        ensureExplicitCapacity(minCapacity);
    }

接下来，我们判断是否需要进行扩容。如果目前需要的最小容量大于原数组的长度，才进行扩容，否则不进行扩容，该功能写入函数 ensureExplicitCapacity。

    /**
     * 判断是否需要进行扩容
     * 如果目前需要的最小长度大于原数组的长度，才进行扩容
     * 否则不进行扩容
     * @param minCapacity  目前需要的最小容量
     */
    void ensureExplicitCapacity(int minCapacity){
        //目前需要的最小容量超过原数组长度,才进行扩容，否则就不扩容
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity); //扩容
        }
    }

然后，若进行扩容，则执行扩容函数grow。在grow中，我们需要进行如下操作：
①获取原数组的容量oldCapacity，然后计算出值为oldCapacity1.5倍的新容量newCapacity

int oldCapacity = elementData.length;
//扩容为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);

②将扩容1.倍后的新容量newCapacity与目前需要的最小容量minCapacity进行对比，若新容量小于目前需要的最小容量，则新容量的值取目前需要的最小容量。

if (newCapacity - minCapacity < 0) newCapacity = minCapacity;

③将新容量newCapacity与所允许的数组的最大长度进行对比，数组最大长度定义为常量MAX_ARRAY_SIZE = Integer.MAX_VALUE，值为整数的最大值。如果新容量newCapacity大于数组最大长度MAX_ARRAY_SIZE ，则取目前需要的最小容量minCapacity与数组最大长度MAX_ARRAY_SIZE 两者中的最小值作为新容量newCapacity的值。

 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = (minCapacity - MAX_ARRAY_SIZE) > 0 ? MAX_ARRAY_SIZE : minCapacity;

④使用Arrays.copyOf(原数组, 新长度)进行数组的复制，即实现数组扩容

elementData = Arrays.copyOf(elementData,newCapacity);

完成扩容任务的函数grow如下：

 /**
     * 扩容函数：如何进行扩容（扩多少）
     * ①扩容1.5倍
     * ②若扩容1.5倍还不满足需要的最小容量，则扩容长度为目前需要的最小容量
     * ③若新的容量大于数组所允许的最大长度，则取需要的最小容量与数组所允许的最大长度
     * 两者中的最小值
     * @param minCapacity 目前需要的最小容量
     */
    void grow(int minCapacity){
        int oldCapacity = elementData.length;
        //oldCapacity原数组长右移1位，即相当于除2，最后加原长度，则为扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容1.5倍后的新容量小于需要的最小容量，则新的容量即为传入的最小容量
        if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
        //如果新容量大于数组能够允许的最大长度，则看传入的最小容量与数组最大长度对比，取其中的小者
        if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = (minCapacity - MAX_ARRAY_SIZE) > 0 ? MAX_ARRAY_SIZE : minCapacity;

        //Arrays.copyOf(原数组, 新长度)，返回新数组。使用该函数完成自动扩容
        elementData = Arrays.copyOf(elementData,newCapacity);
    }

至此，就完成了新增时，判断是否需要扩容，并且完成扩容功能。接下来我们只需要将新增元素插入数组元素末尾位置的下一个位置，并返回true即可。

boolean add(E e){
        //1、自动扩容机制，传入的是目前需要的最小容量
        ensureCapacityInternal(size + 1);

        //2、扩容完毕，将元素存入
        elementData[size++] = e;

        return true;
}

最终，新增add方法和自动扩容有关的函数编写完成：

	/**
     * ArrayList的add方法
     * 将元素放到数组末尾元素的后面
     * @param e 待插入的元素
     * @return 
     */
boolean add(E e){
        //1、自动扩容机制，传入的是目前需要的最小容量
        ensureCapacityInternal(size + 1);

        //2、扩容完毕，将元素存入
        elementData[size++] = e;

        return true;
}

	/**
     * 判断原数组是否为空数组
     * 是：则选默认容量和目前需要的最小容量二者中的最小值，然后接着往下判断
     * 否：则直接继续往下判断
     * @param minCapacity 目前需要的最小容量
     */
    void ensureCapacityInternal(int minCapacity){
        // elementData 为空数组，则将传入的minCapacity与默认的初始容量DEFAULT_CAPACITY进行对比，取两者中最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
        }

        //接着往下判断
        ensureExplicitCapacity(minCapacity);
    }

 	/**
     * 判断是否需要进行扩容
     * 如果目前需要的最小长度大于原数组的长度，才进行扩容
     * 否则不进行扩容
     * @param minCapacity  目前需要的最小容量
     */
    void ensureExplicitCapacity(int minCapacity){
        //目前需要的最小容量超过原数组长度,才进行扩容，否则就不扩容
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity); //扩容
        }
    }

	/**
     * 扩容函数：如何进行扩容（扩多少）
     * ①扩容1.5倍
     * ②若扩容1.5倍还不满足需要的最小容量，则扩容长度为目前需要的最小容量
     * ③若新的容量大于数组所允许的最大长度，则取需要的最小容量与数组所允许的最大长度
     * 两者中的最小值
     * @param minCapacity 目前需要的最小容量
     */
    void grow(int minCapacity){
        int oldCapacity = elementData.length;
        //oldCapacity原数组长右移1位，即相当于除2，最后加原长度，则为扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容1.5倍后的新容量小于需要的最小容量，则新的容量即为传入的最小容量
        if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
        //如果新容量大于数组能够允许的最大长度，则看传入的最小容量与数组最大长度对比，取其中的小者
        if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = (minCapacity - MAX_ARRAY_SIZE) > 0 ? MAX_ARRAY_SIZE : minCapacity;

        //Arrays.copyOf(原数组, 新长度)，返回新数组。使用该函数完成自动扩容
        elementData = Arrays.copyOf(elementData,newCapacity);
    }

接下来，就是删除，remove方法。由于该方法传入待删除元素的位置索引index，因此需要检查index
的范围是否符合要求。编写一个函数rangeCheck来检查下标。

	/**
     * 检查index范围
     * 超出范围则抛出异常
     * @param index 数组下标位置
     */
     void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException("哎呀，超出范围了！");
    }

若index没有超出范围，则接下来就是获取索引对应的元素，获取方式很简单，就是elementData[index]即可。考虑到其他方法也会需要通过这样方式来获取对应位置的元素，因此我们将这个操作抽取出来，成为一个函数elementData(),用于获取元素。

 	/**
     * 返回数组中指定位置的元素
     * @param index
     * @return
     */
    E elementData(int index){
        return (E) elementData[index];
    }

那么，目前remove方法前面两个操作我们已经完成

    E remove(int index){
        //1、检查index范围
        rangeCheck(index);
        //2、获取index对应的元素
        E oldValue = elementData(index);
       
    }

删除index元素，需要把该位置后面的所有元素都向前移动一个位置。因此接下来我们就需要将index后面的元素向前移动一个位置。

具体做法是，先计算出需要移动的元素个数numMoved，用数组中最后一个元素的下标减去index即可获得需要移动的元素个数：size-1-index。

然后利用System.arraycopy(）来移动元素，该方法的用法如下：

System.arrayCopy(Object srcArray,int srcPos,Object destArray ,int destPos,int length)
①Object srcArray 原数组（要拷贝的数组）
②int srcPos 要复制的原数组的起始位置（数组从0位置开始）
③ Object destArray 目标数组
④ int destPos 目标数组的起始位置
⑤int length 要复制的长度
从原数组srcArray 取元素，范围为下标srcPos到srcPos+length-1，取出共length个元素，存放到目标数组中，存放位置为下标destPos到destPos+length-1。

我们将原数组和目标数组都设为elementData，然后原数组的起始位置为index+1，目标数组的起始位置为index，要复制的长度设为元素个数numMoved。这样就能做到将数组index位置后面的元素向前移动一位。

不过这样做目标数组的最后一位元素依然是原来的数，因此我们需要将目标数组最后的元素置为null，并且由于是删除，所以元素个数size需要减一。至此，删除方法remove完成。

	/**
     * ArrayList的remove方法
     * @param index 要删除元素的位置
     * @return 返回被删除元素
     */
    E remove(int index){
        //1、检查index范围
        rangeCheck(index);
        //2、获取index对应的元素
        E oldValue = elementData(index);
        //3、计算需要移动的元素的个数
        int numMoved = size - 1 - index;
        //4、将index后面的数往前移动一位
        if (numMoved > 0){
            System.arraycopy(elementData,index + 1, elementData, index, numMoved);
        }
        //5、把最后的元素置为null
        elementData[--size] = null;
        //返回被删除元素
        return oldValue;
    }

增删操作已完成，接下来就是改操作，set()方法。这个方法就比较简单，具体的步骤如下：
①检查index范围
②获取index位置的元素
③将index位置的元素，替换为传入的元素
④返回原先index位置的元素

	/**
     * ArrayList的set
     * @param index 需要修改的位置
     * @param e 需要替换的元素
     */
    E set(int index, E e){
        //1、检查index范围
        rangeCheck(index);

        //2、获取指定位置的元素
        E oldValue = elementData(index);

        //3、替换元素
        elementData[index] = e;

        //4、返回原先index位置的元素
        return oldValue;
    }

最后，就是查操作，get方法。该方法更为简单，只需要先检查index范围，再获取index位置的元素直接返回即可。

	/**
     * ArrayList的get方法
     * @param index
     * @return
     */
    E get(int index){
        //1、检查index范围
        rangeCheck(index);

        //2、获取指定位置的元素
        return elementData(index);
    }

到这里，我们编写的简易版ArrayList的增删改查操作就全部完成了。点进JDK1.8中ArrayList源码可以看到，我们的上面的代码几乎与ArrayList源码一模一样。

最终这个简易版ArrayList所有代码如下：

public class MyArrayList<E> {

    private int size; //ArrayList中实际元素的数量的size
    private Object[] elementData; //ArrayList的对象数组

    private final static int DEFAULT_CAPACITY = 10; //ArrayList的对象数组的默认初始容量
    private final static int MAX_ARRAY_SIZE = Integer.MAX_VALUE; //数组的最大长度，也就是整数的最大值
    private final static Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList的对象数组的默认初始化
    private static final Object[] EMPTY_ELEMENTDATA = {}; //传入容量为0时的初始化

    /**
     * 不指定初始容量的构造函数
     */
    public MyArrayList(){
        elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 传入指定初始容量的构造函数
     * @param initialCapacity
     */
    public MyArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("非法的容量: "+
                    initialCapacity);
        }
    }

    /**
     * ArrayList的add方法
     * 将元素放到数组有效长度的末尾
     * @param e 待插入的元素
     * @return
     */
    boolean add(E e){
        //1、自动扩容机制，传入的是目前需要的最小容量
        ensureCapacityInternal(size + 1);

        //2、扩容完毕，将元素存入
        elementData[size++] = e;

        return true;
    }


    /**
     * 判断原数组是否为空数组
     * 是：则选默认容量和目前需要的最小容量二者中的最小值，然后接着往下判断
     * 否：则直接继续往下判断
     * @param minCapacity 目前需要的最小容量
     */
    void ensureCapacityInternal(int minCapacity){
        // elementData 为空数组，则将传入的minCapacity与默认的初始容量DEFAULT_CAPACITY进行对比，取两者中最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
        }

        //接着往下判断
        ensureExplicitCapacity(minCapacity);
    }

    /**
     * 判断是否需要进行扩容
     * 如果目前需要的最小长度大于原数组的长度，才进行扩容
     * 否则不进行扩容
     * @param minCapacity  目前需要的最小容量
     */
    void ensureExplicitCapacity(int minCapacity){
        //目前需要的最小容量超过原数组长度,才进行扩容，否则就不扩容
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity); //扩容
        }
    }

    /**
     * 扩容函数：如何进行扩容（扩多少）
     * ①扩容1.5倍
     * ②若扩容1.5倍还不满足需要的最小容量，则扩容长度为目前需要的最小容量
     * ③若新的容量大于数组所允许的最大长度，则取需要的最小容量与数组所允许的最大长度
     * 两者中的最小值
     * @param minCapacity 目前需要的最小容量
     */
    void grow(int minCapacity){
        int oldCapacity = elementData.length;
        //oldCapacity原数组长右移1位，即相当于除2，最后加原长度，则为扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容1.5倍后的新容量小于需要的最小容量，则新的容量即为传入的最小容量
        if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
        //如果新容量大于数组能够允许的最大长度，则看传入的最小容量与数组最大长度对比，取其中的小者
        if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = (minCapacity - MAX_ARRAY_SIZE) > 0 ? MAX_ARRAY_SIZE : minCapacity;

        //Arrays.copyOf(原数组, 新长度)，返回新数组。使用该函数完成自动扩容
        elementData = Arrays.copyOf(elementData,newCapacity);
    }

    /**
     * ArrayList的remove方法
     * @param index 要删除元素的位置
     * @return 返回被删除元素
     */
    E remove(int index){
        //1、检查index范围
        rangeCheck(index);
        //2、获取index对应的元素
        E oldValue = elementData(index);
        //3、计算需要移动的元素的个数
        int numMoved = size - 1 - index;
        //4、将index后面的数往前移动
        if (numMoved > 0){
            System.arraycopy(elementData,index + 1, elementData, index, numMoved);
        }
        //5、把最后的元素置为null
        elementData[--size] = null;
        //返回被删除元素
        return oldValue;
    }

    /**
     * 检查index范围
     * 超出范围则报错
     * @param index
     */
    void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException("哎呀，超出范围了！");
    }

    /**
     * 返回数组中指定位置的元素
     * @param index
     * @return
     */
    E elementData(int index){
        return (E) elementData[index];
    }


    /**
     * ArrayList的set
     * @param index 需要修改的位置
     * @param e 需要替换的元素
     */
    E set(int index, E e){
        //1、检查index范围
        rangeCheck(index);

        //2、获取指定位置的元素
        E oldValue = elementData(index);

        //3、替换元素
        elementData[index] = e;

        //4、返回原先index位置的元素
        return oldValue;
    }

    /**
     * ArrayList的get方法
     * @param index
     * @return
     */
    E get(int index){
        //1、检查index范围
        rangeCheck(index);

        //2、获取指定位置的元素
        return elementData(index);
    }


    /**
     * 获取元素个数
     * @return
     */
    int size(){
        return size;
    }

}

我们测试一下，这个简易版ArrayList

 public static void main(String[] args) {
        MyArrayList<String> myArrayList = new MyArrayList<>();
        //增
        myArrayList.add("hello");
        myArrayList.add("word");
        myArrayList.add("hello");
        myArrayList.add("java");
        //改
        myArrayList.set(1,"####");
        //删
        myArrayList.remove(2);
        //查
        for (int i = 0; i < myArrayList.size(); i++){
            System.out.println(myArrayList.get(i));
        }

    }

测试结果如下：

hello
####
java