1 序

api文檔給出的解釋還是可以仔細讀，從中可以得到綜述信息。

• 雙端隊列
• 實現(xiàn)了list接口的所有操作
• 允許添加null
• JDK版本為1.8

與ArrayList一樣，linkedList本身也不是線程安全的。api解釋到了，如果在多線程環(huán)境下使用list并且沒有添加必要的同步代碼，那么更推薦使用Collections.synchronizedList。

LinkedList對象獲取的遍歷器滿足fail-fast策略，多線程環(huán)境下的使用就要注意了。但是請不要依賴于fail-fast策略來在多線程環(huán)境下使用這個容器。這并不能保證避免一些少見、晦澀的異常。到時候就很難排查了。

基于鏈表的數(shù)據(jù)結(jié)構(gòu)，add和remove操作linkedList的表現(xiàn)比ArrayList好，其add(E)與remove()操作的時間復(fù)雜度是O(1),get(int)與remove()為O(n)。ArrayList基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)與更適合隨機訪問的場景。

2 代碼

2.1 類的繼承結(jié)構(gòu)

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

除了期望中的list、cloneable和序列化之外，還有一個deque隊列接口和AbstractSequentialList。

實現(xiàn)了隊列接口意味著linkedList實現(xiàn)了隊列數(shù)據(jù)結(jié)構(gòu)的一系列方法，比如pop/peek/push等等。

另一個AbstractSequentialList是一個之前從沒有去注意過的另一個抽象類。一個list接口的最小化實現(xiàn)。其通過迭代器實現(xiàn)了與隨機訪問不同的get/set/add等一系列方法。這一系列方法可以被linkedList復(fù)用到。

API中的介紹說明LinkedList的一部分特質(zhì)是和ArrayList類似的(這些特質(zhì)也是List接口本身決定的)

• 允許插入null
• 允許重復(fù)元素

2.2 鏈表基礎(chǔ)操作

和在以前數(shù)據(jù)結(jié)構(gòu)的教材上看到的類似，類中包含了一個頭結(jié)點和一個尾節(jié)點。

/**
 * 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;

/* LinkedList的內(nèi)部類，類結(jié)構(gòu)本身比較簡單，一個前驅(qū)節(jié)點一個后繼節(jié)點和一個用來容納節(jié)點內(nèi)容的泛型對象*/
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;
}
}

鏈表的插入操作和刪除操作都是修改對應(yīng)前驅(qū)和后繼節(jié)點的指向。這個Node對象是LinkedList的一個內(nèi)部類，包含一個前驅(qū)引用和一個后繼引用，這樣的數(shù)據(jù)結(jié)構(gòu)可以幫助實現(xiàn)雙端隊列。

TailInterpolation.jpg

2.2.1 構(gòu)造函數(shù)

總計有兩個構(gòu)造函數(shù)，一個無參構(gòu)造和一個接納已有集合中元素的構(gòu)造函數(shù)。

