Java 容器源碼分析之 LinkedList

概覽

同 ArrayList 一樣，LinkedList 也是對 List 接口的一種具體實作。不同的是，ArrayList 是基于數組來實作的，而 LinkedList 是基于雙向連結清單實作的。LinkedList 類的聲明如下：

1
2
3

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

LinkedList 繼承自 AbstractSequentialList，實作了 List 接口，同時還實作了 Deque 接口。AbstractSequentialList 是 AbstractList 的子類，為基于順序通路的連結清單提供了一些基本的實作。LinkedList 實作了 Deque 接口，Deque 接口是一種雙端隊列，可以作為 FIFO 隊列和 LIFO 隊列（棧）來使用。LinkedList 支援所有元素，包括 null。

下面基于JDK 8 中的代碼對LinkedList的實作加以分析。

底層結構

LinkedList 基于雙向連結清單進行實作，并使用兩個引用 first 和 last 分别指向雙向連結清單的頭尾元素。同 ArrayList 一樣，使用 modCount 來記錄結構化修改的次數，并依此實作 fail-fast 機制。

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;

雙向連結清單的節點結構如下，分别用 prev 和 next 指向該節點的前驅和後繼結點。

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

雙向連結清單操作

LinkedList 提供的所有操作都是在雙向連結清單的基礎上完成的。Dqeue 接口的一些實作就是在雙向連結清單的兩端進行操作，也是基于對頭和尾部元素的操作。總的來說，雙向連結清單的操作并不複雜，下面簡單地進行解析，大部分操作都是對以下幾種操作的封裝。

向頭部添加元素

//将一個元素加入雙向連結清單的頭部
private void linkFirst(E e) {
    final Node<E> f = first;
    //新節點的前驅節點為null，後繼節點為原來的頭節點
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null) //原來的頭節點為空
        //新加入的節點是第一個也是最後一個
        last = newNode;
    else
        //修改原來頭節點的前驅指向
        f.prev = newNode;
    //調整連結清單大小
    size++;
    //修改計數器
    modCount++;
}

向尾部添加元素

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

從中間插入元素

//在一個非空節點前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev; //擷取前驅
    //注意建立節點的前驅與後繼
    final Node<E> newNode = new Node<>(pred, e, succ);
    //調整相關節點的前驅與後繼關系
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    //修改大小
    size++;
    modCount++;
}

移除頭部節點

//将頭節點從連結清單移除
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    //引用修改為null，友善GC
    f.item = null;
    f.next = null; // help GC
    //調整頭節點
    first = next;
    if (next == null) //移除後連結清單為空
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

移除尾部節點

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

移除任意一個非空節點

//移除一個非空節點
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; //後繼

    //注意對前驅為null的處理
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    //注意對後繼為null的處理
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

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

清空連結清單

主要是為了友善垃圾回收器進行垃圾回收。

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

根據索引擷取元素

因為是雙向連結清單，可向前周遊，也可向後周遊。查找時雙向進行，靠近頭節點則從前向後查找；靠近尾部，則從後向前查找。

//根據索引擷取元素
Node<E> node(int index) {
    // assert isElementIndex(index);
    //雙向查找，根據index和size判斷
    //前半段，從頭節點向後查找
    //後半段，從尾節點向前查找
    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;
    }
}

反查一個元素的索引

第一次出現：

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

最後一次出現，從後向前查找：

public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

疊代器

通過 next 的指向依次進行周遊。還提供了反向的疊代（從尾部到頭部），通過 prev 的指向依次周遊。

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    //建立疊代器時的modCount，檢測并發修改，fail-fast
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

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

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

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        //如果next == null， 前一個為尾節點
        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<E> lastNext = lastReturned.next;
        //調用unlink方法移除元素
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        //修改modCount
        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<? super E> action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }
    //檢查并發修改，fail-fast
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

小結

LinkedList 是 List 接口基于雙向連結清單的一種實作，同時還實作了 Deque 接口，可以作為 FIFO 和 LIFO 隊列使用。雙向連結清單的實作使得插入和删除操作的代價降低，可以在常數時間内完成；然而查找操作需要周遊清單，盡管雙向清單使得可以從兩端進行查找，但在長度較長時仍然需要較長的時間。

在大多數情況下會選擇使用 ArrayList，盡管插入和删除代價相較于 LinkedList 更高，但随機通路的特性使得在查找方面 ArrayList 比 LinkedList 具有更多的優勢。關于 ArrayList 和 LinkedList 的使用選擇上可以參考 StackOverflow 上的這個問答。

熬夜不易,點選請老王喝杯烈酒！！！！！！！

Java 容器源碼分析之 LinkedList

概覽

底層結構

雙向連結清單操作

向頭部添加元素

向尾部添加元素

從中間插入元素

移除頭部節點

移除尾部節點

移除任意一個非空節點

清空連結清單

根據索引擷取元素

反查一個元素的索引

疊代器

小結

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method