作为一个android开发者，大家在平时的开发工作当中，一定会大量用到ArrayList来管理数据。不外乎调用它的添加，删除等方法。但是具体怎么实现就不清楚了。而且，最让我感到蛋疼的就是，很多面试的时候，面试官必然少不了深挖这些java知识，每次我都很懵逼啊有没有。于是我们就来深入源码了解它，揭开这层遮羞布。
好了，废话不多说，我们开始ArrayList的学习。文章中会有大量源码，这是避免不了的。
ArrayList是一个可以动态调整大小的List实现，其数据的顺序与插入顺序始终一致，其余特性与List中定义的一致。
what?数据顺序与插入顺序一致？难道你底层实现是依靠数组吗？我也还不知道呢。那我们继续往下学习
我们首先看类的关系
可以看到，
ArrayList是AbstractList的子类，同时实现了List接口。除此之外，它还实现了三个标识型接口，这几个接口都没有任何方法，仅作为标识表示实现类具备某项功能。RandomAccess表示实现类支持快速随机访问，Cloneable表示实现类支持克隆，具体表现为重写了clone方法，java.io.Serializable则表示支持序列化，如果需要对此过程自定义，可以重写writeObject与readObject方法。
我们如果要使用ArrayList首先我们就要new一个，而我们通常的做法就是下面这样：
ArrayList<String> strings = new ArrayList<>();
我们追寻这个构造函数进入源码：为了方便大家观看，我们将解释放入到每一句代码中。在本文中这些注释很重要。
/**
* 默认初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
/**
* 构建一个指定初始容量的list
*
* @param list的指定容量
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//这里就可以看出，list内部就是维护的一个基本的一维数组。并且初始化了大小。
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//elementData为空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 初始化大小为10的空数组
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//这个方法基本不用，不做过多解释
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
我们可以看到，它拥有三个构造方法。而我们常用的就是第二个，空参的方法。官方的解释是我们构建了一个空的list，初始容量为10。看到这里我们就不禁产生两个思考。
我们可以看到list中维护了一个重要的elementData而它的定义是一个数组，它有什么用？
明明你构造方法就一个简单的赋值，而且这个变量我不知道干嘛的，哪来的10的容量？
我们先不管这两个疑问。我们都知道数据的操作最重要的就是增删改查，改查都不涉及长度的变化，而增删就涉及到动态调整大小的问题。
我们就从这四个方面再来分析分析源码：
增
我们首先看添加元素：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//这里不就是添加数据了？？？？？
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
添加元素有两个方法可以使用，先看第一个方法，我们一行一行的看。首先我们看到这个方法ensureCapacityInternal(size + 1);在它之后，elementData[size++] = e;将我们要插入的数据赋值给了elementData数组。
到这里我们终于可以知道，ArrayList内部就是通过elementData数组实现的。并且添加数据是从位置0开始。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
我们刚创建一个新的ArrayList，可以知道当第一次调用add方法，这里的size=0。并且满足这里的if语句，这里minCapacity的值将变为我们初始化的10。
然后到ensureExplicitCapacity(minCapacity);方法。
private void ensureExplicitCapacity(int minCapacity) {
//这个变量主要作用是防止在进行一些操作时，改变了ArrayList的大小，那将使得结果不可预测。
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
最后执行了grow(minCapacity);扩容的方法。
/**
*增加容量以确保它能存下数据
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// 数组的容量，按我们流程来这里oldCapacity=0，因为还没有执行数组的赋值操作
//minCapacity=10
int oldCapacity = elementData.length;
//新的容量为原来的1.5倍
//newCapacity=0；
int newCapacity = oldCapacity + (oldCapacity >> 1);
//新的容量不够，直接将minCapacity作为容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//防止溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 如果是第一次执行，就可以看出这里的newCapacity =10
elementData = Arrays.copyOf(elementData, newCapacity);
}
最后执行了elementData = Arrays.copyOf(elementData, newCapacity);到这里，我们就可以看出来是怎么扩容了。我们继续看最后一行有一个copyOf方法。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
最后到了native的复制方法，这个方法就是将数组进行复制。
/* @param src 源数组（要复制的数组）
* @param srcPos 源数组开始的位置（要将源数组复制的开始位置）
* @param dest 目标数组（将源数组复制到的另一个数组）
* @param destPos 目标数组的开始位置（将复制的元素存入的开始位置）
* @param 复制的长度
* @exception IndexOutOfBoundsException if copying would cause
* access of data outside array bounds.
* @exception ArrayStoreException if an element in the <code>src</code>
* array could not be stored into the <code>dest</code> array
* because of a type mismatch.
* @exception NullPointerException if either <code>src</code> or
* <code>dest</code> is <code>null</code>.
*/
@FastNative
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
通过以上方法我们再回到grow(int minCapacity)的最后一句
elementData = Arrays.copyOf(elementData, newCapacity);
底层通过System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
将elementData数组复制到了一个新的容量为10的数组copy中，然后将新数组赋给elementData。
不难发现我们将执行的添加操作是将elementData复制到新的数组，由此可以看出每次添加元素都会涉及到数组的copy操作，这样在一定程度上是很耗费资源的。
到这里我们来从新梳理下当我们第一次从创建到调用add(E e)方法的整个流程。
- 1.首先构造方法生成一个空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 2.调用add方法
public boolean add(E e) {
//通过一系列判断是否扩容，第一次调用到grow()方法完成，才算初始化真正完成。此时elementData才是容量为10的数组。
ensureCapacityInternal(size + 1);
// 然后将元素添加到elementData数组
elementData[size++] = e;
return true;
}
那么当我们元素等于10，这时我们插入第11个元素呢？
我们来看，此时的的各个方法的参数如下值：
size=10
ensureCapacityInternal(11)
ensureExplicitCapacity(11)
grow(11)
int oldCapacity =10;
int newCapacity = 15;
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, 15);
到这里可以看出每次grow()方法都会先进行扩容。然后通过
为了方便观看这里直接跳过语法正确性进行赋值
original=elementData ;
copy=new Object[15];
System.arraycopy(original, 0, copy, 0,
Math.min(original.length=10, newLength=15));
将原来的十个数据copy到新数组后赋值给elementData 。
这样其实就是每次添加数据都会扩充数组大小，但是实际元素个数size一般是小于elementData.length的，也就是list中的元素个数实际小于容量。
我们在看添加的第二个方法public void add(int index, E element)
第一步它也是先做了是否扩容的操作，确保数组容量足够。然后将原数据复制到扩充后的数组，最后在相应的位置插入值。整个流程如下图：
删
删除操作总共有三个方法，一个是根据索引删除，一个是直接删除元素，最后一个是清空list的clear方法，clear()方法是用for循环将所有元素置空。
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
//查找到要删除的元素
E oldValue = (E) elementData[index];
//要移动（copy）的长度
int numMoved = size - index - 1;
if (numMoved > 0)
//数组的copy移动
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将最后的地方置空回收
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
//该方法其实内部实现其实是根据下标找到该元素，最后执行了remove(index)方法
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
我们还是用图来说明一下删除操作的过程：
改
改动元素的方法只有一个而且很简单，它的操作就是找到该元素然后进行重新赋值就可以。
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
查
就一个方法，内部就是数组的位置查找。
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
到在这里基本的数据操作就分析完了。我们也可以回答之前的疑问。
ArrayList我们可以理解为一个可以动态扩容的数组，内部通过elementData数组来管理。
它的每次操作都会进行copy，如果数据量小，其实影响不大。但是当数据量很大，这样就会影响性能。我们要缓解这样的问题可以有下面两种方法可以使用：
- 使用
ArrayList(int initialCapacity)这个有参构造，在创建时就声明一个较大的大小，这样解决了频繁拷贝问题，但是需要我们提前预知数据的数量级，也会一直占有较大的内存。 - 除了添加数据时可以自动扩容外，我们还可以在插入前先进行一次扩容。只要提前预知数据的数量级，就可以在需要时直接一次扩充到位，与
ArrayList(int initialCapacity)相比的好处在于不必一直占有较大内存，同时数据拷贝的次数也大大减少了。这个方法就是ensureCapacity(int minCapacity)，其内部就是调用了ensureCapacityInternal(int minCapacity)方法。
所以对于ArrayList和数组一样，更适合于数据随机访问，而不太适合于大量的插入与删除。
