LinkedList源碼分析

LinkedList是基于連結清單實作的。适合大量資料的插入、修改以及删除。

連結清單節點定義

這是一個雙向連結清單，有前驅節點和後繼節點。

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

全局變量

雖然這不是用指針實作的，但是為了表述還是用“指針”和“指向”來說明（也可以說為引用）。

transient int size = ;//連結清單元素個數

    transient Node<E> first;//頭指針

    transient Node<E> last;//尾指針

構造方法

有兩個構造方法。

public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

添加頭節點

private void linkFirst(E e) {
        final Node<E> f = first;//f指向頭節點
        final Node<E> newNode = new Node<>(null, e, f);//建立新節點，元素為e，新節點的前驅節點為null，後繼節點為f
        first = newNode;//頭指針指向新節點
        if (f == null)
            last = newNode;//如果原頭節點為空（說明連結清單為空），則将尾指針指向新節點
        else
            f.prev = newNode;//否則原節點的前驅節點指向新節點
        size++;//元素數量加1
        modCount++;//連結清單結構改變次數加1
    }

添加尾節點

這裡并沒有用private修飾，而添加頭節點确用了private，不知道為什麼。

void linkLast(E e) {
        final Node<E> l = last;//l指向尾節點
        final Node<E> newNode = new Node<>(l, e, null);//建立新節點，元素為e，新節點的前驅節點為l,後繼節點為null
        last = newNode;//尾指針指向新節點
        if (l == null)
            first = newNode;//如果原尾節點為空（說明連結清單為空），則将頭指針指向新節點
        else
            l.next = newNode;//否則原尾節點的後繼節點指向新節點
        size++;//元素個數加1
        modCount++;//連結清單結構改變次數加1
    }

在非空節點前插入新節點

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;//聲明succ不為空
        final Node<E> pred = succ.prev;//succ的前驅節點
        final Node<E> newNode = new Node<>(pred, e, succ);//新節點，前驅指向pred，後繼指向succ
        succ.prev = newNode;//succ的前驅指向新節點
        if (pred == null)
            first = newNode;//如果前驅為null，則目前插入的新節點為頭節點，頭指針指向它
        else
            pred.next = newNode;//否則pred的next指向新節點
        size++;
        modCount++;
    }

删除頭節點和尾節點

/**
     * 删除頭節點
     */
    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;
    }

    /**
     * 删除尾節點
     */
    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;//x的前驅節點
        final Node<E> prev = x.prev;//x的後繼節點

        if (prev == null) {
            first = next;//如果前驅節點為空，則目前節點為頭節點，删除目前節點x後，頭指針指向x的後繼
        } else {
            prev.next = next;//否則x的前驅節點的後繼指向x的後繼節點
            x.prev = null;//x的前驅指向null
        }

        if (next == null) {
            last = prev;//如果後繼節點為空，則目前節點為尾節點，删除目前節點x後，尾指針指向x的前驅節點
        } else {
            next.prev = prev;/否則x的後繼節點的前驅指向x的前驅節點
            x.next = null;//x的後繼指向null
        }

        x.item = null;//x的元素指派為null便于GC回收空間
        size--;
        modCount++;
        return element;
    }

LinkedList主要的連結清單操作就這麼多，對外公開的方法都是基于以上這些操作的，以下是源碼：

/**
     * Returns the first element in this list.
     *
     * @return the first element in this list
     * @throws NoSuchElementException if this list is empty
     */
       public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    /**
     * Returns the last element in this list.
     *
     * @return the last element in this list
     * @throws NoSuchElementException if this list is empty
     */
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    /**
     * Removes and returns the first element from this list.
     *
     * @return the first element from this list
     * @throws NoSuchElementException if this list is empty
     */
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    /**
     * Removes and returns the last element from this list.
     *
     * @return the last element from this list
     * @throws NoSuchElementException if this list is empty
     */
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

    /**
     * Inserts the specified element at the beginning of this list.
     *
     * @param e the element to add
     */
    public void addFirst(E e) {
        linkFirst(e);
    }

    /**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #add}.
     *
     * @param e the element to add
     */
    public void addLast(E e) {
        linkLast(e);
    }

以上操作的時間複雜度都是O(1)，是以LinkedList對頭/尾節點的插入删除操作效率還是比較高的。但是對于查找，以及修改等操作的就不高效了，時間複雜度變為O(n)

public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

查找元素

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    Node<E> node(int index) {
        // assert isElementIndex(index);

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

添加元素

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

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

修改元素

public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

删除元素

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

對于LinkedList和ArrayList的效率總結如下：

**直接添加元素：**LinkedList和ArrayList都是在尾部添加的。對于ArrayList來說，因為自動增長機制，在數組複制上會花費大量時間，是以資料量大的情況下，LinkedList的添加效率更高。

指定位置插入/删除/修改元素：這種方式下，兩種方式都要先找到指定位置的元素，然後再進行插入操作，時間複雜度都為O(n)。但是ArrayList還需要數組複制，是以會相對慢一些。

随機通路：基于數組的ArrayList的随機通路時間遠小于LinkedList 的，因為LinkedList需要移動指針。

是以資料不是經常變動時，用ArrayList好，而需要平凡改動時，用LinkedList好。如果需要線程同步，則使用Vector，因為ArrayList和LinkedList都不是同步的

另外LinkedList經常被用作隊列及棧使用

實作隊列操作：

public E peek() {//檢視第一個，但不删除
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    public E element() {//檢視第一個，但不删除
        return getFirst();
    }

    public E poll() {//擷取第一個，并且删除
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    public E remove() {//擷取第一個并且删除
        return removeFirst();
    }

    public boolean offer(E e) {//在隊列尾部添加一個
        return add(e);
    }

實作雙向隊列操作：

實作棧的操作：

public E poll() {//檢視棧頂但不删除
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    public void push(E e) {//壓棧
        addFirst(e);
    }

    public E pop() {//出棧
        return removeFirst();
    }

兩篇參考文章：

https://www.cnblogs.com/yakovchang/p/java_linkedlist.html
https://www.cnblogs.com/springfor/p/3985333.html

【深入Java基礎】LinkedList源碼分析LinkedList源碼分析

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