Java-集合类源码List篇（一）
List作为一个集合类的接口，我们实际使用中通常是使用其实现类，常用的实现类有ArrayList、Vector、LinkedList，以及Vector的子类Stack。
1. Collection接口
List接口其实是继承自Collection接口，先来看下它的继承、实现关系：
从该图中可以看出最高接口为Iterable，该接口中只有一个方法为iterator()，查看下JDK源码，该方法返回一个Iterator类型的接口。那么为什么不直接继承Iterator接口呢？
public interface Iterable<T> { /** * 返回一个当前集合类型的迭代子 * @return */ Iterator<T> iterator(); }
可以看到Iterable接口只有一个方法且就是返回一个迭代子，我们看下 Iterator的源码：
public interface Iterator<E> { /** * 是否有下一元素 */ boolean hasNext(); /** * 下一迭代元素 */ E next(); /** * 删除当前元素 */ void remove(); }
其主要方法 hasNext() 、next ()方法，当我们集合在传递过程中，是无法预知它的当前迭代位置的，所以hasNext和next（）方法将失效，而继承Iterable接口则可以返回一个
迭代器，每次都是从头开始计数，且多个迭代器之间不干扰！
AbstractList 抽象类
我们再来看下AbstractList抽象类:
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>
此类提供 List 接口的骨干实现，从而最大限度地减少了实现由“随机访问”数据存储（如数组）支持的接口所需的工作。
对于连续的访问数据（如链表），应优先使用AbstractSequentialList，如LinkedList则继承自AbstractSequentialList而非此类。
public void add(int index, E element) { throw new UnsupportedOperationException(); } public E remove(int index) { throw new UnsupportedOperationException(); } public E set(int index, E element) { throw new UnsupportedOperationException(); }
在查看代码时，我们可以看到上述三个方法均为public类型且抛出了异常，因为它们已经不属于公用方法的范畴了！需要具体继承该抽象类的子类去覆写这三个方法。
接下来看下具体我们常用的四种List实现。
2. ArrayList
下面是它的继承、实现关系：
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
看到这，不禁有个疑惑，为什么AbstractList继承了AbstractCollection，实现了List接口，那么为什么ArrayList还要实现List<E>这个接口呢？这其实是个mistake。ArrayList实现了RandomAccess接口，说明该类支持快速随机访问；实现了Serializable接口，说明它支持序列化，能够通过序列化传输；实现了Cloneable接口，说明它支持通过clone（）方法来得到浅复制出来的List实例。学习一个类，首先要看其成员变量了解其属性有哪些？
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to * DEFAULT_CAPACITY when the first element is added. */ private transient Object[] elementData; /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;
既然是一个基于数组的集合类，那么肯定会有一个数组elementData，然后要返回一个当前集合的大小的size，再者就是集合的变化（包含增加、删除、修改）modCount，modCount是父类AbstractList的属性，从这看出集合实现类都需要对modCount进行维护，它的实际作用在下面我们会提到。
2.1 ArrayList构造函数
import java.util.Arrays; import java.util.Collection; /** * 由于一些虚拟机厂商使用了一些头信息在数组中，为避免超出最大范围 * ArrayList的最大值限定为Integer.MAX_VALUE - 8 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 指定容器默认初始化大小构造函数 */ public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); this.elementData = new Object[initialCapacity]; } /** * 无参的构造函数 */ public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; } /** * 已有集合类作为参数 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
所以我们看到ArrayList的最大值是Integer最大值-8，若以Integer最大值作为长度，运行效果如图：
2.2 ArrayList访问元素
访问元素不外乎CRUD的四种方法，我们逐各来看下ArrayList中是怎么实现的。
get（int index）
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* 返回List中指定位置的元素
*
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
可以看到其实get（index）方法访问某个指定索引的元素其实就是访问数组下标元素的过程，而数组是连续的寻址空间，访问目标元素时，通过数组下标偏移量来找到目标元素。
add（E e）
/** * Appends the specified element to the end of this list. **/ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 通过判断size+1 和table.length的大小决定是否需要扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * 对数组进行扩容 * */ 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); }
每次添加时，都会检查是否超过了其容量，如果超过了，则对其进行扩容，每次增长大约是其原容量的1.5倍（大约是因为可能指定的初始容量不是2的整数倍而newCapacity=oldCapacity/2）。
数组进行扩容时，会将其老数组的数组重新拷贝一份到新的数组中，这种操作对内存的消耗代价是很高的，因此当我们可预知范围时，应进行设置合理的初始化大小，避免进行扩容的次数，以提高效率减少内存开销。
add(int index, E element)
该方法为指定位置添加元素
public void add(int index, E element) { //校验index是否在size范围内 rangeCheckForAdd(index); //size+1和length比较 是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! //将指定位置及其后的元素往后移一位 空出index,并指定其为指定值 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
从源码可看出，ArrayList往指定位置添加元素是将原位置上的元素及其之后的元素全部后移一位，空出来的位置放置目标值，并不是覆盖原值，所以往指定位置 添加元素涉及到一次复制元素。
remove(int index)
/** * 移除方法，为了保证索引的连续 * 当移除一个元素，其后面所有的元素都要向前移动一个位置 * @parram src 源数组 * @parram srcPos 要复制源数组的起始位置 * @parram dest 目标数组 * @parram destPos 要复制到目标数组的起始位置 * @parram destPos 要复制的长度 * System.arraycopy(Object src, int srcPos,Object dest, int destPos, int length); * */ public E remove(int index) { //校验index是否超出了size大小 rangeCheck(index); modCount++; E oldValue = elementData(index); //numMoved为需要移动的元素个数 int numMoved = size - index - 1; if (numMoved > 0) //如果被移除的元素不是最后一个元素（即需要移动元素） //使用System字典的native方法进行数组的复制 System.arraycopy(elementData, index+1, elementData, index, numMoved); //将size大小位置为null elementData[--size] = null; // clear to let GC do its work return oldValue; }
有个System.arraycopy()方法，当我们数组个数较多，且需要进行复制时，可以直接利用System的静态方法arraycopy进行操作，它是一个native方法，直接操作内存，比使用for循环要快得多，但是如果是二维数组时，则不可以使用，因为二维数组其实是数组的数组。
ArrayList内部其实就是通过数组来实现的，所以它具备了数组的特点。
1.寻址空间是连续的。
2.存储类型须保持一致，注意不能保存基本数据类型，如int、long；只能是其包装类或引用类型。
至此，ArrayList的简单的操作方法我们都看完了，那么思考以下几个问题：
|
1.为什么elementData要设置成transient类型？ 2.modCount的作用是什么，为什么每次操作完后要进行自增的操作？ 3.进行删除元素的时候，为什么删除之后还是要移动元素以保证其数组中没有null的元素呢？ |
为什么elementData要设置成transient类型？
transient标注的成员变量在进行对象序列的时候会忽略，不进行序列化操作。而ArrayList将其设置成transient类型显然不是因为这个，设想一下，如果最核心的成员变量都没有进行序列化，那序列化还有什么意义呢！这是ArrayList对成员数组中的元素序列化进行了优化，当我们的size满了一般是是直接将其扩容为原先的1.5倍，可能会存在数组中的元素为null的情况，为了避免序列化null的元素而进行的优化。
看下ArrayList中有以下writeObject（）方法：
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
ArrayList覆写了writeObject和readObject方法，当覆写了该方法时，ObjectInputStream和ObjectOutputStream在进行调用的时候，会利用Java的反射机制直接调用对象上已覆写的writeObject和readObject方法。接下来看第二个问题：
modCount的作用是什么，为什么每次操作完后要进行自增的操作？
* bogus {@code ConcurrentModificationExceptions}. If an implementation * does not wish to provide fail-fast iterators, this field may be * ignored. */ protected transient int modCount = 0;
该属性是在AbstractList的属性，作用是记录ArrayList结构性变化的次数。在ArrayList中，所有涉及到结构性变化的操作，modCount值都会+1，包括add(),addAll(),Remove()等。
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赋值给迭代子中的expectedModCount public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { //先验证expectedModCount与modCount是否相等，即在迭代期间所要迭代的对象的值是否改变，若已改变，则直接抛出异常 checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
在上面的ArrayList内部的获取迭代器实现中，可以看到初始化一个迭代器时，会将modCount的值赋给expectedModCount。
我们进行迭代List时，是获取一个内部类的迭代子实例，当进行迭代操作时，我们对list进行操作是不会报检查型异常的，同时也是可以操作成功的(此时modCount值已经改变)，但这时再去通过迭代子的next或者remove方法操作list时，会去检查expectedModCount与modCount是否相等，如果不相等，则直接抛出异常，该种操作是不被允许的。
为什么删除之后还是要移动元素以保证其数组中没有null的元素呢？
if (numMoved > 0) //如果被移除的元素不是最后一个元素（即需要移动元素） //使用System字典的native方法进行数组的复制 System.arraycopy(elementData, index+1, elementData, index, numMoved); //将size大小位置为null elementData[--size] = null; // clear to let GC do its work
在remove（）方法中有以上的代码描述，它将调用System.arrayCopy（）将被删除元素之后的所有元素向前移动一个位置使整个ArrayList中size上的元素没有null元素。
初步以为是从节约存储空间角度和扩容考虑的，如果移除后都不前移，那么再次往List中添加元素时，就不能直接判断出是否需要进行扩容操作了(因为此时size的大小是准确的，但是并不能通过size+1位是否超过list.length来判断，新增元素都是直接放至size位，索引从0开始)，如果一味的进行扩容操作，那势必造成空间的浪费和额外的开销。
总结
学习完一个常用的List实现，那么我们需要记住或者说知道哪些点呢？个人觉得主要有以下几个方面：
1.ArrayList的实现机制（基于数组的存储结构以及扩容是什么时候，怎么扩容的，设置初始化大小避免扩容开销）；
2.ArrayList常用的访问、操作元素的方法使用及其里面涉及到的复制数组移动操作；
3.ArrayList的迭代子的实现机制及如何遍历ArrayList。
那么List中基于链表是怎么实现的，以及多线程访问下保证线程安全的List组件又该用哪个，我们下节再讨论。
因为水平有限，可能不足和不够严谨之处，欢迎批评雅正~~