List源码研究
一、概述
ArrayList：【数组实现的】方法不同步、线程不安全、性能相对高，查找速度快,默认扩充为原来的1.5倍。
Vector：【数组实现的】方法同步（sychronized）、线程安全、性能相对低、查找速度快，可设置增长因子，一般扩充2倍。
LinkedList：【双向列表实现的】线程不安全、插入效率高。>>只在末端增删元素，用于保持数据插入的顺序。
二、ArrayList
1、继承了AbstractList，实现了RandomAccess, Cloneable, java.io.Serializable接口。
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
2、初始容量为10.
private static final int DEFAULT_CAPACITY = 10;
3、ArrayList扩容机制 ：调用ensureCapacity(int minCapacity)函数，传入扩容参数，如果扩容参数大于默认容量，就调用ensureExplicitCapacity，最终进入grow()函数进行扩容。
grow()函数接收一个minCapacity参数，新容量扩为旧容量的1.5倍。如果新容量大于 MAX_ARRAY_SIZE ，调用hugeCapacity，抛出OutOfMemoryError();否则开始执行Arrays.copyOf()函数，该方法内new了一个数组，调用了System.arraycopy()把旧的元素复制到新的数组中。
public void ensureCapacity(
int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
?
0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void grow(
int minCapacity) {
int oldCapacity = elementData.length;
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);
}
4、add方法实现：要add新元素，首先调用ensureCapacityInternal，此时的容量为原size+1，如果没有超过默认容量，就直接在数组最后插入该元素。
public boolean add(E e) {
ensureCapacityInternal(size +
1);
elementData[size++] = e;
return true;
}
5、indexOf方法实现：可以看处Array是支持null元素的，首先是判断对象是否为null，然后用for循环进行查找。查找失败的时候返回-1.
public int indexOf(Object o) {
if (o ==
null) {
for (
int i =
0; i < size; i++)
if (elementData[i]==
null)
return i;
}
else {
for (
int i =
0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -
1;
}
三、Vector
1、与ArrayList一样， 继承了AbstractList，实现了RandomAccess, Cloneable, java.io.Serializable接口。
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
2、不同点：自己实现了coptInto方法，并且加上了synchronized同步，ArrayList中是直接调用的System.arraycopy，这样就不能保证复制过程中的同步。
public synchronized void copyInto(Object[] anArray) {
System.arraycopy(elementData,
0, anArray,
0, elementCount);
}
3、扩容机制：把synchronized修饰符放在了最上面，判断是否需要扩容的函数上，而不是grow上。新容量默认是扩充为旧容量的两倍，但是如果在构造函数的时候传入了自定义的扩容参数，新容量就扩为旧容量+自定义增量的和。
public synchronized void ensureCapacity(
int minCapacity) {
if (minCapacity >
0) {
modCount++;
ensureCapacityHelper(minCapacity);
}
}
private void grow(
int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement >
0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity <
0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE >
0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
4、indexOf：同样也是支持null元素的，唯一不同的是加上了synchronized修饰。
public synchronized int indexOf(Object o,
int index) {
if (o ==
null) {
for (
int i = index ; i < elementCount ; i++)
if (elementData[i]==
null)
return i;
}
else {
for (
int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))
return i;
}
return -
1;
}
5、addAll方法：首先是被synchronized修饰，然后调用toArray()方法先将传入的集合放到一个对象数组中，然后获得数组的长度，判断是否需要扩容，然后再调用System.arraycopy()函数完成复制，最后更新当前的元素总数。
public synchronized boolean addAll(Collection<? extends E> c) {
modCount++;
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityHelper(elementCount + numNew);
System.arraycopy(a,
0, elementData, elementCount, numNew);
elementCount += numNew;
return numNew !=
0;
}
四、LinkedList
1、继承了AbstractSequentialList，实现了List,Deque, Cloneable和Serializable接口。 因此LinkedList既可以看成是List（列表），也可以看成是Deque（双端队列）。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
2、内部实现：使用链表实现，每个Node都有前继和后继。
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;
}
}
3、add方法：默认是在尾部添加元素。LinkedList中定义了一个last节点，该节点是记录当前最后一个节点last，然后把新节点赋给last，如果该节点为空，该节点就设为新的头节点first，如果不为空，就把该节点赋给l.next。
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode =
new Node<>(l, e,
null);
last = newNode;
if (l ==
null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
