一、概述

LinkedList 是一個(gè)繼承于AbstractSequentialList的雙向鏈表祥国。它也可以被當(dāng)作堆棧昵观、隊(duì)列或雙端隊(duì)列進(jìn)行操作。

LinkedList 實(shí)現(xiàn) List 接口舌稀，能對(duì)它進(jìn)行隊(duì)列操作啊犬。

LinkedList 實(shí)現(xiàn) Deque 接口，即能將LinkedList當(dāng)作雙端隊(duì)列使用壁查。

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

LinkedList 實(shí)現(xiàn)java.io.Serializable接口语御，這意味著LinkedList支持序列化峻贮，能通過(guò)序列化去傳輸。

LinkedList 是非同步的。

AbstractSequentialList

AbstractSequentialList 實(shí)現(xiàn)了“鏈表中魄藕，根據(jù)index索引值操作鏈表的全部函數(shù)”藏研。

實(shí)現(xiàn)了與index相關(guān)接口

• get(int): E
• set(int, E): E
• add(int, E): void
• remove(int, E): E
• addAll(int, Collection<? extends E>):boolean

限定只返回ListIterator

AbstractSequentialList使用Iterator實(shí)現(xiàn)了這些隨機(jī)訪問(wèn)接口，減少隨機(jī)訪問(wèn)對(duì)于具體數(shù)據(jù)結(jié)構(gòu)的依賴嚼黔。如果想要自定義隨機(jī)訪問(wèn)方式，可以繼承AbstractList惜辑。

二唬涧、數(shù)據(jù)結(jié)構(gòu)

鏈表

Node - 雙向鏈表節(jié)點(diǎn)類，一般來(lái)說(shuō)包括previous引用盛撑、next引用碎节、element

size - 節(jié)點(diǎn)個(gè)數(shù)

    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;

與之前版本修改點(diǎn)：header拆分成兩個(gè)first+last，之前只有一個(gè)header使用index判斷是否是邊界抵卫，使用first+last只需要判斷prev==null||next==null就可以了狮荔。

三、特點(diǎn)

• 順序訪問(wèn)效率高介粘、隨機(jī)訪問(wèn)效率低
• 隨機(jī)添加／隨機(jī)刪除元素效率高
• 無(wú)限容量

四殖氏、實(shí)現(xiàn)要點(diǎn)

1. 雙向鏈表的索引值實(shí)現(xiàn)

隨機(jī)訪問(wèn)

遍歷尋找，根據(jù)size選擇比較近的一端開(kāi)始遍歷姻采。復(fù)雜度為O(N/2)

LinkedList中所有隨機(jī)訪問(wèn)都是先通過(guò)node(int)得到Node雅采，然后再對(duì)Node進(jì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;
        }
    }

定位（indexOf(E)）

遍歷實(shí)現(xiàn)

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

2. 基本功能的實(shí)現(xiàn)

AbstractSequentialList已實(shí)現(xiàn)方法add()慨亲、remove()婚瓜、get() ，依然保留刑棵，使用Iterator實(shí)現(xiàn)AbstractSequentialList未實(shí)現(xiàn)方法巴刻，Node元素操作直接修改next、prev引用對(duì)象來(lái)實(shí)現(xiàn)蛉签，索引操作先找到Node元素冈涧，再進(jìn)行操作。

拋棄元素時(shí)需要設(shè)置各項(xiàng)為null正蛙，保證對(duì)象可以被gc掉

    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) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

3. Iterator／DescendingIterator實(shí)現(xiàn)

自定義了ListItr<E>繼承自ListIterator<E>

成員變量：

        private Node<E> lastReturned = null;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

使用方式：類同ArrayList

fast-fail機(jī)制：類同ArrayList

DescendingIterator：從size開(kāi)始向前調(diào)用

4. Deque雙端隊(duì)列

由于LinkedList實(shí)現(xiàn)了Deque督弓，而Deque接口定義了在雙端隊(duì)列兩端訪問(wèn)元素的方法。提供插入乒验、移除和檢查元素的方法愚隧。每種方法都存在兩種形式：一種形式在操作失敗時(shí)拋出異常，另一種形式返回一個(gè)特殊值（null 或 false，具體取決于操作）狂塘。

方法總結(jié)