ArrayList可以说是我们在java中最经常使用的数据结构之一了，它为我们提供了方便灵活的可变长度列表实现，并可以高效的存取。因此，作为一个如此亲密的朋友，我们自然是要走近它，一探究竟了。
一.类定义
ArrayList位于java.util包，其定义如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看到ArrayList继承自AbstractList类，并实现了List接口、RandomAccess接口、Cloneable接口、Serializable接口。继承关系如下图所示：
位于继承关系最顶端的是Iterable接口，该接口只有一个方法：
// 获取一个可以应用于一组元素的迭代器
Iterator<T> iterator();
通过迭代器来遍历元素是很多容器类的共有特性，其他的还有Set系列的类。
Collection接口声明了很多容器操作方法，例如add、contains、remove等。
Collection的概念还是比较宽泛的，像Set家族的很多类、Queue家族的很多类都实现了该方法。而List就更具体了，它表示列表，可以按下标进行存取。
除了List接口外，ArrayList还实现了Serializable接口、RandomAccess接口、Cloneable接口，这三个接口本身都没有任何方法，只起到标识作用。Serializable接口使对象能够被序列化和反序列化；RandomAccess声明了ArrayList类的实例可以被随机访问，也就是可以通过下标的方式来访问列表中的元素；Cloneable接口为了实现Object类中的clone方法，从而获得对象的副本，有关clone方法我们在jdk源码分析（一）中已有提到，此处不再赘述。
二.存储结构
既然ArrayList类中的元素可以被随机访问，在java中，能够实现这一点的基础数据结构也只有数组了。我们查看源代码，也可以发现：ArrayList中的所有元素保存在一个对象数组中：
// 存储列表元素
private transient Object[] elementData;
// 记录列表中元素个数
private int size;
三.常用方法
1.构造方法
ArrayList共有三个构造方法：
// 指定初始化容量
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
// 不指定初始化容量，默认容量为10
public ArrayList() {
this(10);
}
// 复制另一个容器类中的元素到ArrayList
public ArrayList(Collection<? extends E> c) {
// c.toArray将会产生一个新的数组，因此elementData是一份拷贝
elementData = c.toArray();
size = elementData.length;
// elementData的类型可能不是Object[]
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
这个方法值得我们注意：在对elementData和size赋值后，又检查了elementData的类型，我们看Collection接口的文档，看到toArray方法返回的是Object[]类型，而我们声明的elementData也是Object[]类型的，这不是正好匹配吗？为什么还要判断类型呢？
这是由于java中广泛存在类的继承关系，父类中的方法常常会被子类重写，有时候toString方法返回的未必是Object[]类型，我们看下面的例子：
class A {}
public class MyList<A> extends ArrayList<A> {
public MyList() {
super();
}
// 重写toArray方法
@Override
public String[] toArray() {
String[] array = new String[super.size()];
for (int i = 0; i < super.size(); i++) {
array[i] = super.get(i).toString();
}
return array;
}
}
上面代码中，我们实现了一个特殊的ArrayList类，并重写toArray方法，然后我们执行以下操作：
List<A> list = new MyList<A>();
list.add(new A());
Object[] array = list.toArray();
// 输出false
System.out.println(array.getClass() == Object[].class);
// 输出class [Ljava.lang.String;
System.out.println(array.getClass());
// throw java.lang.ArrayStoreException
// array[0] = new A();
Object[] objectArray = Arrays.copyOf(array, array.length, Object[].class);
// 输出true
System.out.println(objectArray.getClass() == Object[].class);
我们我们调用list.toArray()方法，虽然可以得到Object数组，但其实得到的是String数组，这可以通过打印array.getClass()看出。如果此时，我们将一个A类型的对象放入数组，将会抛出ArrayStoreException异常。执行完Arrays.copyOf的操作后，我们才算将String数组转换为Object数组。
此时，我们明白了，ArrayLis的这个构造方法进行类型检查是完全有必要的，可以确保类型安全。
2.add方法
在完成了列表实例的初始化后，就可以往列表中添加元素了，这就要用到add方法，我们这里只看最简单的add()方法：
public boolean add(E e) {
// 确保对象数组中有足够的空间可以容纳新的列表元素
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}
public void ensureCapacity(int minCapacity) {
// 记录列表发生结构性变化的次数
modCount++;
int oldCapacity = elementData.length;
// 需要进行扩容
if (minCapacity > oldCapacity) {
// oldData复制后并没有被用到，不知道是不是无用代码？
Object oldData[] = elementData;
// 按照固定的公式计算扩容后的大小
int newCapacity = (oldCapacity * 3)/2 + 1;
// 扩容后依然小于所需要的大小，将新的数组大小设置为所需大小
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// 将旧有元素拷贝到新的数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
在执行添加操作前，会首先检查数组大小是否足以容纳新的元素，如果不够，就进行扩容，扩容的公式是：新的数组大小=(老的数组大小*3)/2 + 1，例如初始时数组大小为10，第一次扩容后，数组大小就为16，再扩容一次变为25。
值得注意的是，在操作过程中有一个变量似乎与添加元素的操作并无关系：modCount。但其实这个变量也十分重要，它主要用于记录列表发生结构性变化的次数，例如列表的长度发生变化，modCount就会递增。其作用主要体现在多线程当中，可能我们在一个线程中正在读ArrayList中的元素，但另一个线程却插入了一个元素，那么我们就可以及时发现，从而做一些安全处理。modCount字段定义在父类AbstractList中：
protected transient int modCount = 0;
3.get方法
在向列表中添加完元素后，后续可能需要取出，ArrayList支持按照下标来读取列表元素。
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
// 边界检查
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
get方法比较简单，首先进行一次边界检查，判断所请求的下标是否越界，如果越界，抛出IndexOutOfBoundsException异常，如果不越界，则取出数组元素，转换为相应元素类型，返回。
4.indexOf方法
有时，我们会需要检查列表中是否包括某个元素，那么就可以使用indexOf方法，该方法将返回被检查元素在列表中的下标，如果未找到该元素，则返回-1。
// 查找列表中是否存在元素o
public int indexOf(Object o) {
// 如果o为null
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else { // 如果o不为null
for (int i = 0; i < size; i++)
// 是否equals进行比较
if (o.equals(elementData[i]))
return i;
}
return -1;
}
代码逻辑清晰明了，不再赘述，但有以下两点值得注意：
（1）保存到列表中的元素可以为null；
（2）在进行元素比较时，使用的是equals方法，也就是内容比较。
5.remove方法
我们可以通过使用remove方法将指定下标的元素删除：
public E remove(int index) {
// 边界检查
RangeCheck(index);
// 删除元素必然要改变列表结构，因此modCount递增
modCount++;
// 记录待删除的元素
E oldValue = (E) elementData[index];
// 需要被移动的元素
int numMoved = size - index - 1;
// 如果有元素需要被移动，则将需要被移动的元素顺次往前移动一个位置
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 移动后，最后一个位置已经没有用了，置为null，等待被垃圾回收
elementData[--size] = null; // Let gc do its work
return oldValue;
}
元素的删除操作效果如下：
四.相关类
除了ArrayList外，Java中还有几个容器类拥有线性存储结构：
- LinkedList：链式存储结构，以链表的形式存储列表元素；
- Vector：向量，方法与
ArrayList非常类似，但列表操作都是同步的，线程安全。
LinkedList与ArrayList的主要区别如下：
（1）存储结构不同。LinkedList以链表的形式存储元素，ArrayList以数组的形式存储元素；
（2）使用场景不同。LindedList随机访问性能差，但插入和删除效果较高；ArrayList随机访问性能高，但插入和删除性能较差，两者正好互补。
Vector与ArrayList的主要区别如下：
（1）Vector是线程安全的，ArrayList不是线程安全的；
（2）扩容方式不同。ArrayList按照新的数组大小=(老的数组大小*3)/2 + 1的公式进行扩容；Vector则可以指定每次扩容的增量，若不指定，则每次扩为为原有大小的2倍。
本文已迁移至我的博客：http://ipenge.com/25632.html
