LinkedList的實現原理

1. LinkedList概述：
 
List 接口的鏈接列表實現。實現所有可選的列表操作，并且允許所有元素（包括 null）。除了實現 List 接口外，LinkedList 類還為在列表的開頭及結尾 get、remove 和 insert 元素提供了統一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。
此類實現 Deque 接口，為 add、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。
所有操作都是按照雙重鏈接列表的需要執行的。在列表中編索引的操作將從開頭或結尾遍歷列表（從靠近指定索引的一端）。
注意，此實現不是同步的。如果多個線程同時訪問一個鏈接列表，而其中至少一個線程從結構上修改了該列表，則它必須 保持外部同步。（結構修改指添加或刪除一個或多個元素的任何操作；僅設置元素的值不是結構修改。）這一般通過對自然封裝該列表的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedList 方法來“包裝”該列表。最好在創建時完成這一操作，以防止對列表進行意外的不同步訪問，如下所示：
                    List list = Collections.synchronizedList(new LinkedList(...));
此類的 iterator 和 listIterator 方法返回的迭代器是快速失敗 的：在迭代器創建之后，如果從結構上對列表進行修改，除非通過迭代器自身的 remove 或 add 方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對并發的修改，迭代器很快就會完全失敗，而不冒將來不確定的時間任意發生不確定行為的風險。

注意，迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發修改時，不可能作出任何硬性保證。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。

2. LinkedList的實現：

private transient Entry<E> header = new Entry<E>(null, null, null); 

 這個成員變量是LinkedList的關鍵，它在鏈表中沒有實際數據意義，是鏈表的標示（通俗一點就是鏈表的第一個無意義的元素），而且被修飾為transient，標示著他不會被序列化。header也可以當做隊列末尾的元素，因為是雙向列表，所以header.next末尾元素后邊的元素就成了隊首元素，header.previous就是隊尾元素了，看一下它的添加方法

public void addFirst(E paramE) {
    addBefore(paramE, this.header.next);//隊首
}
public void addLast(E paramE) {
    addBefore(paramE, this.header);//隊尾
}

 以上兩個方法都利用addBefore方法將元素添加到指定對象之前，
 
 addFirst向隊頭加元素，將元素paramE添加到header.next-隊首元素之前；
 addLast向隊尾加元素，將元素paramE添加到header之前；
 
         再看一下addBefore(E e,Entry<E> entry)函數

/***
 * 要添加的元素：paramE
 * 目標對象：paramEntry
 */
private Entry<E> addBefore(E paramE, Entry<E> paramEntry)
{
    //要添加的對象
    Entry localEntry = new Entry(paramE, paramEntry, paramEntry.previous);
    /***
     * localEntry.previous = paramEntry.previous
     * 目標對象的前一元素的后一元素（localEntry.previous.next）設置為要添加的對象
     */
    localEntry.previous.next = localEntry;
    /***
     * localEntry.next = paramEntry
     * 目標對象的前一元素（localEntry.next.previous）設置為要添加的對象
     */
    localEntry.next.previous = localEntry;
    this.size += 1;
    this.modCount += 1;
    return localEntry;
}

鏈表的基本特性是插入速度快，遍歷速度慢，下面兩個方法可以反映這個特點

public int indexOf(Object paramObject) {
    int i = 0;
    Entry localEntry;
    /***
     * 遍歷規則：從頭到尾，序列呈升序狀態
     */
    if (paramObject == null)
        for (localEntry = this.header.next; localEntry != this.header; localEntry = localEntry.next) {
            if (localEntry.element == null)
                return i;
            i++;
        }
    else {
        for (localEntry = this.header.next; localEntry != this.header; localEntry = localEntry.next) {
            if (paramObject.equals(localEntry.element))
                return i;
            i++;
        }
    }
    return -1;
}
public int lastIndexOf(Object paramObject) {
    int i = this.size;
    Entry localEntry;
    /***
     * 遍歷規則：從尾到頭，序列呈降序狀態
     */
    if (paramObject == null) {
        for (localEntry = this.header.previous; localEntry != this.header; localEntry = localEntry.previous) {
            i--;
            if (localEntry.element == null)
                return i;
            }
    }else {
        for (localEntry = this.header.previous; localEntry != this.header; localEntry = localEntry.previous) {
            i--;
            if (paramObject.equals(localEntry.element))
                return i;
        }
    }
    return -1;
}

