List是在面試中經常會問的一點，在我們面試中知道的僅僅是List是單列集合Collection下的一個實作類，
List的實作接口又有幾個，一個是ArrayList，還有一個是LinkedList，還有Vector。這次我們就來看看這三個類的源碼。
ArrayList
ArrayList是我們在開發中最常用的資料存儲容器，它的底層是通過數組來實作的。我們在集合裡面可以存儲任何類型的資料，
而且他是一個順序容器，存放的資料順序就是和我們放入的順序是一緻的，而且他還允許我們放入null元素，我們可以畫個圖了解一下。
這個圖可能不是很正确，裡面存放的元素的引用，是以我用了個000x，大緻了解一下就行，一個僞圖。
這樣的話我們來看看源碼分析
源碼分析
/**
* Default initial capacity.
* 預設初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
* 如果是數組剛初始化就會用這個空數組替代它，這是自定義容量為0的時候。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 未自定義容量 數組剛初始化就會用這個空數組替代它
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 這個elementDate就是底層使用的數組
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 實際ArrayList集合大小 也就是實際元素的個數
*/
private int size;
DEFAULT_CAPACITY 這是預設的初始容量，容量是10.
EMPTY_ELEMENTDATA 這代表的是一個空的數組，初始化數組。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 這個是差別上邊的那個自定義容量為0的時候的空數組。
有些看源碼的就會發現為什麼初始容量為10，有會出現一堆什麼空數組容量為0的呢？
這就得接下來看一下他的構造了
看這裡
構造
/**
* Constructs an empty list with an initial capacity of ten.
* 這個地方就會構造一個初始容量為10的數組
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
注釋的意思是構造一個初始容量為10的數組，但是構造函數隻是給elementDate指派了一個空數組，其實就是在我們添加元素的時候，容量自動擴充為10.
我們在看看構造具有指定初始容量的空清單。
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);
}
}
從以上的源碼我們能夠看出來，如果是使用無參構造時，是把DEFAULTCAPACITY_EMPTY_ELEMENTDATA 給了elementDate
，當initialCapacity為0的時候，就把EMPTY_ELEMENTDATA指派給了elementDate，如果initialCapacity大于0，就會初始化一個initialCapacity長度的數組給elementDate。
這上邊的就是我們如果給定初始容量的時候他會在底層幹的事情
至于使用方法，add，get這些方法就不仔細的去說了，都能看懂。我們主要來說他的疊代器
也就是inertor。
使用過ArrayList的人一般都知道，在執行for循環的時候一般情況是不會去執行remove的操作的，因為remove的操作會改變這個集合的大小，
是以會有可能出現數組角标越界異常，我們可以試一下。
看圖
下面則是他出現異常的代碼
foreach循環在我們的印象中不就是inertor麼？但是他就是會出現異常，是以我們得繼續看源碼介紹
public Iterator<E> iterator() {
return new Itr();
直接傳回的Itr這個對象，我們看一下。
}
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;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
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();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
在這個方法内部next是最主要的一個方法，他首先去判斷了expectedModCount和modCount是否一樣，然後去看cursor，是不是超過
集合的大小和數組的長度，然後去吧cursor的值給lastRet，傳回的是下标lastRet的元素，最後cursor加1，這樣就是說沒調用一次next方法，
cursor和lastRet都會加1。
當我們在調用remove方法的時候，他會去判斷lastRet是否小于0，然後去判斷expectedModCount和modCount是否一樣，然後他去調用ArrayList.remove()方法
去删除下标是lastRet的元素，然後把lastRet指派給cursor，然後初始化lastRet = -1 ，最後把modCount重新指派給expectedModCount。
這個關鍵的地方來了，remove方法對modCount進行了修改，這個時候expectedModCount和modCount是不一緻的，這時候就會出現圖中出現的那個異常了。
ConcurrentModificationException異常，而這個異常就是出自ArrayList中的内部類Itr中的checkForComodification方法。
不光是remove這個方法會出現這個，如果你使用add方法的時候也是會出現這個異常的，原理都是一樣的都是因為modCount和expectedModCount不相等導緻的原因。
ArrayList的結構看完了我們在來看看同樣是List的實作類中的LinkedList把
LinkedList
首先啊，這個LinkedList它和ArrayList這資料結構是完全不一樣的，ArrayList底層我們已經看過了是數組的結構，而LinkedList的底層則是連結清單的結構，
它可以進行高效的插入和移除的操作，他基于的是一個雙向連結清單的結構，我們畫個圖了解一下。
LinkedList的Node節點結構
就和圖中畫的一樣LinkedList是由很多個這樣的節點組成的
prev是存儲的上一個節點的引用。
element是存儲的具體的内容。
next是存儲的下一個節點的引用。
正是因為了這很多個節點，他存放着上一個和下一個節點的引用，就形成了有序的一個連結清單，就個鐵鍊類似的那種，而且再加上它存的是前後兩個節點的引用全部都儲存起來，
是以從前往後和從後往前都能增删改查資料，是以他是個雙向的連結清單。
我們再看看他的整體結構。
LinkedList的整體結構圖
我們從圖解中也能看出點東西來，他有好多的Node，并且還有first和last這兩個變量儲存頭部和尾部節點的資訊
還有就是他不是一個循環的雙向連結清單，因為他前後都是null，這個也是我們需要注意的地方
圖解看完了，我們看看他的源碼解析把。
源碼分析
1.變量
/**
* 集合元素的數量
*/
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
* 指向第一個節點的指針
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
* 指向最後一個節點的指針
*/
transient Node<E> last;
構造方法
/**
* Constructs an empty list.
* 無參構造
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* 将集合C中的所有的元素都插入到連結清單中
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
接下來我們在看看node節點
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;
}
}
看到這個Node節點，我們就能看出來在圖中的意思了，也證明了他是個雙向的連結清單、
添加元素
/**
* 将集合插入到連結清單的尾部
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
//擷取目标集合轉為數組
Object[] a = c.toArray();
//新增元素的數量
int numNew = a.length;
//如果新增元素為0，則不添加，并且傳回false
if (numNew == 0)
return false;
//定義index節點的前置節點，後置節點
Node<E> pred, succ;
//判斷是不是連結清單的尾部，如果是，那麼就在連結清單尾部追加資料
//尾部的後置節點一定是null，前置節點是隊尾
if (index == size) {
succ = null;
pred = last;
} else {
//如果不是在連結清單的末尾而是在中間位置的話，
//取出index節點，作為後繼節點
succ = node(index);
//index節點的前節點，作為前驅的節點
pred = succ.prev;
}
//連結清單批量的增加，去循環周遊原數組，依次去 插入節點的操作
for (Object o : a) {
@SuppressWarnings("unchecked")
//類型轉換
E e = (E) o;
// 前置節點為pred，後置節點為null，目前節點值為e的節點newNode
Node<E> newNode = new Node<>(pred, e, null);
// 如果前置節點為空， 則newNode為頭節點，否則為pred的next節點
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// 循環結束後，如果後置節點是null，說明此時是在隊尾追加的
if (succ == null) {
last = pred;
} else {
//否則是在隊中插入的節點 ，更新前置節點 後置節點
pred.next = succ;
succ.prev = pred;
}
// 修改數量size
size += numNew;
//修改modCount
modCount++;
return true;
}
看完這個addAll方法之後我們再看看其他的添加元素的方法，分為了頭部addFist和尾部addLast。
addFist(E e)
将e元素添加到連結清單并且設定其為頭節點Fist
看看代碼中的實作方式
public void addFirst(E e) {
linkFirst(e);
}
/**
* Links e as first element.
* 将e元素弄成連結清單的第一個元素
*/
private void linkFirst(E e) {
final Node<E> f = first;
//連結清單開頭前驅為空，值為e，後繼為f
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
//若f為空，則表明清單中還沒有元素，last也應該指向newNode
if (f == null)
last = newNode;
else
//否則，前first的前驅指向newNode
f.prev = newNode;
size++;
modCount++;
}
詳細步驟如下：
- 拿到first節點設定為f；
- 新建立一個newNode設定為next節點為f節點；
- 然後把newNode指派給這個first
- 如果f為空，則說明清單中沒有元素，last指向newNode，否則，前first的前驅指向newNode；
這是代碼的意思，我們可以通過一個圖來看一下這實作：
下面我們再看看這個addLast(E e)
就是将元素E添加到連結清單，并且設定為尾部的節點next；
public void addLast(E e) {
linkLast(e);
}
/**
* Links e as last element.
*将e元素弄成連結清單的last元素
*/
void linkLast(E e) {
final Node<E> l = last;
// 前驅為前last，值為e，後繼為null
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
//最後一個節點為空，說明清單中無元素
if (l == null)
//first同樣指向此節點
first = newNode;
else
//否則，前last的後繼指向目前節點
l.next = newNode;
size++;
modCount++;
}
其實過程都差不多，不仔細的去詳細講解了
我們再看看線程安全性問題，ArrayList和LinkedList都是線程不安全的，因為，他内部的方法都沒有進行方法同步，或者說是加鎖，
這個時候就出了一個我們不經常用的Vector，
Vector
Vector是一個可實作自動增長的數組，他也是一個線程安全的數組。
我們可以去看一下他的源碼介紹：
//它底層也是個數組 但是他的修飾符确實protected的而ArrayList是一個transient的。
protected Object[] elementData;
//它的方法都是通過synchronized關鍵字來修飾的
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
還有很多方法我就不再一一去舉例子了，而synchronized關鍵字表面的意思是
當有兩個并發線程同時通路一個對象(synchronized)代碼塊的時候，在同一個時刻，隻能有一個線程得到執行，
而另外的一個線程受到阻塞，必須等待目前線程的代碼執行完這個代碼塊之後才能執行該代碼。
也就是說在執行synchronized代碼塊的時候會鎖定目前的對象，隻有執行完改代碼塊之後才能釋放鎖，下一個線程開始鎖定對象執行。
總結
List實作類：
-
ArrayList–>數組結構–>線程不安全，效率高–>查詢快，增删慢–>容量不夠擴容，目前容量長度*1.5+1；
預設長度為10，第一次擴充後的長度為16，第二次擴充後的長度為25，第三次擴從後的長度為38.5，不取用四舍五入，為38；
但是要注意，JDk1.7是1.5+1；而JDK8是1.5，是以視情況而定
- LinkedList–>雙向連結清單結構–>線程不安全，效率高–>查詢慢，增删快–>連結清單直接在頭部尾部新增都可以，是以沒有倍數；
- Vector–>數組結構–>線程安全，效率低–>查詢快，增删慢–>擴容長度是：目前容量長度*2；