摘要：快速失敗在用迭代器遍歷一個集合對象時，如果遍歷過程中對集合對象的內(nèi)容進行了修改增加刪除修改，則會拋出。原理由于迭代時是對原集合的拷貝進行遍歷，所以在遍歷過程中對原集合所作的修改并不能被迭代器檢測到，所以不會觸發(fā)。

原文地址

在Java.util包下

繼承自AbstractSequentialList

實現(xiàn) List 接口，能對它進行隊列操作。

實現(xiàn) Deque 接口，即能將LinkedList當作雙端隊列使用。

實現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()，能克隆。

實現(xiàn)java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。

允許包含null值

迭代器可以快速報錯

非線程安全的，如果在多線程中使用（修改），需要在外部作同步處理。

LinkedList是一種可以在任何位置進行高效地插入和移除操作的有序序列，它是基于雙向鏈表實現(xiàn)的。內(nèi)部有三個變量，size表示鏈表中元素的個數(shù)， first指向鏈表頭部，last指向鏈表尾部。 結(jié)構(gòu)圖如下圖所示

下面是LinkedList中Node節(jié)點的定義，Node類是LinkedList的靜態(tài)內(nèi)部類。

private static class Node {
    E item;          // 當前節(jié)點所存數(shù)據(jù)
    Node next;    // 當前節(jié)點的下一個節(jié)點
    Node prev;    // 當前節(jié)點的前一個節(jié)點

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList提供了兩種種方式的構(gòu)造器，構(gòu)造一個空列表、以及構(gòu)造一個包含指定collection的元素的列表，
這些元素按照該collection的迭代器返回的順序排列的。

public LinkedList() {
}

public LinkedList(Collection c) {
    this();
    addAll(c);   // 調(diào)用addAll方法，構(gòu)建一個包含指定集合c的列表
}

因為LinkedList即實現(xiàn)了List接口，又實現(xiàn)了Deque接口，所以LinkedList既可以添加將元素添加到尾部，也可以將元素添加到指定索引位置，還可以添加添加整個集合；另外既可以在頭部添加，又可以在尾部添加。

//添加元素作為第一個元素
public void addFirst(E e) {
    linkFirst(e);
}
//店家元素作為最后一個元素
public void addLast(E e) {
    linkLast(e);
}

//使用對應參數(shù)作為第一個節(jié)點，內(nèi)部使用
private void linkFirst(E e) {
    final Node f = first;//得到首節(jié)點
    final Node newNode = new Node<>(null, e, f);//創(chuàng)建一個節(jié)點
    first = newNode;        //更新首節(jié)點
    if (f == null)
        last = newNode;     //如果之前首節(jié)點為空(size==0)，那么尾節(jié)點就是首節(jié)點
    else
        f.prev = newNode;   //如果之前首節(jié)點不為空，之前的首節(jié)點的前一個節(jié)點為當前首節(jié)點
    size++;                 //長度+1
    modCount++;             //修改次數(shù)+1
}
//使用對應參數(shù)作為尾節(jié)點
void linkLast(E e) {
    final Node l = last; //得到尾節(jié)點
    final Node newNode = new Node<>(l, e, null);//使用參數(shù)創(chuàng)建一個節(jié)點
    last = newNode;         //設(shè)置尾節(jié)點
    if (l == null)
        first = newNode;    //如果之前尾節(jié)點為空(size==0)，首節(jié)點即尾節(jié)點
    else
        l.next = newNode;   //如果之前尾節(jié)點不為空，之前的尾節(jié)點的后一個就是當前的尾節(jié)點
    size++;
    modCount++;
}

//在非空節(jié)點succ之前插入元素E。
void linkBefore(E e, Node succ) {
    final Node pred = succ.prev;//獲取前一個節(jié)點
    final Node newNode = new Node<>(pred, e, succ);//使用參數(shù)創(chuàng)建新的節(jié)點
    succ.prev = newNode;//當前節(jié)點指向新的節(jié)點
    if (pred == null)
        first = newNode;//如果前一個節(jié)點為null，新的節(jié)點就是首節(jié)點
    else
        pred.next = newNode;//如果存在前節(jié)點，那么前節(jié)點的向后指向新節(jié)點
    size++;
    modCount++;
}

//添加指定集合的元素到列表，默認從最后開始添加
public boolean addAll(Collection c) {
    return addAll(size, c);//size表示最后一個位置
}

/*
從指定位置（而不是下標！下標即索引從0開始，位置可以看做從1開始，其實也是0）后面添加指定集合的元素到列表中，只要有至少一次添加就會返回true
index換成position應該會更好理解，所以也就是從索引為index(position)的元素的前面索引為index-1的后面添加！
當然位置可以為0啊，為0的時候就是從位置0(雖然它不存在)后面開始添加嘛，所以理所當然就是添加到第一個位置（位置1的前面）的前面

比如列表：0 1 2 3，如果此處index=4(實際索引為3)，就是在元素3后面添加；如果index=3(實際索引為2)，就在元素2后面添加。
*/
public boolean addAll(int index, Collection c) {
    checkPositionIndex(index);  //檢查索引是否正確（0<=index<=size）
    Object[] a = c.toArray();   //得到元素數(shù)組
    int numNew = a.length;      //得到元素個數(shù)
    if (numNew == 0)            //若沒有元素要添加，直接返回false
        return false;
    Node pred, succ;
    if (index == size) {    //如果是在末尾開始添加，當前節(jié)點后一個節(jié)點初始化為null，前一個節(jié)點為尾節(jié)點
        succ = null;        //這里可以看做node(index)，不過index=size了（index最大只能是size-1），所以這里的succ只能=null，也方便后面判斷
        pred = last;        
    } else {                //如果不是從末尾開始添加，當前位置的節(jié)點為指定位置的節(jié)點，前一個節(jié)點為要添加的節(jié)點的前一個節(jié)點
        succ = node(index); //添加好元素后(整個新加的)的后一個節(jié)點
        pred = succ.prev;   
    }
    //遍歷數(shù)組并添加到列表中
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node newNode = new Node<>(pred, e, null);//創(chuàng)建一個節(jié)點，向前指向上面得到的前節(jié)點
        if (pred == null)
            first = newNode;    //若當前節(jié)點為null，則新加的節(jié)點為首節(jié)點
        else
            pred.next = newNode;//如果存在前節(jié)點，前節(jié)點會向后指向新加的節(jié)點
        pred = newNode;         //新加的節(jié)點成為前一個節(jié)點
    }
    if (succ == null) {
        //pred.next = null  //加上這句也可以更好的理解
        last = pred;        //如果是從最后開始添加的，則最后添加的節(jié)點成為尾節(jié)點
    } else {
        pred.next = succ;   //如果不是從最后開始添加的，則最后添加的節(jié)點向后指向之前得到的后續(xù)第一個節(jié)點
        succ.prev = pred;   //當前，后續(xù)的第一個節(jié)點也應改為向前指向最后一個添加的節(jié)點
    }
    size += numNew;
    modCount++;
    return true;
}

