本篇文章是【Java集合系列】文章的第二篇敷搪，本系列將會逐個分析 Java 中的常用集合的特性及實現(xiàn)啡捶，然后對比不同場景下應該選擇哪種集合使用口蝠。

List 系列

• Java 中的 ArrayList
• Java 中的 LinkedList
• Java 中的 CopyOnWriteArrayList

LinkedList

實現(xiàn)了 List 以及 Deque 的雙向鏈表柿究，元素允許為 null诉字，所以 LinkedList 同時具備 List 以及 Deque 的特性多糠。
跟 ArrayList 一樣谨履，LinkedList 也是非線程安全的，可以使用包裝方法獲取同步對象：

List list = Collections.synchronizedList(new LinkedList(...));

iterator以及listIterator同樣也被設計為 fail-fast熬丧。

使用特性

LinkedList 內部實現(xiàn)上是個鏈表笋粟，所以可以把它當作鏈表使用。

LinkedList 同樣還可以代替 Stack 類當做棧來使用（官方也推薦這么做）析蝴。

但不合適作為 List 使用害捕，List 相關的方法會比較耗時，性能低闷畸。

鏈表和棧相關的操作基本都可以在固定時間內完成尝盼，但是 List 特性的操作，也就是通過索引訪問元素的方法get需要 O(n) 的時間佑菩，不推薦使用盾沫。

公開方法

因為雙端隊列也是基于隊列的，所以 LinkedList 中的方法大體可以分為三種：

• 列表方法
• 隊列方法
• 雙端隊列方法

下面分別看下殿漠。

列表方法

列表方法比較簡單赴精，這里就不贅述了，可以看 ArrayList 那一節(jié)文章绞幌。

隊列

隊列是一種先進先出（FIFO）的數(shù)據(jù)結構蕾哟，Java 中的接口 Queue 描述了隊列這種數(shù)據(jù)結構。

我們可以將上表按照功能分為三類：插入帘营、移除、檢索逐哈。
每種操作又提供了兩種方法：拋出異撤移或返回特殊值。

上面就是隊列中提供的方法了昂秃，Java 大概是考慮到使用方便問題禀梳，所以給每種方法都提供了拋出異常或者返回特殊值的方式械蹋，也導致方法數(shù)量多了一倍，而對于雙端隊列來說羞芍，上述的每種方法又會多出兩個哗戈，看起來很多，但我們只要知道本質上就是上述的三種操作就行荷科，其他的都是變種而已唯咬。

雙端隊列

作為雙端隊列，比隊列多出的特性將通過給隊列中的每個操作方法提供兩個變種方法來實現(xiàn)畏浆，比如隊列中的 add 方法胆胰，雙端隊列中將提供addFirst和addLast方法，用于將元素添加到頭或者尾刻获。

由于雙端隊列的特性導致還可以很輕易的實現(xiàn)棧的功能蜀涨，可以用來替換 Stack 類來使用，所以 Deque 中又提供了兩個用于實現(xiàn)棧結構的方法蝎毡。

Deque 還提供了從后向前遍歷的descendingIterator的迭代器厚柳，元素將從最后一個開始遍歷到第一個元素。

總結

下面來總結一下沐兵。
LinkedList 作為隊列（FIFO）使用時的方法：

LinkedList 作為堆棧（FILO）使用時的方法：

源碼

我們先看看鏈表的節(jié)點是如何定義的：

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;
    }
}

因為是雙向鏈表别垮，所以每個節(jié)點除了保存下一個節(jié)點的引用外，還保存了上一個節(jié)點的引用扎谎。
所以與 ArrayList 不同的是碳想，LinkedList 并不是使用數(shù)組存儲數(shù)據(jù)，而是通過上面 Node 形成的鏈表來存儲毁靶。

我們先來通過一個簡單的add方法看看實現(xiàn)：

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

主要就調用了linkLast方法將元素添加到鏈表的末尾胧奔，這就是個鏈表的操作。
除了linkLast之外還有linkFirst用于將元素添加到鏈表頭部预吆。
諸如addFirst,push,offer之類的添加元素的操作最終都是通過上面兩個方法實現(xiàn)的葡盗。

再來看看移除操作poll:

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

使用unlinkFirst方法將元素從鏈表頂部移除，對應的還有unlinkLast方法。
同樣觅够，類似removeFirst,pop,pollFirst等操作也是通過上面兩個方法實現(xiàn)的胶背。

上面的兩種操作都是直接對鏈表的頭尾操作，都可以在固定時間復雜度內完成喘先，實現(xiàn)也比較簡單钳吟。
但考慮到 LinkedList 還實現(xiàn)了 List 接口，具備了 List 的特性窘拯，例如通過下標獲取到指定值红且，這個實現(xiàn)就比較復雜了，也會消耗掉 O(n) 的時間涤姊。

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int 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;
    }
}

get方法通過調用node方法獲取到指定索引的值暇番，由于鏈表的特性使然，無法直接通過索引獲取到元素思喊，需要從端點開始逐個向內遍歷壁酬，直到遍歷到指定索引再將元素返回。
node方法考慮到性能問題恨课，在遍歷前會先判斷index值靠前還是靠后舆乔，然后選擇是從頭還是尾開始遍歷，充分利用了雙向鏈表的特性剂公。

好了希俩，上面幾個方法就是 LinkedList 源碼中最具有代表性的幾個方法了。