/**
 * 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.
 *
 * @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);
}

無參構(gòu)造沒有做任何多余的操作。另一個構(gòu)造函數(shù)則會執(zhí)行addAll方法。這個方法是可以直接調(diào)用的，向鏈表的指定位置插入集合列表。

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    // 集合對象轉(zhuǎn)換為Object對象數(shù)組
    Object[] a = c.toArray();
    int numNew = a.length;
    // 判斷數(shù)組長度,驗證有效性
    if (numNew == 0)
        return false;
    // 用于保存原有鏈表指定位置前后的兩個Node節(jié)點
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    // for循環(huán)遍歷對象數(shù)組，注釋中說明了toArray方法生成的數(shù)組排列順序取決于collection對象遍歷器的實現(xiàn)邏輯
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    // 將新生成的鏈表段與之前保存的前驅(qū)后綴節(jié)點鏈接起來
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    // 更新鏈表size字段，該字段表明鏈表長度
    size += numNew;
    // modCount字段累加
    modCount++;
    return true;
}

2.2.2 增刪改查

boolean add(E e)

向鏈表添加元素，是在其表尾新增一個節(jié)點(尾插法)。如果加入的元素是鏈表中的第一個元素，那么首節(jié)點和尾節(jié)點會同時指向這個節(jié)點元素。

public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    // 新的元素,賦值給當前鏈表的尾節(jié)點
    last = newNode;
    // 如果之前的尾節(jié)點為空即當前add方法加入的是這個鏈表中唯一的一個元素，那么頭結(jié)點的指向也會指向新加入的節(jié)點newNode
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 更新鏈表的長度size字段
    size++;
    // 累加modCount統(tǒng)計字段
    modCount++;
}

示例為向鏈表尾加入一個新元素的方法linkLast

注意Node節(jié)點是LinkedList里的一個內(nèi)部類。結(jié)構(gòu)簡潔，包含一個prev,一個next和一個泛型化的元素容器類成員item。

同時add操作也對modCount計數(shù)做了累加操作。

public boolean addAll(Collection<? extends E> c)

這個方法的內(nèi)部調(diào)用非常簡潔，直接復(fù)用前面已經(jīng)分析過的方法==addAll(int index, Collection<? extends E> c)==。位置參數(shù)直接指定為當前鏈表的表尾。注意這兩個方法都是由public修飾，所以都可以直接使用。

boolean remove(Object o)

刪除指定元素，那么需要先遍歷鏈表檢查是否確實包含了這個目標元素。然后修改該位置元素的指向，包括檢查對應(yīng)的prev和next指向。

// 注意區(qū)分刪除的是節(jié)點內(nèi)容為null的節(jié)點，不是刪除null節(jié)點。這個方法的刪除遍歷順序是從頭節(jié)點開始遍歷，找到并刪除第一個匹配的元素。
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

鏈表的刪除操作-解除這個節(jié)點在鏈表中的前驅(qū)、后繼的關(guān)聯(lián)關(guān)系。

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {
        // 如果前驅(qū)節(jié)點為null即當前要刪除的節(jié)點就是鏈表的頭結(jié)點，則將被刪除節(jié)點的后繼節(jié)點賦給頭結(jié)點
        first = next;
    } else {
        // 如果前驅(qū)節(jié)點不為null則將要刪除節(jié)點的后繼指向刪除節(jié)點的前驅(qū)節(jié)點的后繼。然后釋放被刪除節(jié)點的前驅(qū)引用
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        // 如果后繼節(jié)點為null即當前要刪除的節(jié)點就是鏈表的尾結(jié)點，則將被刪除節(jié)點的后繼節(jié)點賦給尾結(jié)點
        last = prev;
    } else {
        // 如果后繼節(jié)點不為null則將要刪除節(jié)點的前驅(qū)指向刪除節(jié)點的前驅(qū)節(jié)點的前驅(qū)。然后釋放被刪除節(jié)點的后繼引用。
        next.prev = prev;
        x.next = null;
    }
    // 將被刪除元素的內(nèi)容item釋放
    x.item = null;
    // 更新鏈表長度的size字段
    size--;
    // modCount統(tǒng)計字段累加
    modCount++;
    // 返回這個被刪除的節(jié)點的內(nèi)含元素內(nèi)容
    return element;
}

要想在鏈表中訪問到指定位置的元素，需要從頭節(jié)點開始遍歷直到指定下標的位置。這里就和隨機訪問存在區(qū)別和性能差異了。如果鏈表size很大，那么訪問一個元素的操作就會耗時較多。

鏈表的刪除操作都是將指定位置的元素的頭結(jié)點指向這個元素的next節(jié)點。注意為了方便GC回收釋放空間，修改了引用指向后，被刪除元素的prev與next指向都一并置空，包括置空元素的item指向。

E remove(int index)

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

除了刪除指定元素，還有一個刪除指定位置的元素方法。這個方法需要首先檢查是否有數(shù)組越界的潛在危險。找到指定位置上的元素然后執(zhí)行unlink方法來解除已經(jīng)存在的引用關(guān)系。

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

這個方法在增刪查的操作中會被經(jīng)常用到。獲取指定下標位置的非空節(jié)點對象。

E get(int index)

/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

和上一個方法一樣，獲取指定位置的元素內(nèi)容，首先檢查數(shù)組下標是否是在正確的范圍內(nèi)，然后用node(index)遍歷獲取到目標位置的元素item內(nèi)容。注意區(qū)分linkedList與ArrayList的獲取指定下標元素方法的實現(xiàn)，這里可以區(qū)別隨機訪問與順序訪問。

E set(int index, E element)

public E set(int index, E element) {
    // 檢查下標參數(shù)合法性
    checkElementIndex(index);
    // 獲取index下標的Node節(jié)點
    Node<E> x = node(index);
    // 獲取節(jié)點原有元素
    E oldVal = x.item;
    // 將新的元素值賦給這個節(jié)點
    x.item = element;
    // 返回被替換的節(jié)點的值 oldValue
    return oldVal;
}

設(shè)置指定位置的元素。

跟指定元素位置有關(guān)的操作都需要先檢查入?yún)⑾聵耸欠袷强捎玫摹Ｏ聵藱z查不通過的都會拋出數(shù)組越界異常IndexOutOfBoundsException。然后node(index)方法獲取指定下標位置的元素，修改該元素的item引用并返回被替換掉的原有的item值。set方法操作成功會返回原有的舊的值。

void add(int index, E element)

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

向指定位置插入元素

• 檢查入?yún)⑾聵?/li>
• 如果下標是當前l(fā)ist的尾巴上，直接addLast，與add方法的實現(xiàn)一致(尾插法)
• 如果是在list中嵌入一個元素。那個要對應(yīng)修改前后節(jié)點元素的prev與next的指向。

順序表(如ArrayList)插入一個元素后，就要將其后的元素一一進行后移。但是鏈表只需要修改共計三個節(jié)點的前后指向關(guān)系。所以這里的操作成本比較，鏈表是更好的。所以這里就可以看到鏈表的插入和刪除操作的優(yōu)越性。

2.3 隊列系列操作

因為Node的實現(xiàn)里面包含了前節(jié)點的引用后后續(xù)節(jié)點的引用，再加上實現(xiàn)了Deque接口，因此LinkedList是一個雙端隊列的實現(xiàn)。其中的一系列操作方法(在隊列首、尾的插入與刪除操作)都是基于前面我們提到的增刪查改的操作完成的。

peek()

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

返回隊首元素，不過這個方法不會刪除原有隊首元素。

element()

public E element() {
    return getFirst();
}

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

返回隊首元素，與前一個方法不同的地方在于，如果當前l(fā)ist列表是一個空列表的話，會拋出異常

與上面這一組方法類似的還有一組方法，這里放在一起比較。

E poll()

E remove()

這兩個方法都是刪除隊首元素，poll在遇到隊列為空的情況下返回null而remove會拋出異常。

boolean offer(E e)

向隊尾加入元素

2.4 雙端隊列系列操作

包含一系列的雙端隊列隊首隊尾插入、獲取雙端隊列隊首隊尾元素、隊首隊尾刪除等等。這一些列方法都是LinkedList類實現(xiàn)的Deque接口所要求的方法。

2.5 值得注意的地方

LinkedList實現(xiàn)了cloneable接口，但是其實現(xiàn)的克隆操作是一個淺拷貝。注意ArrayList也僅僅是實現(xiàn)了一個淺拷貝方法。

boolean removeFirstOccurrence(Object o)

刪除list列表中遇到的第一個符合要求的object元素的對象。其實這個方法就是很直接的包裝了remove(Object)方法。

boolean removeLastOccurrence(Object o)

刪除list列表中遇到的最后一個符合要求的object元素的對象。這個方法是前一個方法的另一端。反過來從隊列的尾端開始尋找。

3 總結(jié)

LinkedList的使用，主要可以與ArrayList作對比，二者有各自的適用場景和特點。用一句很簡潔的話說：ArrayList適合快速隨機訪問操作而其插入刪除的操作效率不如LinkedList。當然這幾句話幾乎是背下來的，至于為什么是這個結(jié)論，需要結(jié)合類的數(shù)據(jù)結(jié)構(gòu)和思想來總結(jié)。

可以簡要對比一下幾種主要操作二者的時間復(fù)雜度：

• add(E e) ArrayList是O(n),LinkedList是O(1)
• remove(int n) ArrayList是O(n),LinkedList是O(1)
• get(int n) ArrayList是O(1),LinkedList是O(n)