本文已收錄到 AndroidFamily，技術和職場問題，請關注公衆号 [彭旭銳] 提問。

前言

大家好，我是小彭。

在上一篇文章裡，我們聊到了基于動态數組 ArrayList 線性表，今天我們來讨論一個基于連結清單的線性表 —— LinkedList。

小彭的 Android 交流群 02 群已經建立啦，掃描文末二維碼進入~

思維導圖：

1. LinkedList 的特點

1.1 說一下 ArrayList 和 LinkedList 的差別？

1、資料結構：在資料結構上，ArrayList 和 LinkedList 都是 “線性表”，都繼承于 Java 的 List 接口。另外 LinkedList 還實作了 Java 的 Deque 接口，是基于連結清單的棧或隊列，與之對應的是 ArrayDeque 基于數組的棧或隊列；
2、線程安全： ArrayList 和 LinkedList 都不考慮線程同步，不保證線程安全；
3、底層實作：在底層實作上，ArrayList 是基于動态數組的，而 LinkedList 是基于雙向連結清單的。事實上，它們很多特性的差別都是因為底層實作不同引起的。比如說：

在周遊速度上：數組是一塊連續記憶體空間，基于局部性原理能夠更好地命中 CPU 緩存行，而連結清單是離散的記憶體空間對緩存行不友好；
在通路速度上：數組是一塊連續記憶體空間，支援 O(1) 時間複雜度随機通路，而連結清單需要 O(n) 時間複雜度查找元素；
在添加和删除操作上：如果是在數組的末尾操作隻需要 O(1) 時間複雜度，但在數組中間操作需要搬運元素，是以需要 O(n)時間複雜度，而連結清單的删除操作本身隻是修改引用指向，隻需要 O(1) 時間複雜度（如果考慮查詢被删除節點的時間，複雜度分析上依然是 O(n)，在工程分析上還是比數組快）；
額外記憶體消耗上： ArrayList 在數組的尾部增加了閑置位置，而 LinkedList 在節點上增加了前驅和後繼指針。

1.2 LinkedList 的多面人生

在資料結構上，LinkedList 不僅實作了與 ArrayList 相同的 List 接口，還實作了 Deque 接口（繼承于 Queue 接口）。

Deque 接口表示一個雙端隊列（Double Ended Queue），允許在隊列的首尾兩端操作，是以既能實作隊列行為，也能實作棧行為。

Queue 接口：

拒絕政策抛異常傳回特殊值入隊（隊尾）add(e)offer(e)出隊（隊頭）remove()poll()觀察（隊頭）element()peek()

Queue 的 API 可以分為 2 類，差別在于方法的拒絕政策上：

抛異常：向空隊列取資料，會抛出 NoSuchElementException 異常；向容量滿的隊列加資料，會抛出 IllegalStateException 異常。
傳回特殊值：向空隊列取資料，會傳回 null；向容量滿的隊列加資料，會傳回 false。

Deque 接口：

Java 沒有提供标準的棧接口（很好奇為什麼不提供），而是放在 Deque 接口中：

拒絕政策抛異常等價于入棧push(e)addFirst(e)出棧pop()removeFirst()觀察（棧頂）peek()peekFirst()

除了标準的隊列和棧行為，Deque 接口還提供了 12 個在兩端操作的方法：

拒絕政策抛異常傳回值增加addFirst(e)/ addLast(e)offerFirst(e)/ offerLast(e)删除removeFirst()/ removeLast()pollFirst()/ pollLast()觀察getFirst()/ getLast()peekFirst()/ peekLast()

2. LinkedList 源碼分析

這一節，我們來分析 LinkedList 中主要流程的源碼。

2.1 LinkedList 的屬性

LinkedList 底層是一個 Node 雙向連結清單，Node 節點中會持有資料 E 以及 prev 與next 兩個指針；
LinkedList 用 first 和 last 指針指向連結清單的頭尾指針。

LinkedList 的屬性很好了解的，不出意外的話又有小朋友出來舉手提問了：

‍♀️ 疑問 1：為什麼字段都不聲明 private 關鍵字？