//將指定的元素(E element)插入到列表的指定位置(index)
public void add(int index, E element) {
    checkPositionIndex(index); //index >= 0 && index <= size

    if (index == size) 
        linkLast(element); //尾插入
    else
        linkBefore(element, node(index));  //中間插入
}

linkBefore的添加步驟：

創(chuàng)建newNode節(jié)點，將newNode的后繼指針指向succ，前驅(qū)指針指向pred

將succ的前驅(qū)指針指向newNode

根據(jù)pred是否為null，進行不同操作。

如果pred為null，說明該節(jié)點插入在頭節(jié)點之前，要重置first頭節(jié)點

如果pred不為null，那么直接將pred的后繼指針指向newNode即可

addAll的添加步驟：

檢查index索引范圍

得到集合數(shù)據(jù)

得到插入位置的前驅(qū)和后繼節(jié)點

遍歷數(shù)據(jù)，將數(shù)據(jù)插入到指定位置

同樣的LinkedList也提供了很多方法來刪除元素

// 刪除首節(jié)點并返回刪除前首節(jié)點的值，內(nèi)部使用 (f == first && f != null)
private E unlinkFirst(Node f) {
    final E element = f.item;      // 獲取首節(jié)點的值 
    final Node next = f.next;   // 獲取首節(jié)點的后一個節(jié)點
    f.item = null;
    f.next = null; // help GC
    first = next;                 // 更新首節(jié)點
    if (next == null)             //如果不存在下一個節(jié)點，則首尾都為null
        last = null;
    else
        next.prev = null;        //如果存在下一個節(jié)點，那它的前指針為null
    size--;
    modCount++;
    return element;
}

