【Java集合】ArrayList源码分析

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

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

首先新建一个class，命名为<code>MyArrayList</code>。

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

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

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

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

第二种构造函数，传入指定的容量。根据传入的容量参数，我们有以下三种结果：

①传入的容量参数大于0：则以该参数为容量创建对象数组

②存入的容量参数等于0：则需要创建一个空的对象数组，因此定义一个常量数组EMPTY_ELEMENTDATA = {}用于传入容量为0时的初始化。

③传入的容量参数小于0：明显这是非法的，因此抛出参数异常IllegalArgumentException()

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

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

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

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

然后，若进行扩容，则执行扩容函数grow。在grow中，我们需要进行如下操作：

①获取原数组的容量oldCapacity，然后计算出值为oldCapacity1.5倍的新容量newCapacity

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

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

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

完成扩容任务的函数<code>grow</code>如下：

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

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

接下来，就是删除，remove方法。由于该方法传入待删除元素的位置索引index，因此需要检查index

的范围是否符合要求。编写一个函数rangeCheck来检查下标。

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

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

删除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完成。

增删操作已完成，接下来就是改操作，set()方法。这个方法就比较简单，具体的步骤如下：

①检查index范围

②获取index位置的元素

③将index位置的元素，替换为传入的元素

④返回原先index位置的元素

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

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

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

我们测试一下，这个简易版<code>ArrayList</code>

测试结果如下：