這個問題直接回答吧。我的了解是：因為内部類在編譯後會生成獨立的 Class 檔案，如果外部類的字段是 private 類型，那麼編譯器就需要通過方法調用，而 non-private 字段就可以直接通路字段。

‍♀️ 疑問 2：為什麼字段都聲明 transient 關鍵字？

這個問題我們在分析源碼的過程中回答。

疑問比 ArrayList 少很多，LinkedList 真香（還是别高興得太早吧）。

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

    // 疑問 1：為什麼字段都不聲明 private 關鍵字？
    // 疑問 2：為什麼字段都聲明 transient 關鍵字？
    // 元素個數
    transient int size = 0;

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

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

    // 連結清單節點
    private static class Node<E> {
        // 節點資料
        // （類型擦除後：Object item;）
        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;
        }
    }
}

2.2 LinkedList 的構造方法

LinkedList 有 2 個構造方法：

1、無參構造方法： no-op；
2、帶集合的構造：在連結清單末尾添加整個集合，内部調用了 addAll 方法将整個集合添加到數組的末尾。

// 無參構造方法
public LinkedList() {
}

// 帶集合的構造方法
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

// 在連結清單尾部添加集合
public boolean addAll(Collection<? extends E> c) {
    // 索引為 size，等于在連結清單尾部添加
    return addAll(size, c);
}

2.3 LinkedList 的添加方法

LinkedList 提供了非常多的 addXXX 方法，内部都是調用一系列 linkFirst、linkLast 或 linkBefore 完成的。如果在連結清單中間添加節點時，會用到 node(index) 方法查詢指定位置的節點。

其實，我們會發現所有添加的邏輯都可以用 6 個步驟概括：

步驟 1：找到插入位置的後繼節點（在頭部插入就是 first，在尾部插入就是 null）；
步驟 2：構造新節點；
步驟 3：将新節點的 prev 指針指向前驅節點（在頭部插入就是 null，在尾部插入就是 last）；
步驟 4：将新節點的 next 指針指向後繼節點（在頭部插入就是 first，在尾部插入就是 null）；
步驟 5：将前驅節點的 next 指針指向新節點（在頭部插入沒有這個步驟）；
步驟 6：将後繼節點的 prev 指針指向新節點（在尾部插入沒有這個步驟）。

分析一下添加方法的時間複雜度，區分在連結清單兩端或中間添加元素的情況共：

如果是在連結清單首尾兩端添加：隻需要 O(1) 時間複雜度；
如果在連結清單中間添加：由于需要定位到添加位置的前驅和後繼節點，是以需要 O(n) 時間複雜度。如果事先已經獲得了添加位置的節點，就隻需要 O(1) 時間複雜度。

添加方法

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

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

public boolean add(E e) {
    linkLast(e);
    return true;
}

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        // 在尾部添加
        linkLast(element);
    else
        // 在指定位置添加
        linkBefore(element, node(index));
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 在連結清單頭部添加
private void linkFirst(E e) {
    // 1. 找到插入位置的後繼節點（first）
    final Node<E> f = first;
    // 2. 構造新節點
    // 3. 将新節點的 prev 指針指向前驅節點（null）
    // 4. 将新節點的 next 指針指向後繼節點（f）
    // 5. 将前驅節點的 next 指針指向新節點（前驅節點是 null，是以沒有這個步驟）
    final Node<E> newNode = new Node<>(null, e, f);
    // 修改 first 指針
    first = newNode;
    if (f == null)
        // f 為 null 說明首個添加的元素，需要修改 last 指針
        last = newNode;
    else
        // 6. 将後繼節點的 prev 指針指向新節點
        f.prev = newNode;
    size++;
    modCount++;
}

// 在連結清單尾部添加
void linkLast(E e) {
    final Node<E> l = last;
    // 1. 找到插入位置的後繼節點（null）
    // 2. 構造新節點
    // 3. 将新節點的 prev 指針指向前驅節點（l）
    // 4. 将新節點的 next 指針指向後繼節點（null）
    final Node<E> newNode = new Node<>(l, e, null);
    // 修改 last 指針
    last = newNode;
    if (l == null)
        // l 為 null 說明首個添加的元素，需要修改 first 指針
        first = newNode;
    else
        // 5. 将前驅節點的 next 指針指向新節點
        l.next = newNode;
    // 6. 将後繼節點的 prev 指針指向新節點（後繼節點是 null，是以沒有這個步驟）
    size++;
    modCount++;
}