// 刪除尾節(jié)點，并返回尾節(jié)點的元素 （assert l == last && l != null）
private E unlinkLast(Node l) {
    final E element = l.item;//獲取尾節(jié)點的值
    final Node prev = l.prev;//獲取尾節(jié)點前一個節(jié)點
    l.item = null;
    l.prev = null;   // help GC
    last = prev;        //前一個節(jié)點成為新的尾節(jié)點
    if (prev == null)
        first = null;   //如果前一個節(jié)點不存在，則首尾都為null
    else
        prev.next = null;//如果前一個節(jié)點存在，先后指向null
    size--;
    modCount++;
    return element;
}

// 刪除指定節(jié)點x并返回節(jié)點的值（x != null）
E unlink(Node x) {
    //獲取當前值和前后節(jié)點
    final E element = x.item;
    final Node next = x.next;
    final Node prev = x.prev;
    if (prev == null) {
        first = next;   //如果前一個節(jié)點為空(如當前節(jié)點為首節(jié)點)，后一個節(jié)點成為新的首節(jié)點
    } else {
        prev.next = next;//如果前一個節(jié)點不為空，那么他先后指向當前的下一個節(jié)點
        x.prev = null;  //help  GC
    }
    if (next == null) {
        last = prev;    //如果后一個節(jié)點為空(如當前節(jié)點為尾節(jié)點)，當前節(jié)點前一個成為新的尾節(jié)點
    } else {
        next.prev = prev;//如果后一個節(jié)點不為空，后一個節(jié)點向前指向當前的前一個節(jié)點
        x.next = null;  //help  GC
    }
    x.item = null;   //help  GC
    size--;
    modCount++;
    return element;
}

//刪除第一個元素并返回刪除的元素
public E removeFirst() {
    final Node f = first;//得到第一個節(jié)點
    if (f == null)          //如果為空，拋出異常
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
//刪除最后一個元素并返回刪除的值
public E removeLast() {
    final Node l = last;//得到最后一個節(jié)點
    if (l == null)          //如果為空，拋出異常
        throw new NoSuchElementException();
    return unlinkLast(l);
}

private static final long serialVersionUID = 876323262645176354L;

//序列化：將linkedList的“大小，所有的元素值”都寫入到輸出流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    s.defaultWriteObject();
    s.writeInt(size);

    for (Node x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

//反序列化：先將LinkedList的“大小”讀出，然后將“所有的元素值”讀出
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    int size = s.readInt();

    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());  //以尾插入的方式
}

