大家好，我是程式員xiao熊，本篇内容将為大家Java集合中LinkedList的源碼解析，本篇是源碼解讀系列的第一篇，後續還會有其他的源碼解讀分享，如果大家有想要了解的内容，可以寫在評論中，或者私信告訴我；廢話不多說，開始進入正題吧，由于篇幅問題，本篇内容如下：

LinkedList介紹
LinkedList底層結構分析
LinkedList構造函數
LinkedList添加元素方法說明
LinkedList添加元素方法源碼解析

1、LinkedList介紹

LinkedList繼承結構圖

從繼承結構圖中可以看出，LinkedList實作了List、Queue、Deque接口，具備被了List的特性，例如排序、元素可重複等；由于實作了Queue、Deque接口，具備了隊列的FIFO以及在隊列兩端添加/删除元素，具體如下：

LinkedList本質是沒有容量限制的連結清單，底層使用内部類Node實作連結清單節點
LinkedList可接收所有類型的元素，包括null值；并且可以重複添加元素
繼承了雙端隊列的特性，可在頭部、尾部添加或者删除元素以及其他的雙端隊列操作；
LinkedList不是線程安全的，需要對其進行封裝，例如：Collections.synchronizedList
由于線程不安全，是以疊代器Iterator的操作會在多線程操作LinkedList時抛出并發修改異常： ConcurrentModificationException，具體原因可參考源碼分析部分
應用程式不能依賴ConcurrentModificationException異常來作為業務邏輯的一部分，因為并發場景不一定100%會抛出這個異常；

2、LinkedList底層結構分析

LinkedList本質是使用Node構成的雙向連結清單，LinkedList中包含頭結點、尾結點以及元素數量這三個關鍵屬性；而元素節點Node則由資料項(item)、前驅節點指針（prev）、後繼節點指針（next）組成，通過前驅節點指針、後繼節點指針來連接配接前後元素，最終構成雙向連結清單；具體代碼如下：

Node結構

===============LinkedList屬性 ===================
// 元素數量
transient int size = 0;

// 頭結點
transient Node<E> first;
// 尾結點
transient Node<E> last;



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

3、LinkedList構造函數

LinkedList有兩個構造函數：

1. 預設無參構造函數：什麼邏輯也沒有，建立一個空的連結清單

2. 入參是集合的構造函數：利用入參集合建立雙向連結清單，核心邏輯是addAll方法，具體邏輯參考後續的講解

// 無參構造函數，建立一個空的連結清單
public LinkedList() {
}


// 集合作為參數的構造函數，建立一個包含集合元素的連結清單
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

4、LinkedList添加元素方法說明

根據LinkedList實作的接口，我将其中的方法大緻分為了三類：Queue(隊列)接口中的方法、Deque(雙端隊列)中接口的方法、List(清單)接口中的方法；下面将方法進行講解（隊列方法、清單方法）；

隊列接口的方法

addFirst(E e)、addLast(E e)、offer(E e)、offerFirst(E e)、offerLast(E e)

清單接口的方法

add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)

5、LinkedList添加元素方法源碼解析

如前所述，LinkedList是由Node組成的雙向連結清單，是以需要重點關注的核心内容是兩個節點如何連接配接；在兩個元素之間插入元素以及删除元素時，指向前一個節點和後一個節點的指針如何變化；

5.1、在末尾追加元素

由于LinkedList實作了List、Queue、Deque，是以在添加元素方面也具備了多種方式，由于上一小節已經對方法所屬接口進行了簡單講解，後續内容将不再重複；

在末尾添加元素的方法有add(E e)、offer(E e)、addLast(E e)、offerLast(E e);不過這些方法最終都會調用linkLast(E e)，是以本小節内容主要是分析linkLast的執行過程；linkLast方法業務邏輯過程具體如下：

1、擷取尾結點

2、建立新節點，以添加的元素作為資料項，前驅節點指針指向尾結點，後繼節點指針為空

3、尾結點指針指向新節點

4、如果原來的尾結點為空，則表示這是一個空的連結清單，則頭結點指針也指向新建立的節點，即頭指針也指向新的節點

5、如果原來的尾結點不為空，則将原來尾結點的後繼節點指針指向新節點

6、更新元素數量

7、更新修改連結清單結構的次數

尾部添加元素流程圖

代碼如下：

public boolean add(E e) {
    // 将元素添加至尾部
    linkLast(e);
    return true;
}

public boolean offer(E e) {
    return add(e);
}

