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