//提供普通隊列和雙向隊列的功能，當然，也可以實現(xiàn)棧，F(xiàn)IFO，F(xiàn)ILO
//出隊（從前端），獲得第一個元素，不存在會返回null，不會刪除元素（節(jié)點）
public E peek() {
    final Node f = first;
    return (f == null) ? null : f.item;
}
//出隊（從前端），不刪除元素，若為null會拋出異常而不是返回null
public E element() {
    return getFirst();
}
//出隊（從前端），如果不存在會返回null，存在的話會返回值并移除這個元素（節(jié)點）
public E poll() {
    final Node f = first;
    return (f == null) ? null : unlinkFirst(f);
}
//出隊（從前端），如果不存在會拋出異常而不是返回null，存在的話會返回值并移除這個元素（節(jié)點）
public E remove() {
    return removeFirst();
}
//入隊（從后端），始終返回true
public boolean offer(E e) {
    return add(e);
}
//入隊（從前端），始終返回true
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
//入隊（從后端），始終返回true
public boolean offerLast(E e) {
    addLast(e);//linkLast(e)
    return true;
}
//出隊（從前端），獲得第一個元素，不存在會返回null，不會刪除元素（節(jié)點）
public E peekFirst() {
    final Node f = first;
    return (f == null) ? null : f.item;
 }
//出隊（從后端），獲得最后一個元素，不存在會返回null，不會刪除元素（節(jié)點）
public E peekLast() {
    final Node l = last;
    return (l == null) ? null : l.item;
}
//出隊（從前端），獲得第一個元素，不存在會返回null，會刪除元素（節(jié)點）
public E pollFirst() {
    final Node f = first;
    return (f == null) ? null : unlinkFirst(f);
}
//出隊（從后端），獲得最后一個元素，不存在會返回null，會刪除元素（節(jié)點）
public E pollLast() {
    final Node l = last;
    return (l == null) ? null : unlinkLast(l);
}
//入棧，從前面添加
public void push(E e) {
    addFirst(e);
}
//出棧，返回棧頂元素，從前面移除（會刪除）
public E pop() {
    return removeFirst();
}

//返回迭代器
public Iterator descendingIterator() {
    return new DescendingIterator();
}
//迭代器
private class DescendingIterator implements Iterator {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

public ListIterator listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
}

private class ListItr implements ListIterator {
    private Node lastReturned;
    private Node next;
    private int nextIndex;
    private int expectedModCount = modCount;//保存當前modCount，確保fail-fast機制

    ListItr(int index) {
        next = (index == size) ? null : node(index);//得到當前索引指向的next節(jié)點
        nextIndex = index;
    }

    public boolean hasNext() {   // 判斷后面是否還有元素
        return nextIndex < size;
    }
    