// 在指定節點前添加
// 1. 找到插入位置的後繼節點
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    // 2. 構造新節點
    // 3. 将新節點的 prev 指針指向前驅節點（pred）
    // 4. 将新節點的 next 指針指向後繼節點（succ）
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        // 5. 将前驅節點的 next 指針指向新節點
        pred.next = newNode;
    size++;
    modCount++;
}

// 在指定位置添加整個集合元素
// index 為 0：在連結清單頭部添加
// index 為 size：在連結清單尾部添加
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    // 事實上，c.toArray() 的實際類型不一定是 Object[]，有可能是 String[] 等
    // 不過，我們是通過 Node中的item 承接的，是以不用擔心 ArrayList 中的 ArrayStoreException 問題
    Object[] a = c.toArray();
    // 添加的數組為空，跳過
    int numNew = a.length;
    if (numNew == 0)
        return false;

    // 1. 找到插入位置的後繼節點
    // pred：插入位置的前驅節點
    // succ：插入位置的後繼節點
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 找到 index 位置原本的節點，插入後變成後繼節點
        succ = node(index);
        pred = succ.prev;
    }
    // 插入集合元素
    for (Object o : a) {
        E e = (E) o;
        // 2. 構造新節點
        // 3. 将新節點的 prev 指針指向前驅節點
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            // pred 為 null 說明是在頭部插入，需要修改 first 指針
            first = newNode;
        else
            // 5. 将前驅節點的 next 指針指向新節點
            pred.next = newNode;
        // 修改前驅指針
        pred = newNode;
    }

    if (succ == null) {
        // succ 為 null 說明是在尾部插入，需要修改 last 指針
        last = pred;
    } else {
        // 4. 将新節點的 next 指針指向後繼節點
        pred.next = succ;
        // 6. 将後繼節點的 prev 指針指向新節點
        succ.prev = pred;
    }
    // 數量增加 numNew
    size += numNew;
    modCount++;
    return true;
}

// 将 LinkedList 轉化為 Object 數組
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

在連結清單中間添加節點時，會用到 node(index) 方法查詢指定位置的節點。可以看到維持 first 和 last 頭尾節點的作用又發揮出來了：

如果索引位置小于 size/2，則從頭節點開始找；
如果索引位置大于 size/2，則從尾節點開始找。

雖然，我們從複雜度分析的角度看，從哪個方向查詢是沒有差別的，時間複雜度都是 O(n)。但從工程分析的角度看還是有差別的，從更靠近目标節點的位置開始查詢，實際執行的時間會更短。

查詢指定位置節點

