动态数组也是一个常用的集合类，stl 中的 vector、util 中的 ArrayList 就是动态数组。
一 ArrayList 添加操作的平均复杂度是 O(1)
ArrayList 中使用成员数组 Object[] elementData 存储数据，还有一个成员变量 int size 表示数组中存储的数据的个数，elementData[0..size-1] 存储着 size 个数据。 size <= elementData.length，当有必要扩大数组容量时，就要给 elementData 重新申请空间，并将原来所有的数据拷贝到新数组中。
看起来好像 ArrayList 添加元素的时间复杂度会很挫，但实际上 n 次 add 操作的平均复杂度是 O(1)。
首先我写了一个测试程序，其中使用了 ArrayList 的 add 操作，这样我就可以选中 add 然后转到它的源代码：
import java.util.ArrayList;
public class Temp {
public static void main(String[] args) {
ArrayList<Integer> a = new ArrayList<Integer>();
a.add(2013);
}
}
下面是我看到的 add 的源代码，我加了几行注释：
// 添加单个元素 e
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 保证 elementData 能容纳 size+1 个元素
elementData[size++] = e;
return true;
}
// 保证 elementData 能容纳 minCapacity 个元素
private void ensureCapacityInternal(int minCapacity) {
modCount++; // 修改次数自增，多线程中通过比对这个次数发现竞争
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 数组的一次增长，且一定保证 minCapacity 个元素的容量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 现在 newCapacity 是 MAX(minCapacity, 1.5 * oldCapacity)
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
从这 3 个函数中就可以看出 add 的过程：如果数组还没填满 add 直接追加一个元素；否则先扩容为原来的 1.5 倍，再追加一个元素。
现在来算一下平均时间复杂度：假设一个 ArrayList 对象中的 elementData 经过 n 次 add 操作增长为长度为 n 的数组，这时数组刚好装满，那么可得出有 n 次追加操作，还有
次扩容造成的元素拷贝操作，于是 n 次 add 总共花费了 3n 个单位时间，平均下来 add 的复杂度就是 O(1) 了。
二 链表和动态数组的对比
有时候我们可能会纠结于一个集合到底是用链表还是用动态数组来表示，这个时候我们就要根据需求来判断：
- 如果集合要进行排序或二分查找，那么它需要能随机访问， ArrayList 的 get(index) 操作的复杂度是 O(1)， LinkedList 的 get(index) 操作的复杂度是 O(n)，所以选动态数组。
- 如果集合要不断添加/删除元素，那么选链表是最好的。链表在任意位置添加/删除一个元素的复杂度都是 O(1)，而动态数组可能还要移动数组中的其他元素。