本文是对 JDK1.8 中 ArrayList 的分析与总结，在阅读源码的同时加深对其提供的方法的使用，以便更好的理解。
总览
在了解 ArrayList 之前，我们不妨看一看集合框架中的重要成员 List，不管是 Vector、LinkedList 还是 ArrayList，它们都实现了 List 接口。而 List 本身又继承了 Collection 接口，拥有 Collection 提供的所有方法，同时也实现了一些自身常用的方法。
List 结构具有以下特点：
- 可以包含 null；
- 元素可以重复存在；
- List 中的元素是按照插入的顺序进行“有序”存储的；
- 对于常用的 ArrayList 和 LinkedList 是不是线程安全的，而 Vector 是线程安全的，即 synchronized。
下图给出了它们之间的继承关系：
ArrayList
从源码中可以看到，ArrayList 继承了AbstractList 类，同时实现了 List、RandomAccess、Cloneable 以及 java.io.Serializable 接口。因此 ArrayList 可以支持序列化传输、支持快速的随机访问以及克隆功能。如下所示：
1
2
|
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
|
下面给出了它们之间详细的继承图：
ArrayList 是 List 的可变数组的实现，即可以将 ArrayList 理解为动态数组，其数组的容量是动态增长的。下面看一下 ArrayList 的域有哪些：
域
这里有几个比较重要的域：
DEFAULT_CAPACITY：默认的初始化容量为 10；EMPTY_ELEMENTDATA：当指定 ArrayList 的容量为 0 时，返回该空数组；DEFAULTCAPACITY_EMPTY_ELEMENTDATA：当调用 ArrayList 的无参构造时，返回该空数组；elementData：用于存储数据的数组；size：数组中包含元素的个数，非数组长度。
源码如下：
其中，被关键字transient修饰的属性在对象被序列化时不会被保存。
1
2
3
4
5
6
7
8
9
|
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
|
构造方法
ArrayList 提供了三个构造方法，如下所示：
第一个是给定一个初始容量的构造方法：
1
2
3
4
5
6
7
8
9
|
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
|
第二个是默认无参的构造函数，数组的初始化容量为 10：
1
2
3
|
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
|
第三个是一个包含指定集合的构造函数：
1
2
3
4
5
6
7
8
9
|
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
|
添加
为了保证能够顺利的对元素进行添加，ArrayList 提供了一些例如边界检查、调整数组容量等方法，如下所示：
1
2
3
4
5
6
7
8
9
10
11
|
// 检查给定的 index 是否在数组的范围内
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 用于 add 和 addAll 方法使用的索引检查方法
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
|
下面是进行扩容校验的方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
|
可以看到，在每次向数组中添加元素的时候，都需要去检查添加后的元素的个数是否会超出当前数组的长度，即ensureCapacityInternal方法。如果超出，则会将数组进行扩容。
第26行的grow方法即为扩容的最终实现，如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 扩容后的新数组的长度约为原数组长度的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
|
等到计算完新的数组的容量时，再次对容量大小进行检查，最后通过Arrays.copyOf函数将老数组中的元素重新拷贝到新数组中。
ArrayList 中提供了四个添加元素的方法，下面分别进行介绍：
如下所示，该方法将指定的元素添加到列表的尾部，再添加之前，当然需要检查一下数组是否还有容量，以便确保能够进行插入操作。
1
2
3
4
5
|
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
|
如下所示，该方法将指定元素（element）插入到指定的位置（index）。如果index位置已经有元素了，则将index位置及其后面size - index长度的元素拷贝到index + 1位置。换句话说，就是将index及其之后的元素往后移动一位，给新插入的元素留出空位。由此可见，ArrayList 对于插入操作来说，是非常耗时的。
1
2
3
4
5
6
7
8
9
|
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
|
下面是两个addAll方法，再添加元素的过程中，也涉及到了元素的拷贝操作，如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
|
修改
用指定的元素替代数组中指定位置上的元素，返回以前位于该位置上的元素，如下所示：
1
2
3
4
5
6
7
|
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
|
查询
即返回数组中指定索引上的元素，如下所示：
1
2
3
4
5
|
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
|
删除
常用的删除操作有根据索引删除元素以及根据指定的对象删除元素。先看第一种情况，首先检查index是否在指定的范围，确保index不越界；然后暂存被删除的元素，用于最终返回；最后将index + 1及其后面的元素往前移动一个位置，再将最后那个空出来的位置填上null即可。如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
return oldValue;
}
|
第二种情况是根据指定的对象进行删除，这里需要注意一下。由于 ArrayList 可以存储相同的元素，所以此方法删除的是在该列表中第一次出现的元素，删除成功返回 true，如果列表中不包含该元素，则返回 false。如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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;
}
|
这里使用了私有的方法fastRemove移除元素，原因是该方法跳过了边界检查，并且不返回已删除的元素。其方法如下：
1
2
3
4
5
6
7
8
|
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;
}
|
总结
在明确了 ArrayList 的相关操作之后，可以看到它确实不适合用来进行插入、删除操作，因为这需要移动大量的元素，即对元素进行复制操作。但是基于数组的特性，ArrayList 在查询方面的效率非常高，可直接通过索引找到指定位置的元素。
其次，ArrayList 的数组是支持动态扩充的，通过newCapacity = oldCapacity + (oldCapacity >> 1);语句可以在元素过多而数组容量不足的情况下对数组进行动态的增长。
然后，ArrayList 可以存储元素为 null 的情况，在进行删除操作时，会根据某元素是否为 null 而分别进行对应的删除操作。
最后，AarrayList 不是线程安全的，在多个线程同时访问一个 ArrayList 实例的时候，需要特别注意线程同步问题。