    public E next() {     //獲取下一個節(jié)點
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    //獲取前一個節(jié)點，將next節(jié)點向前移
    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    public void forEachRemaining(Consumer action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

在ListIterator的構(gòu)造器中，得到了當前位置的節(jié)點，就是變量next。next()方法返回當前節(jié)點的值并將next指向其后繼節(jié)點，previous()方法返回當前節(jié)點的前一個節(jié)點的值并將next節(jié)點指向其前驅(qū)節(jié)點。

由于Node是一個雙向節(jié)點，所以這用了一個節(jié)點就可以實現(xiàn)從前向后迭代和從后向前迭代。另外在ListIterator初始時，exceptedModCount保存了當前的modCount，如果在迭代期間，有操作改變了鏈表的底層結(jié)構(gòu)，那么再操作迭代器的方法時將會拋出ConcurrentModificationException。

fail-fast 機制是java集合(Collection)中的一種錯誤機制。當多個線程對同一個集合的內(nèi)容進行操作時，就可能會產(chǎn)生fail-fast事件。例如：當某一個線程A通過iterator去遍歷某集合的過程中，若該集合的內(nèi)容被其他線程所改變了；那么線程A訪問集合時，就會拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件。

快速失敗（fail—fast）

在用迭代器遍歷一個集合對象時，如果遍歷過程中對集合對象的內(nèi)容進行了修改（增加、刪除、修改），則會拋出Concurrent Modification Exception。

原理：迭代器在遍歷時直接訪問集合中的內(nèi)容，并且在遍歷過程中使用一個 modCount 變量。集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會改變modCount的值。每當?shù)魇褂胔ashNext()/next()遍歷下一個元素之前，都會檢測modCount變量是否為expectedmodCount值，是的話就返回遍歷；否則拋出異常，終止遍歷。

注意：這里異常的拋出條件是檢測到 modCount！=expectedmodCount 這個條件。如果集合發(fā)生變化時修改modCount值剛好又設(shè)置為了expectedmodCount值，則異常不會拋出。因此，不能依賴于這個異常是否拋出而進行并發(fā)操作的編程，這個異常只建議用于檢測并發(fā)修改的bug。

場景：java.util包下的集合類都是快速失敗的，不能在多線程下發(fā)生并發(fā)修改（迭代過程中被修改）。

安全失?。╢ail—safe）

采用安全失敗機制的集合容器，在遍歷時不是直接在集合內(nèi)容上訪問的，而是先復制原有集合內(nèi)容，在拷貝的集合上進行遍歷。

原理：由于迭代時是對原集合的拷貝進行遍歷，所以在遍歷過程中對原集合所作的修改并不能被迭代器檢測到，所以不會觸發(fā)Concurrent Modification Exception。

缺點：基于拷貝內(nèi)容的優(yōu)點是避免了Concurrent Modification Exception，但同樣地，迭代器并不能訪問到修改后的內(nèi)容，即：迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發(fā)生的修改迭代器是不知道的。

場景：java.util.concurrent包下的容器都是安全失敗，可以在多線程下并發(fā)使用，并發(fā)修改。

//獲取第一個元素
public E getFirst() {
    final Node f = first;//得到首節(jié)點
    if (f == null)          //如果為空，拋出異常
        throw new NoSuchElementException();
    return f.item;
}
//獲取最后一個元素
public E getLast() {
    final Node l = last;//得到尾節(jié)點
    if (l == null)          //如果為空，拋出異常
        throw new NoSuchElementException();
    return l.item;
}

//檢查是否包含某個元素，返回bool
public boolean contains(Object o) {
    return indexOf(o) != -1;//返回指定元素的索引位置，不存在就返回-1，然后比較返回bool值
}
//返回列表長度
public int size() {
    return size;
}

//清空表
public void clear() {     // help GC
    for (Node x = first; x != null; ) {
        Node next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}
//獲取指定索引的節(jié)點的值
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
//修改指定索引的值并返回之前的值
public E set(int index, E element) {
    checkElementIndex(index);    // 檢查下標是否合法
    Node x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

//獲取指定位置的節(jié)點
Node node(int index) {
    if (index < (size >> 1)) {//如果位置索引小于列表長度的一半(或一半減一)，從前面開始遍歷；
        Node x = first;//index==0時不會循環(huán)，直接返回first
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {                 // 否則，從后面開始遍歷
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

//獲取指定元素從first開始的索引位置，不存在就返回-1
//這里不能按條件雙向找了，所以通常根據(jù)索引獲得元素的速度比通過元素獲得索引的速度快
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}
//獲取指定元素從first開始最后出現(xiàn)的索引，不存在就返回-1
//但實際查找是從last開始的
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

//返回此 LinkedList實例的淺拷貝
public Object clone() {
    LinkedList clone = superClone();

    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    for (Node x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}

//返回一個包含LinkedList中所有元素值的數(shù)組
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

//如果給定的參數(shù)數(shù)組長度足夠，則將ArrayList中所有元素按序存放于參數(shù)數(shù)組中，并返回
//如果給定的參數(shù)數(shù)組長度小于LinkedList的長度，則返回一個新分配的、長度等于LinkedList長度的、包含LinkedList中所有元素的新數(shù)組
@SuppressWarnings("unchecked")
public  T[] toArray(T[] a) {
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
                            a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    for (Node x = first; x != null; x = x.next)
        result[i++] = x.item;

    if (a.length > size)
        a[size] = null;

    return a;
}