public void addLast(E e) {
// 添加元素至預設，具體參考 add方法的解析
    linkLast(e);
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}
===========最終調用的方法+++++++++++++++
void linkLast(E e) {
// 1.擷取尾結點
    final Node<E> l = last;
// 2.建立新節點，以添加的元素作為資料項，前驅節點指針指向尾結點，後繼節點指針為空
    final Node<E> newNode = new Node<>(l, e, null);
    // 3.尾結點指針指向新節點
last = newNode;
// 4.如果原來的尾結點為空，則表示這是一個空的連結清單，則頭結點指針也指向新建立的節點
    if (l == null)
        first = newNode;
    else
// 5.	如果原來的尾結點不為空，則将原來尾結點的後繼節點指針指向新節點
        l.next = newNode;
// 6.更新元素數量
    size++;
// 7.更新修改連結清單結構的次數
    modCount++;
}

5.2、在指定位置添加元素

在指定位置添加元素的核心方法是linkBefore，具體過程如下：

1、校驗需要添加元素的位置是否合法，不合法則抛出索引越界異常

2、如果添加元素的索引位置是最後一個位置，則将元素添加至預設，具體參考“在尾部添加元素”的解析

3、如果索引位置不是最後一個位置，則将節點添加至指定位置，具體如下

a) 根據索引擷取對應位置的元素

i. 如果索引位置在前半段，則從開始位置周遊，直到索引的位置

ii. 如果索引位置在後半段，則從尾部位置周遊，直到索引的位置

b) 擷取索引處的節點的前驅節點(該節點的後繼節點指針需要指向新添加的節點)

c) 建立節點，以添加的元素為資料項，新節點的前驅節點指針指向指定索引位置的前驅節點，新節點的後繼節點指針指向索引位置處的節點

d) 将索引位置的節點的前驅節點指針指向建立節點

e) 如果索引位置的前驅節點為空，則表示連結清單為空，或者索引位置的節點是頭結點，則需要更新頭結點為建立的節點

f) 如果前驅節點不為空，則将前驅節點的後繼節點指針指向新節點

g) 更新元素數量

h) 更新修改連結清單結構的次數

在指定位置添加元素的流程圖

代碼如下：

public void add(int index, E element) {
    // 1. 校驗需要添加元素的位置是否合法，不合法則抛出索引越界異常
checkPositionIndex(index);

//2.如果添加元素的索引位置是最後一個位置，則将元素添加至預設，具體參考之前的解析
    if (index == size)
        linkLast(element);
    else
// 如果索引位置不是最後一位，則将元素element添加至索引位置index處的節點node(index)之前 （node(index)表示索引index處的節點）
        linkBefore(element, node(index));
}
================================
private void checkPositionIndex(int index) {
// 如果需要添加元素的索引不合法，則抛出索引越界異常
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
================================
private boolean isPositionIndex(int index) {
// 如果索引大于等于0并且小于等于元素數量，則表示索引位于範圍之内，傳回true；否則傳回false
    return index >= 0 && index <= size;
}
================================
// 查詢索引位置的節點，使用了二分查找法，但也僅僅使用了一次
Node<E> node(int index) {
    // assert isElementIndex(index);
// 如果索引位置在前半段，則從開始位置周遊，直到索引的位置
    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;
    }
}
===============================
// 将元素添加至指定索引位置處（即将節點插入指定索引位置處的節點之前）
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++;
}

5.3、添加集合

LinkList提供了兩種方法添加集合元素：addAll(Collection<? extends E> c) 和addAll(int index, Collection<? extends E> c)；但是前者也是調用的後者，位置是在末尾；是以本小節重點分析講解addAll(int index, Collection<? extends E> c)；該方法的業務邏輯過程如下：

1、校驗需要添加元素的位置是否合法，不合法則抛出索引越界異常

2、将集合轉為數組

3、擷取入參集合的元素數量

4、如果入參集合的元素為空，則不執行後續操作

5、擷取指定索引的前驅節點和後驅節點，目的與“在指定索引位置添加元素”一緻；

a) 如果是添加的索引位置是末尾，則前驅節點等于最後一個節點，後繼節點為空

b) 如果索引位置不是末尾，則根據索引擷取元素，并将其作為後繼節點，索引處的節點的前驅節點作為本次處理的前驅節點

6、按照在尾部添加元素的方式處理集合的元素

7、最後将集合中的最後一個元素與指定索引位置的節點連接配接

8、更新元素數量、更新修改連結清單結構的次數

代碼如下：