// 尋找指定位置的節點，時間複雜度：O(n)
Node<E> node(int index) {
    if (index < (size >> 1)) {
        // 如果索引位置小于 size/2，則從頭節點開始找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 如果索引位置大于 size/2，則從尾節點開始找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

LinkedList 的删除方法其實就是添加方法的逆運算，我們就不重複分析了。

// 删除頭部元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 删除尾部元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

// 删除指定元素
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

2.4 LinkedList 的疊代器

Java 的 foreach 是文法糖，本質上也是采用 iterator 的方式。由于 LinkedList 本身就是雙向的，是以 LinkedList 隻提供了 1 個疊代器：

ListIterator listIterator()：雙向疊代器

與其他容器類一樣，LinkedList 的疊代器中都有 fail-fast 機制。如果在疊代的過程中發現 expectedModCount 變化，說明資料被修改，此時就會提前抛出 ConcurrentModificationException 異常（當然也不一定是被其他線程修改）。

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

// 非靜态内部類
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    // 建立疊代器時會記錄外部類的 modCount
    private int expectedModCount = modCount;

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

    public E next() {
        // 更新 expectedModCount
        checkForComodification();
        ...
    }
    ...
}

2.5 LinkedList 的序列化過程

‍♀️ 疑問 2：為什麼字段都聲明 transient 關鍵字？

LinkedList 重寫了 JDK 序列化的邏輯，不序列化連結清單節點，而隻是序列化連結清單節點中的有效資料，這樣序列化産物的大小就有所降低。在反序列時，隻需要按照對象順序依次添加到連結清單的末尾，就能恢複連結清單的順序。

// 序列化和反序列化隻考慮有效資料

// 序列化過程
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // 寫傳入連結表長度
    s.writeInt(size);

    // 寫入節點上的有效資料
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

// 反序列化過程
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // 讀取連結清單長度
    int size = s.readInt();
  
    // 讀取有效元素并用 linkLast 添加到連結清單尾部
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

2.6 LinkedList 的 clone() 過程

LinkedList 中的 first 和 last 指針是引用類型，是以在 clone() 中需要實作深拷貝。否則，克隆後兩個 LinkedList 對象會互相影響：

private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

public Object clone() {
    LinkedList<E> clone = superClone();

    // Put clone into "virgin" state
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // 将原連結清單中的資料依次添加到新立案表中
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}

2.7 LinkedList 如何實作線程安全？

有 5 種方式：

方法 1 - 使用 Collections.synchronizedList 包裝類：原理也是在所有方法上增加 synchronized 關鍵字；
方法 2 - 使用 ConcurrentLinkedQueue 容器類：基于 CAS 無鎖實作的線程安全隊列；
方法 3 - 使用 LinkedBlockingQueue 容器：基于加鎖的阻塞隊列，适合于帶阻塞操作的生産者消費者模型；
方法 4 - 使用 LinkedBlockingDeque 容器：基于加鎖的阻塞雙端隊列，适合于帶阻塞操作的生産者消費者模型；
方法 5 - 使用 ConcurrentLinkedDeque 容器類：基于 CAS 無鎖實作的線程安全雙端隊列。

3. 總結

1、LinkedList 是基于連結清單的線性表，同時具備 List、Queue 和 Stack 的行為；
2、在查詢指定位置的節點時，如果索引位置小于 size/2，則從頭節點開始找，否則從尾節點開始找；
3、LinkedList 重寫了序列化過程，隻處理連結清單節點中有效的元素；
4、LinkedList 和 ArrayList 都不考慮線程同步，不保證線程安全。

在上一篇文章裡，我們提到了 List 的數組實作 ArrayList，而 LinkedList 不僅是 List 的連結清單實作，同時還是 Queue 和 Stack 的連結清單實作。那麼，在 Java 中的 Queue 和 Stack 的數組實作是什麼呢，這個我們在下篇文章讨論，請關注。

說一下 ArrayList 和 LinkedList 的差別？

前言

1. LinkedList 的特點

1.1 說一下 ArrayList 和 LinkedList 的差別？

1.2 LinkedList 的多面人生

2. LinkedList 源碼分析

2.1 LinkedList 的屬性

2.2 LinkedList 的構造方法

2.3 LinkedList 的添加方法

2.4 LinkedList 的疊代器

2.5 LinkedList 的序列化過程

2.6 LinkedList 的 clone() 過程

2.7 LinkedList 如何實作線程安全？

3. 總結

小彭的 Android 交流群 02 群

繼續閱讀

go基礎——03(array、slice、map)

JavaScript 中splice()方法增删數組元素

[完]PHP Array 建立、索引、添加、删除、判斷是否存在指定元素

JavaScript splice() 方法的周遊循環使用傳回值

JavaScript - 數組

javaScript中Array(數組)的splice函數

javascript數組基礎方法

Javascript删除數組中某一項或幾項的幾種方法1. splice2. delete

使用mybatis遇到的一些錯誤

JavaScript Array對象indexOf()方法的實作

數組【從入門到精通】

JAVA雜談 —— 1.1 final 修飾引用類型變量

LeetCode-Linked List Cycle II

了解javascript類數組

JavaScript數組reduce

ES6中數組和對象的周遊對象對象