集合框架 （第 04 篇） 源碼分析：LinkedList

一、集合框架源碼分析

原文持續(xù)更新鏈接: https://github.com/about-cloud/JavaCore

正文

源碼分析基于 jdk-11.0.1

本文重點

添加元素
刪除元素

一、擴展關(guān)系

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

LinkedList 繼承至 AbstractSequentialList表現(xiàn)其具有連續(xù)性，同時實現(xiàn)了線性的 List 和雙端的 Deque，LinkedList 底層實現(xiàn)就是雙向鏈表。

二、源碼分析

重點屬性

// 記錄元素數(shù)量
transient int size = 0;
// 記錄鏈表更改的次數(shù)
protected transient int modCount = 0;
// 指向頭節(jié)點
transient Node<E> first;
// 指向尾節(jié)點
transient Node<E> last;

// 鏈表中的每個節(jié)點
private static class Node<E> {
    // 節(jié)點中存放的元素
    E item;
    // 前驅(qū)節(jié)點
    Node<E> next;
    // 后繼節(jié)點
    Node<E> prev;

    // 節(jié)點內(nèi)唯一的方法(構(gòu)造方法)來注入元素、前驅(qū)節(jié)點、后繼節(jié)點
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

2.1、添加元素

添加元素到鏈表尾部

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

// 默認將元素添加到雙向鏈表的尾部
void linkLast(E e) {
    // 將原來的最后一個節(jié)點存儲起來
    final Node<E> l = last;
    // 實例化一個新的節(jié)點，也就是被鏈入的節(jié)點，
    // 并通過Node唯一的構(gòu)造方法注入前驅(qū)節(jié)點和元素
    // (因為它被鏈入尾部，所以后面是沒有節(jié)點的)
    final Node<E> newNode = new Node<>(l, e, null);
    // 將新構(gòu)建的節(jié)點鏈入尾部
    last = newNode;
    // 如果鏈表為空，那么它也是頭節(jié)點
    if (l == null)
        first = newNode;
    else
        l.next = newNode; // 否則，剛才那個節(jié)點的后繼節(jié)點就是這個新節(jié)點
    // 記錄元素個數(shù)加 1
    size++;
    // 更改次數(shù)加 1
    modCount++;
}

添加元素到頭部，操作與此類似。

重點：添加元素到指定index位置

public void add(int index, E element) {
    // 和 ArrayList 相似，只要遇到 index ，必做下標越界檢查
    // 這也符合異常處理規(guī)范：如有異常提前拋出
    checkPositionIndex(index);
    // 如果正好是鏈表的尾部之后，則鏈入尾部
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index)); // 否則鏈入 index 位置元素的前面
}
// 在正式鏈表前，還需要計算index處的節(jié)點(或者說是獲取index處的節(jié)點)
// 前面說過，LinkedList 實現(xiàn)至 List接口，它也有List線性的特性，可以進行迭代
// 這個方法有個牛逼的地方，請看下方
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 判斷 index “距離”哪頭近，就從哪頭開始遍歷，這樣可以節(jié)省時間
    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;
    }
}

/**
 * @param e 被鏈入的元素
 * @param succ index 位置的元素(下文成其為succ節(jié)點 -- 也就是新節(jié)點的后繼節(jié)點)
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 獲取 succ節(jié)點的前驅(qū)節(jié)點引用
    final Node<E> pred = succ.prev;
    // 構(gòu)造新的、即將被鏈入的節(jié)點
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 將新節(jié)點設(shè)置為succ節(jié)點的前驅(qū)節(jié)點
    succ.prev = newNode;
    
    // 以下操作就是不要忘記頭節(jié)點、尾節(jié)點、size、modCount
    // 如果succ節(jié)點沒有前驅(qū)節(jié)點，那么新鏈入的節(jié)點就是頭節(jié)點
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode; // 否則，將新節(jié)點設(shè)置成之前succ的前驅(qū)節(jié)點的后繼節(jié)點
    size++;
    modCount++;
}

圖解雙向鏈表的添加模式：

鏈表添加元素前

第一步：通過 Node<E> node(int index) 獲取 succ 節(jié)點（假設(shè)index為3）

使用node(index)方法獲取succ節(jié)點

第二步：鏈表添加元素

// succ 前驅(qū)節(jié)點是2節(jié)點，pred節(jié)點實際指向2節(jié)點指向的地址
① final Node<E> pred = succ.prev;
// 構(gòu)造新的節(jié)點，同時又設(shè)置前驅(qū)節(jié)點為 pred(也就是指向2節(jié)點)、后繼節(jié)點為succ
② final Node<E> newNode = new Node<>(pred, e, succ);
// 設(shè)置succ的前驅(qū)節(jié)點為新節(jié)點
③ succ.prev = newNode;
④ if (pred == null) // 這里不介紹 pred 為空的情況
      first = newNode;
  else
      pred.next = newNode; // 設(shè)置 pred節(jié)點（也就是2節(jié)點）的后繼節(jié)點為新節(jié)點
鏈入元素

重點：2.2 刪除元素

public boolean remove(Object o) {
    // 分兩種情況：被刪除的元素為nul與不為空
    if (o == null) {
        // for 循環(huán)判斷
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

// 解鏈方法，刪除節(jié)點方法
E unlink(Node<E> x) {
    // assert x != null;
    // 被刪除節(jié)點的元素
    final E element = x.item;
    // 被刪除節(jié)點的后繼節(jié)點
    final Node<E> next = x.next;
    // 被刪除節(jié)點的前驅(qū)節(jié)點
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null; // 空引用，利于GC回收“無用”的對象
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null; // 空引用，利于GC回收“無用”的對象
    }

    x.item = null; // 空引用，利于GC回收“無用”的對象
    size--;
    modCount++;
    return element;
}

圖解刪除LinkedList中的節(jié)點

假設(shè)刪除是3節(jié)點（這里不介紹頭結(jié)點和尾節(jié)點為空的情況）

首先獲取 被刪除節(jié)點x（既節(jié)點3） 的 后繼節(jié)點next（既節(jié)點4） 和 前驅(qū)節(jié)點prev（既節(jié)點2）;

然后將prev節(jié)點（2節(jié)點）的next指向next節(jié)點（4節(jié)點）；

然后將next節(jié)點（4節(jié)點）的prev指向prev節(jié)點（2節(jié)點）；

此時就完成，刪除操作要比添加操作更為簡單。

圖解刪除LinkedList中的節(jié)點

原文持續(xù)更新鏈接: https://github.com/about-cloud/JavaCore

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容