摘要：刪除元素作為雙端隊列，刪除元素也有兩種方式，一種是隊列首刪除元素，一種是隊列尾刪除元素。作為，又要支持中間刪除元素，所以刪除元素一個有三個方法，分別如下。在中間刪除元素比較低效，首先要找到刪除位置的節(jié)點，再修改前后指針，時間復(fù)雜度為。

LinkedList是一個以雙向鏈表實現(xiàn)的List，它除了作為List使用，還可以作為隊列或者棧來使用，它是怎么實現(xiàn)的呢？讓我們一起來學(xué)習(xí)吧。

通過繼承體系，我們可以看到LinkedList不僅實現(xiàn)了List接口，還實現(xiàn)了Queue和Deque接口，所以它既能作為List使用，也能作為雙端隊列使用，當(dāng)然也可以作為棧使用。

// 元素個數(shù)
transient int size = 0;
// 鏈表首節(jié)點
transient Node first;
// 鏈表尾節(jié)點
transient Node last;

典型的雙鏈表結(jié)構(gòu)

private static class Node {
    E item;
    Node next;
    Node prev;

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

public LinkedList() {
}

public LinkedList(Collection c) {
    this();
    addAll(c);
}

是一個無界的隊列

作為一個雙端隊列，添加元素主要有兩種，一種是在隊列尾部添加元素，一種是在隊列首部添加元素，這兩種形式在LinkedList中主要是通過下面兩個方法來實現(xiàn)的。

// 從隊列首添加元素
private void linkFirst(E e) {
    // 首節(jié)點
    final Node f = first;
    // 創(chuàng)建新節(jié)點，新節(jié)點的next是首節(jié)點
    final Node newNode = new Node<>(null, e, f);
    // 讓新節(jié)點作為新的首節(jié)點
    first = newNode;
    // 判斷是不是第一個添加的元素
    // 如果是就把last也置為新節(jié)點
    // 否則把原首節(jié)點的prev指針置為新節(jié)點
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    // 元素個數(shù)加1
    size++;
    // 修改次數(shù)加1，說明這是一個支持fail-fast的集合
    modCount++;
}

// 從隊列尾添加元素
void linkLast(E e) {
    // 隊列尾節(jié)點
    final Node l = last;
    // 創(chuàng)建新節(jié)點，新節(jié)點的prev是尾節(jié)點
    final Node newNode = new Node<>(l, e, null);
    // 讓新節(jié)點成為新的尾節(jié)點
    last = newNode;
    // 判斷是不是第一個添加的元素
    // 如果是就把first也置為新節(jié)點
    // 否則把原尾節(jié)點的next指針置為新節(jié)點
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 元素個數(shù)加1
    size++;
    // 修改次數(shù)加1
    modCount++;
}

public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

// 作為無界隊列，添加元素總是會成功的
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

典型的雙鏈表在首尾添加元素的方法. 上面是作為雙端隊列來看，它的添加元素分為首尾添加元素.

作為List，是要支持在中間添加元素的，主要是通過下面這個方法實現(xiàn)的。

// 在節(jié)點succ之前添加元素
void linkBefore(E e, Node succ) {
    // succ是待添加節(jié)點的后繼節(jié)點
    // 找到待添加節(jié)點的前置節(jié)點
    final Node pred = succ.prev;
    // 在其前置節(jié)點和后繼節(jié)點之間創(chuàng)建一個新節(jié)點
    final Node newNode = new Node<>(pred, e, succ);
    // 修改后繼節(jié)點的前置指針指向新節(jié)點
    succ.prev = newNode;
    // 判斷前置節(jié)點是否為空
    // 如果為空，說明是第一個添加的元素，修改first指針
    // 否則修改前置節(jié)點的next為新節(jié)點
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    // 修改元素個數(shù)
    size++;
    // 修改次數(shù)加1
    modCount++;
}

// 尋找index位置的節(jié)點
Node node(int index) {
    // 因為是雙鏈表
    // 所以根據(jù)index是在前半段還是后半段決定從前遍歷還是從后遍歷
    // 這樣index在后半段的時候可以少遍歷一半的元素
    if (index < (size >> 1)) {
        // 如果是在前半段
        // 就從前遍歷
        Node x = 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;
    }
}

// 在指定index位置處添加元素
public void add(int index, E element) {
    // 判斷是否越界
    checkPositionIndex(index);
    // 如果index是在隊列尾節(jié)點之后的一個位置
    // 把新節(jié)點直接添加到尾節(jié)點之后
    // 否則調(diào)用linkBefore()方法在中間添加節(jié)點
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

在隊列首尾添加元素很高效，時間復(fù)雜度為O(1)。
在中間添加元素比較低效，首先要先找到插入位置的節(jié)點，再修改前后節(jié)點的指針，時間復(fù)雜度為O(n)。

作為雙端隊列，刪除元素也有兩種方式，一種是隊列首刪除元素，一種是隊列尾刪除元素。
作為List，又要支持中間刪除元素，所以刪除元素一個有三個方法，分別如下。

// 刪除首節(jié)點
private E unlinkFirst(Node f) {
    // 首節(jié)點的元素值
    final E element = f.item;
    // 首節(jié)點的next指針
    final Node next = f.next;
    // 添加首節(jié)點的內(nèi)容，協(xié)助GC
    f.item = null;
    f.next = null; // help GC
    // 把首節(jié)點的next作為新的首節(jié)點
    first = next;
    // 如果只有一個元素，刪除了，把last也置為空
    // 否則把next的前置指針置為空
    if (next == null)
        last = null;
    else
        next.prev = null;
    // 元素個數(shù)減1
    size--;
    // 修改次數(shù)加1
    modCount++;
    // 返回刪除的元素
    return element;
}
// 刪除尾節(jié)點
private E unlinkLast(Node l) {
    // 尾節(jié)點的元素值
    final E element = l.item;
    // 尾節(jié)點的前置指針
    final Node prev = l.prev;
    // 清空尾節(jié)點的內(nèi)容，協(xié)助GC
    l.item = null;
    l.prev = null; // help GC
    // 讓前置節(jié)點成為新的尾節(jié)點
    last = prev;
    // 如果只有一個元素，刪除了把first置為空
    // 否則把前置節(jié)點的next置為空
    if (prev == null)
        first = null;
    else
        prev.next = null;
    // 元素個數(shù)減1
    size--;
    // 修改次數(shù)加1
    modCount++;
    // 返回刪除的元素
    return element;
}
// 刪除指定節(jié)點x
E unlink(Node x) {
    // x的元素值
    final E element = x.item;
    // x的前置節(jié)點
    final Node next = x.next;
    // x的后置節(jié)點
    final Node prev = x.prev;

    // 如果前置節(jié)點為空
    // 說明是首節(jié)點，讓first指向x的后置節(jié)點
    // 否則修改前置節(jié)點的next為x的后置節(jié)點
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    // 如果后置節(jié)點為空
    // 說明是尾節(jié)點，讓last指向x的前置節(jié)點
    // 否則修改后置節(jié)點的prev為x的前置節(jié)點
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    // 清空x的元素值，協(xié)助GC
    x.item = null;
    // 元素個數(shù)減1
    size--;
    // 修改次數(shù)加1
    modCount++;
    // 返回刪除的元素
    return element;
}
// remove的時候如果沒有元素拋出異常
public E removeFirst() {
    final Node f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// remove的時候如果沒有元素拋出異常
public E removeLast() {
    final Node l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
// poll的時候如果沒有元素返回null
public E pollFirst() {
    final Node f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// poll的時候如果沒有元素返回null
public E pollLast() {
    final Node l = last;
    return (l == null) ? null : unlinkLast(l);
}
// 刪除中間節(jié)點
public E remove(int index) {
    // 檢查是否越界
    checkElementIndex(index);
    // 刪除指定index位置的節(jié)點
    return unlink(node(index));
}

在隊列首尾刪除元素很高效，時間復(fù)雜度為O(1)。
在中間刪除元素比較低效，首先要找到刪除位置的節(jié)點，再修改前后指針，時間復(fù)雜度為O(n)。

LinkedList是雙端隊列， 雙端隊列可以作為棧使用.

棧的特性是LIFO(Last In First Out)，所以作為棧使用也很簡單，添加刪除元素都只操作隊列首節(jié)點即可。

public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

LinkedList是一個以雙鏈表實現(xiàn)的List；

LinkedList還是一個雙端隊列，具有隊列、雙端隊列、棧的特性；

LinkedList在隊列首尾添加、刪除元素非常高效，時間復(fù)雜度為O(1)；

LinkedList在中間添加、刪除元素比較低效，時間復(fù)雜度為O(n)；

LinkedList不支持隨機訪問，所以訪問非隊列首尾的元素比較低效；

LinkedList在功能上等于ArrayList + ArrayDeque；