public boolean addAll(Collection<? extends E> c) {
    // 将入參的集合加入末尾，具體參考在指定位置添加集合
return addAll(size, c);
}
====================
  public boolean addAll(int index, Collection<? extends E> c) {
    //校驗需要添加元素的位置是否合法，不合法則抛出索引越界異常
checkPositionIndex(index);

// 将集合轉為數組
    Object[] a = c.toArray();
// 擷取入參集合的元素數量
    int numNew = a.length;
// 如果入參集合的元素為空，則不執行後續操作
    if (numNew == 0)
        return false;

// 擷取前驅節點，後繼節點
    Node<E> pred, succ;
    if (index == size) {
// 如果是添加的索引位置是末尾，則前驅節點等于最後一個節點，後繼節點為空
        succ = null;
        pred = last;
    } else {
//如果不是添加至末尾，則找到索引對應的節點，并将該節點作為後繼節點，該節點的前驅節點作為 後續的前驅節點
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
// 周遊需要添加的集合，并建立新節點，以集合中的元素為資料項，索引位置的前驅節點作為新節點的前驅節點，後繼節點為空
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果前驅節點為null，則表示索引位置是頭結點，或者連結清單為空，将頭指針指向新節點
if (pred == null)
            first = newNode;
        else
// 如果前驅節點不為空，則前驅節點的後繼節點指向新節點
            pred.next = newNode;

// 更新前驅節點為目前新節點，開啟下一輪的處理
        pred = newNode;
    }

// 處理完成之後，如果後繼節點為null，則需要将尾結點指向處理完成時的前驅節點pred（因為在處理過程中，前驅節點pred始終等于最新的一個節點）
    if (succ == null) {
        last = pred;
    } else {
// 如果後繼節點不為空，則将處理完的最後一個節點的後繼節點指向索引位置的節點，索引位置的節點的前驅節點指向處理完的最後一個節點
        pred.next = succ;
        succ.prev = pred;
    }

//更新元素數量
    size += numNew;
//更新修改集合結構的次數
    modCount++;
    return true;
}

5.4、添加元素至第一個索引的位置

添加元素至第一個索引位置的方式有兩種：addFirst(E e) 和 offerFirst(E e)；但最終都會調用linkFirst(E e)方法；是以我們将會對linkFirst進行講解和分析；linkFirst的業務邏輯過程如下：

1、擷取第一個元素

2、建立新節點，以添加的元素為資料項，後驅節點指針指向頭結點

3、頭結點指針指向目前新建立的節點

4、如果頭結點為空，則表示連結清單為空，則尾結點也指向新節點

5、如果頭結點不為空，則原頭結點的前驅節點指針指向新節點

6、連結清單的元素數量加1

7、修改連結清單結構的次數加1

添加元素至第一個索引位置的流程圖

代碼如下：

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

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
====================================
private void linkFirst(E e) {
//擷取第一個元素，
    final Node<E> f = first;
// 建立新節點，以添加的元素為資料項，頭結點作為後繼節點
    final Node<E> newNode = new Node<>(null, e, f);
    // 更新頭結點為目前節點
first = newNode;
// 如果頭結點為空，則表示連結清單為空，則尾結點也指向新節點
    if (f == null)
        last = newNode;
    else
// 如果頭結點不為空，則原頭結點的前驅節點更新為新節點
        f.prev = newNode;
// 連結清單的元素數量加1
    size++;
// 修改連結清單結構的次數加1
    modCount++;
}

總結

關于LinkedList的分析就結束了，更多的内容将會在後續的文章中進行分享；

輕松解讀源碼系列之Java集合LinkedList（上）

1、LinkedList介紹

2、LinkedList底層結構分析

3、LinkedList構造函數

4、LinkedList添加元素方法說明

隊列接口的方法

清單接口的方法

5、LinkedList添加元素方法源碼解析

5.1、在末尾追加元素

5.2、在指定位置添加元素

5.3、添加集合

5.4、添加元素至第一個索引的位置

總結

繼續閱讀

Ambry：LinkedIn開源的可擴充分布式對象存儲系統

JUC - BlockingQueue

從源碼全面解析LinkedBlockingQueue的來龍去脈

一個新的AI聊天機器人PI誕生了，對話十分流暢自然，支援語音輸出，UI設計很優雅，将機器人的思考展現在了輸出動畫裡。支援

ArrayList和LinkedList怎麼選，想過嗎？

從 LinkedIn 到 TikTok：新移民如何利用社交媒體在加拿大取得成功

Linkedin要離開中國了做外貿的同行有想法嗎？好像前年開始，國内版本隻作為職場内容，但是越獄還是可以使用，不知道八月

怎麼給領英群組(LinkedIn Group)内的客戶批量發消息添加好友？

Win11預覽版LinkedIn應用上架微軟商城

從Linkedin案例學習怎樣培養人脈，從“弱關系”到“強關系”

外貿&職場-工具&黑科技10000+#外貿#Google#高效辦公#新客戶開發#Linkedin

1900名全球高管、86頁幹貨：LinkedIn釋出B2B營銷基準報告

綠色生态可持續：LinkedIn領英活力動态的混合園區總部設計

Java LinkedList 雙向連結清單實作原理

WhatsAPP找客戶給大家推薦一個超好用的工具，Linkedln，Facebook，GoogleInstagram等9

LeetCode-Linked List Cycle II