值得注意的是，鏈表插入數據速度快的說法是相對的，在數據量很小的時候，ArrayList的插入速度不僅不比LinkedList慢，而且還快很多（本文不作介紹，讀者可自行測試），只有當數據量達到一定量，這個特性才會體現出來，這需要開發者明確需求場景
LinkedList的方法entry(int index)類似ArrayList的get(int index)

/***
 * 根據序號獲取Entry對象
 */
private Entry<E> entry(int paramInt) {
    if ((paramInt < 0) || (paramInt >= this.size)) {
        throw new IndexOutOfBoundsException("Index: " + paramInt + ", Size: " + this.size);
    }
    Entry localEntry = this.header;
    int i;
    /***
     * 二分法：目標序號小于Size的1/2，則從頭到尾
     *             如果大于Size的1/2，則從尾到頭
     */
    if (paramInt < this.size >> 1) {
        for (i = 0; i <= paramInt; i++)
            localEntry = localEntry.next;
    } else {
        for (i = this.size; i > paramInt; i--)
            localEntry = localEntry.previous;
    }
    return localEntry;
}

LinkedList還提供了降序迭代器，如下

public Iterator<E> descendingIterator()    {
        return new DescendingIterator(null);
    }

關于降序迭代的具體實現可以看看源碼，很簡單
LinkedList是針對鏈表操作的一個比較全的實現，對于頻繁的數據插入有較高效率，研究其具體實現可更有利于準確的使用它。該類的toArray、clone以及其他一些方法很值得參考。
 
3. LinkedList.Entry
LinkedList的內部類Entry是實現Deque接口的基本操作單元，其結構如下：

private static class Entry<E>
{
    E element;
    Entry<E> next;
    Entry<E> previous;
    /***
     * 構造方法：目標對象paramE將被放置在paramEntry1之前，paramEntry2之后
     */
    Entry(E paramE, Entry<E> paramEntry1, Entry<E> paramEntry2)
    {
        this.element = paramE;
        this.next = paramEntry1;
        this.previous = paramEntry2;
    }
}

4. 內部迭代器：ListItr
 
雖然上層父類AbstractList<E>已經實現了迭代器，但LinkedList的直接父類AbstractSequentialList<E>給子類重新定義個一個需要實現的迭代器的抽象方法，代碼如下：

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
    /***
     * 返回子類實現的迭代器
     */
    public Iterator<E> iterator() {
        return listIterator();
    }
    public abstract ListIterator<E> listIterator(int paramInt);
}

此處實現的迭代器內部機制跟AbstractList基本一致，可以看看源碼
此類的迭代器的實現機制可以通過ListItr的remove方法來分析，同時也可分析Java對雙端隊列的處理辦法

/***
 * 當前指針位置：this.next
 * 當前所操作的對象：this.lastReturned
 */
public void remove() {
    checkForComodification();
    LinkedList.Entry localEntry = this.lastReturned.next;
    try {
        LinkedList.this.remove(this.lastReturned);
    } catch (NoSuchElementException localNoSuchElementException) {
        throw new IllegalStateException();
    }
    /***
     * 當鏈表的size為0，指針會指向this.header，其他方法（如set方法）將以此判斷當前操作對象的狀態
     */
    if (this.next == this.lastReturned)
        this.next = localEntry;
    else
        this.nextIndex -= 1;
    /***
     * 調用LinkedList.this.remove(E)之后
     * 當前操作對象this.lastReturned指向的對象被設置為this.header（原對象為null）
     * 指針移動到this.lastReturned.next
     */
    this.lastReturned = LinkedList.this.header;
    //修改次數加1
    this.expectedModCount += 1;
}