List 容器
- ArrayList：使用动态数组保存元素，支持随机访问。
- Vector：与 ArrayList 类似，但是它是线程安全的。
- LinkedList：使用双向链表保存元素，只能顺序访问，此外可以用作为栈、队列和双向队列。
1 ArrayList
1.1 简介
基于动态数组实现了 List 接口。除了 List 接口的所有方法之外，还提供了调整内部数组大小的方法。该类与 Vector 类大致相同，区别在于 ArrayList 是不支持同步 的。
size，isEmpty，get，set，iterator 和 listIterator 方法都只需时间复杂度为 O(1)。其他的操作时间复杂度为 O(n)。且常数因子与 LinkedList 类相比更低。
每个 ArrayList 实例都有一个capacity，描述了该列表中实际用于存储元素的数组的大小。当向列表中添加元素时，capacity 会自动增大。使用 ensureCapacity 方法，可以在向列表中添加大量元素之前先使数组扩容，避免列表自身多次自动扩容。
1.2 存储结构
ArrayList 内部使用一个数组来保存元素，ArrayList 的容量就表示该数组的大小，
transient Object[] elementData; // non-private to simplify nested class access任何空的 ArrayList 中的 elementData 数组用一个默认的空数组表示，
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};当向空 ArrayList 中添加第一个元素时，会扩容到 DEFAULT_CAPACITY 大小，
private static final int DEFAULT_CAPACITY = 10;此外，ArrayList 中还使用一个 size 记录当前保存元素的个数,
private int size;1.3 添加元素
add(E e)方法可以向 ArrayList 的末尾添加一个元素，
public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}其中会先调用 ensureCapacityInternal(int minCapacity) 方法对 elementData 数组的大小进行检查与扩容，
private void ensureCapacityInternal(int minCapacity) {
// ensureCapacity 方法返回数组所需要的大小
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}然后调用 ensureExplicitCapacity(int minCapacity) 方法，
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}使用 grow(int minCapacity) 方法对数组进行扩容并复制旧数组的元素到新数组中，
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 先设置新容量为旧容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量小于传入的要求容量，则新容量以要求容量为准
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE（2^31-1-8）if (newCapacity - MAX_ARRAY_SIZE > 0)
// 判断要求容量的大小是否大于 MAX_ARRAY_SIZE（2^31-1-8）// 若要求容量大于 MAX_ARRAY_SIZE（2^31-1-8），则新容量为 Integer.MAX_VALUE（2^31-1）// 否则新容量为 MAX_ARRAY_SIZE（2^31-1-8）newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 将旧数组元素复制到新数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}1.4 获取元素
get(int index)方法返回列表中指定位置的元素，
public E get(int index) {
// 检查下标是否合法
rangeCheck(index);
// 返回元素
return elementData(index);
}1.6 删除元素
remove(int index)方法删除列表中指定位置的元素并将其返回，
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);
// 将数组最后一位设为 null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}1.6 fast-fail 机制
fail-fast 机制是 java 集合（Collection）中的一种错误机制。作用是在集合的迭代器的迭代期间，如果发现集合被其他线程修改，则抛出异常，避免执行一些不确定的操作。
例如：当某一个线程 A 通过迭代器去遍历某集合的过程中，若该集合的内容被其他线程所改变了，那么线程 A 访问集合时，就会抛出 ConcurrentModificationException 异常，产生 fail-fast 事件。
实现方式：
AbstractList中有一个 modCount 字段用于记录容器 结构发生变化 的次数，
protected transient int modCount = 0;结构变化指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，若仅仅设置元素的值不算作结构发生变化，例如，
public boolean add(E e) {ensureCapacityInternal(size + 1); // 增加 modCount
elementData[size++] = e;
return true;
}
public E remove(int index) {rangeCheck(index);
modCount++; // 增加 modCount
E oldValue = elementData(index);
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
return oldValue;
}在使用 ArrayList 的迭代器时，迭代器中会记录当前列表的modCount，
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount; // 记录创建迭代器时，容器的 modCount
...
}在使用迭代器的 next()，remove()，previous()，set() 或add()方法时，会通过检测该字段，判断容器是否被意外地修改了，
// 迭代器类中定义的检查 modCount 的方法，在迭代时容器被意外修改时抛出异常
final void checkForComodification() {if (modCount != expectedModCount)
throw new ConcurrentModificationException();}如果容器的 modCount 与迭代器中记录的 expectedModCount 不一致，即容器在迭代器遍历期间被修改，就会返回 ConcurrentModificationException 异常。
2 Vector
2.1 同步
Vector 的实现与 ArrayList 相似，不过使用了 synchronized 进行同步，
// 添加元素
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
// 获取元素
public synchronized E get(int index) {if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
// 删除元素
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}2.2 ArrayList 与 Vector
- Vector 是同步的，所以开销比 ArrayList 大，性能较低。
- Vector 每次扩容默认请求的大小是原容量的 2 倍（可通过
capacityIncrement设置），ArrayList 则是原容量 1.5 倍。
3 LinkedList
3.1 存储结构
LinkedList 使用双向链表保存元素，因此在插入删除操作的时候相比底层为数组的 ArrayList 更快，
// 节点的结构
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;3.2 LinkedList 与 ArrayList
- ArrayList 基于动态数组，LinkedList 基于双向链表。
- ArrayList 支持随机访问，LinkedList 不支持。
- LinkedList 在任意位置添加删除元素更快。