List的继承结构：
image
如图可知List，有三个子实现类：ArrayList，Vector，LinkedList。下面我们会依次对源码进行分析
ArrayList源码分析
ArrayList一个动态数组,其本质也是用数组实现的，它具有：随机访问速度快，插入和移除性能较差(数组的特点)；【支持null元素】；【有序】；元素【可重复】；【线程不安全】；
ArrayList实现了List接口以及list相关的所有方法，它允许所有元素的插入，包括null。另外，ArrayList和Vector除了线程不同步之外，大致相等。
继承实现
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList继承AbstractList并实现了List接口，RandomAccess接口（http://www.jianshu.com/p/89aaaee1077e）
Cloneable接口，Serializable接口，因此它支持快速访问，可复制，可序列化。
属性
/**
* 初始容量大小为10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 常量EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是为了初始化elementData的。
如果为无参构造函数，使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA；
如果为含参构造函数，使用EMPTY_ELEMENTDATA：
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*元素存放的地方，由此可看出ArrayList内部是用数组实现的
*/
transient Object[] elementData; //非私有便于内部类访问
/**
int类型的size表示数组中元素的个数
*/
private int size;
ArrayList底层是使用一个Object类型的数组来存放数据的，size变量代表List实际存放元素的数量
使用transient修饰，使用writeObject 和 readObject 方法是为了序列化、反序列化时节省空间和时间（http://blog.csdn.net/zero__007/article/details/52166306）
（http://www.importnew.com/12611.html）
为了对应不同的构造函数，ArrayList使用了不同的数组
代码中有个常量，表示数组的默认容量，大小为10
构造函数
/**
* 用指定的初始化容量构造一个空的List
*
* @param initialCapacity 初始容量
* @throws IllegalArgumentException 如果初始容量为负数抛出异常
*
*/
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的数组
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
常量EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是为了初始化elementData的。如果为无参构造函数，使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA；如果为含参构造函数，使用EMPTY_ELEMENTDATA，使用上述构造函数，elementData中没有元素，size为0，不过elementData的长度有可能不同。
ArrayList还提供了使用集合构造的构造函数：
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
函数首先将集合c转化为数组，然后检查转化的类型，如果不是Object[]类型，使用Arrays类中的copyOf方法进行复制；同时，如果c中没有元素，使用EMPTY_ELEMENTDATA初始化。
增删改查操作
get和set方法，都是通过数组下标，直接操作数据的，时间复杂度为O(1)
查询
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
// 遍历所有元素找到相同的元素，返回元素的下标，
// 如果是元素为null，则直接比较地址，否则使用equals的方法比较
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;
}
增加
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 扩容检测
elementData[size++] = e;//新增元素添加到末尾
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);//添加容量检测
ensureCapacityInternal(size + 1); // 扩容检测
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 使用System.arraycopy的方法，将index后面元素往后移动1位
elementData[index] = element;// 存放元素到index位置
size++;
}
//添加一个集合的元素到末端，若要添加的集合为空返回false
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
//从指定位置添加一个集合的元素，若要添加的集合为空返回false
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
//添加方式为：先将指定位置后的元素后移，再复制参数集合的元素到指定位置后
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;
}
删除
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; //方便JVM进行GC操作，避免出现泄露
return oldValue;
}
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;
}
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; // clear to let GC do its work
}
removeRange
//删除指定范围内元素
protected void removeRange(int fromIndex, int toIndex) {
//数组改变，modCount++
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex - fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
removeAll 和 retainAll
//删除指定集合的元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c); //检查集合是否为空
return batchRemove(c, false); //调用batchRemove，complement为false
}
//与removeAll相反，仅保留指定集合的元素
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c); //检查集合是否为空
return batchRemove(c, true); //调用batchRemove，complement为true
}
//complement true时从数组保留指定集合中元素的值，为false时从数组删除指定集合中元素的值。
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0; //w为数组更新后的大小
boolean modified = false;
try {
//遍历数组，并检查元素是否在指定集合中，根据complement的值保留特定值到数组
//若complement为true即保留，则将相同元素移动到数组前端
//若complement为false即删除，则将不同元素移动到数组前端
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
//如果r!=size则说明c.contains(elementData[r])抛出异常
if (r != size) {
//将数组未遍历的部分添加
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//如果w!=size说明进行了删除操作，故需将删除的值赋为null
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w; //更新数组容量
modified = true;
}
}
return modified;
}
clear
//清空数组，全部赋值为null，方便垃圾回收
public void clear() {
//数组改变，modCount++
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
其他重要方法
扩容
在添加一个元素之前，先调用一下ensureCapacityInternal方法，这个方法如下
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
它首先判断Array的底层数组elementData与默认的空数组是不是相同，如果相同，就需要取默认容量（java8中默认是10）与你传进来参数的最大值，这个判断的目的是为了List中的addAll()方法，它会增加一个collection到这个数组里来，这个collection容量大于10，那么就要拓展这个数组的大小。就是通过ensureExplicitCapacity来实现。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount是父类AbstractList里的一个成员变量，用来记录List的修改次数的，这里不再讨论。 下面if判断就是指如果添加完元素后的容量大于当前数组长度，就要对数组扩容。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
oldCapacity>>1 指向右移一位，实际为oldCapacity/2 取整，这样直接位运算速度较快，这跟jdk之前的版本不一样，以前是容量*1.5倍然后加1，新的jdk减少了步骤。
最后一句就是扩容的最终实现
Arrays.copyOf Jdk8也与以前的版本不同，之前直接使用System.arraycopy()实现这一功能，最新版将这一步又重新封装了一层，这儿不再详贴，有意的可以自己翻看一下。
//检查参数是否溢出
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // // 溢出
throw new OutOfMemoryError();
//如果参数比默认的最大值大，则取最大整数值，否则取容量默认最大值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
保存和读取
//保存数组实例的状态到一个流（即它序列化）。写入过程数组被更改（利用modCount的值）会抛出异常
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount; //写入前modCount的值，将依据此检查写入过程数组是否被更改
s.defaultWriteObject();
// 写入容量大小
s.writeInt(size);
// 按顺序写入数组元素
for (int i = 0; i < size; i++) {
s.writeObject(elementData[i]);
}
// 若写入前后modCount值不同，说明写入过程数组被更改，则抛出异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
//读操作，跟上述写操作类似
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i = 0; i < size; i++) {
a[i] = s.readObject();
}
}
}
总结
fail-fast机制的实现
fail-fast机制也叫作”快速失败”机制，是Java集合中的一种错误检测机制。
在对集合进行迭代过程中，除了迭代器可以对集合进行数据结构上进行修改，其他的对集合的数据结构进行修改，都会抛出ConcurrentModificationException错误。
这里，所谓的进行数据结构上进行修改,是指对存储的对象，进行add,set,remove操作，进而对数据发生改变。
ArrayList中，有个modCount的变量，每次进行add，set，remove等操作，都会执行modCount++。
在获取ArrayList的迭代器时，会将ArrayList中的modCount保存在迭代中，
每次执行add,set,remove等操作，都会执行一次检查，调用checkForComodification方法，对modCount进行比较。
如果迭代器中的modCount和List中的modCount不同，则抛出ConcurrentModificationException
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
使用场景
ArrayList的使用场景主要从其优缺点来考虑的：
优点：
get，set，时间复杂度为O(1)
add（一般都是在末尾插入），时间复杂度为O(1)，最差情况下（往头部插入数据），时间复杂度O(n)
数据存储是顺序的
缺点：
remove，时间复杂度为O(n)，最优情况下（移除末尾元素），时间复杂度为O(1)
ArrayList底层使用数组存储数据，数组是不能自动扩容的，因此在发生扩容的情况下，需要移动大量的元素。
ArrayList大小很大的时候，会存在空间浪费（可以通过trimToSize方法，清除空闲空间）
数组大小是由限制的，受jvm和机器的影响，当扩容超出上限时，ArrayList会抛出异常
插入操作多，数据量不大，顺序存储时，可以考虑使用ArrayList
多线程情况下：
ArrayList所有的操作，都不是同步的，因此ArrayList不是线程安全的。
如果考虑到线程安全的话，可以使用CopyOnWriteArrayList或者外部同步ArrayList（List list = Collections.synchronizedList(new ArrayList(…));）
思考
1.remove方法中，为什么会将数组对应的元素置为null？
ArrayList内部使用数组实现一套管理对象的机制，remove操作中，已经将元素的数量-1了，ArrayList认为该对象已经被移除了，应该被jvm回收。
但是，对于jvm来说，该值仍然保存在数组中，ArrayList持有这个对象的引用，在jvm发生GC时，这个对象是不对被jvm回收，这样就会造成内存泄露了。
2.查找元素的方法中（比如indexOf），为什么需要对元素进行null值判断？
判断对象是否相等，有两个方面，1.对象存储的地址；2.对象的内容。
==，是用来比较两个对象的地址是否相等，一般来说，两个对象的地址相同，那么这两个对象可以认为是相同的对象
equals方法，是用来比较对象内容的，当然，也可以重载该方法，直接比较对象地址；Object对象的equals方法，是比较地址的。
一般来说，重载equals方法的同时，也要重载hashCode方法的，重载hashCode方法，必须得遵守6个原则：
自反性：对于任何非null的引用值x，x.equals(x),必须返回true
传递性：对于任何非null的引用值x,y,z，如果x.equals(y) 为true，且y.equals(z)为true，那么x.equals(z)必须为true
对称性：对于任何非null的引用值x,y，如果x.equals(y)为true，那么y.equals(x)必须为true
非空性：对于任何非null的引用值x,x.equals(null)必须为false
一致性：对于任何非null的引用值x，y，如果多次调用equals方法，如果x和y比较的值没有改变，那么x.equals(y)就会一致性返回true或者false
为什么重载equals方法，一般要重载hashCode方法？
重载equals方法，可以不重载hashCode方法，但是一般情况，不建议这么做。
hashCode方法，使用来求出对象的Hash值，
重载hashCode方法主要是为了提高一些容器（比如HashMap，Hashtable）进行hash运算的效率，而且也可以避免出现一些错误（比如HashSet容器的操作）
对于元素进行null值判断，我认为主要是为了效率考虑，如果是null值的话，可以直接比较地址，而非空值，则需要通过equals方法来比较，由于ArrayList是泛型的，
所以其添加的元素，可能重载equals方法，自定义了判断的原则。
3.grow方法中，对新容量大小进行判断，为什么会定义MAX_ARRAY_SIZE的？
ArrayList底层存储是使用数组来实现的，所以ArrayList存储文件的大小必定受数组大小的限制，所以在扩容中，可以看到ArrayList对新容量大小进行逻辑判断。
影响数组最大值：
理论上最大值为Integer.MAX_VALUE(2^32 - 1)
对象头限制，不同类型的元素，可创建数组的最大值是不同的，byte是1字节，int是4字节
比如jvm可用内存为1M，32位机器下，
int[] bytes = new int[1024 * 1024 / 4];
byte[] bytes = new byte[1024 * 1024];
jvm可用内存大小限制
比如jvm可用内存为1M，32位机器下，
byte[] bytes = byte[1024 * 1024]
至于为什么MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
某些机器上需要存储Headerwords
避免一些机器内存溢出，减少出错几率，所以少分配
最大还是能支持到 Integer.MAX_VALUE
