【Java集合】LinkedList源碼深度分析

參考筆記：java LinkedList 源碼分析（通俗易懂)_linkedlist源碼分析-CSDN博客

1.前言

2.LinkedList簡介

3.LinkedList的底層實現

4.LinkedList 與 ArrayList 的對比

4.1 如何選擇

4.2 對比圖

5.LinkedList 源碼Debug

5.1 add(E e)

????????（1）跳入無參構造

????????（2）跳入add方法

????????（3）跳入linkLast方法

????????（4）增加第一個元素成功?

????????（5）向鏈表中添加第二個元素

5.2 remove()

????????（1）準備工作

????????（2）跳入remove()方法

????????（3）跳入removeFirst()方法

????????（4）跳入unlinkFirst()方法

????????（5）第一個結點被刪除

1.前言

? ? ? ? ?本文是對單列集合 List 的實現類之一 LinkedList 的源碼解析。對于單列集合 List 的三個最常用的實現類—— ArrayList, Vector, LinkedList ，我對 ArrayList、Vector 的源碼解讀在另外兩篇文章，感興趣的話可以看看：

【Java集合】ArrayList源碼深度分析-CSDN博客https://blog.csdn.net/m0_55908255/article/details/146886585【Java集合】Vector源碼深度分析-CSDN博客https://blog.csdn.net/m0_55908255/article/details/146949740????????注意 :?本文對 LinkedList?源碼的解讀基于主流的?JDK 8.0?的版本

2.LinkedList簡介

①?LinkedList 是一種常見的線性表，每一個結點中都存放了下一個結點的地址。 LinkedList 類位于 java.lang.LinkedList 下，其類定義和繼承關系圖如下：

②??鏈表可分為單向鏈表和雙向鏈表

? ??? ? 單項鏈表的每個結點：包含兩個值——當前結點的值、下一個結點的地址值(以指向后一個結點)

? ? ? ??雙向鏈表的每個結點：包含三個值——前一個結點的地址值(以指向前一個結點)、當前結點的值、下一個結點的地址值(以指向后一個結點)

③??LinkedList 底層實現了雙向鏈表和雙端隊列的特點

④?同 ArrayList、Vector 類似，可以向 LinkedList 集合中添加任意元素，包括 null，并且元素允許重復

⑤?同 ArrayList 一樣，LinkedList?也沒有實現線程同步，因此?LinkedList 線程不安全

3.LinkedList的底層實現

① LinkedList 的底層維護了一個雙向鏈表。?LinkedList 類中維護了 first、last 屬性，見名知意，它們分別指向雙向鏈表的首結點和尾結點。其在源碼中的定義如下：

②? 鏈表中的每個結點（ Node 對象）中又維護了?prev，next，item 三個屬性，item 存放當前節點的值。通過 prev 指向前一個結點，通過 next 指向后一個結點，從而實現雙向鏈表。此處的 Node<E> 類型，實際上是 LinkedList?類中維護的一個靜態內部類，如下圖所示 :?

③?LinkedList 中元素的添加和刪除，在底層不是通過數組來完成的，而是通過鏈表來完成。因此 LinkedList 相對來說增刪的效率更高

補充：為什么鏈表的增刪效率比數組高？

相信學過數據結構的同學都知道，這里我簡單提一下。數組如果刪除中間的某一個元素可能需要挪動大量的數據，增加亦是如此。而鏈表只需要修改所刪除節點的前后節點的 next、prev 即可，比較方便

④??雙向鏈表的示意圖如下 : (注意箭頭是指向結點整體)

這里我用 Java 來模擬一個簡單的雙向鏈表，現在創建三個《誅仙》人物對象——陸雪琪、張小凡、小環，并且讓他們形成如下的雙向鏈表關系：?

代碼如下：

public class demo {public static void main(String[] args) {//演示 : 用java模擬一個簡單的雙向鏈表//創建誅仙人物對象Node luxueqi = new Node("陸雪琪");        //第一個結點Node zhangxiaofan = new Node("張小凡");   //第二個結點Node xiaohuan = new Node("小環");       //第三個結點//完成雙向鏈表//從左往右相連接luxueqi.next = zhangxiaofan;zhangxiaofan.next = xiaohuan;//從右往左相連接xiaohuan.prev= zhangxiaofan;zhangxiaofan.prev= luxueqi;//令first指向第一個結點，令last指向最后一個結點Node first = luxueqi;Node last = xiaohuan;//遍歷鏈表（頭 ——> 尾）System.out.println("從頭-->尾");while (true) {if (first == null) {break;}System.out.println(first);      //輸出當前對象的信息first = first.next;             //更改指向}System.out.println("=====================================");//遍歷鏈表（尾 ——> 頭）System.out.println("從尾-->頭");while (true) {if (last == null) {break;}System.out.println(last);       //輸出當前對象的信息last = last.prev;                //更改指向}}
}//自定義Node結點
class Node {public Object item;     //存放當前結點的數據public Node prev;       //指向前一個結點public Node next;       //指向后一個結點public Node(Object name) {this.item = name;}public String toString() {return "Node 's name = " + item;}
}

運行結果：

4.LinkedList 與 ArrayList 的對比

4.1 如何選擇

①?增刪操作多，優先選擇 LinkedList ；改查操作多，優先選擇 ArrayList

②?實際開發中，往往對集合的改查操作比較多，因此 ArrayList 一般用的較多

③?根據實際業務需求來選擇

④?ArrayList 與 LinkedList 線程均不安全，建議單線程情況下使用

4.2 對比圖

5.LinkedList 源碼Debug

5.1 add(E e)

用以下代碼為演示，進行?Debug?操作：

import java.util.LinkedList;
public class demo {public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add(11);linkedList.add(141);System.out.println(linkedList);}
}

????????（1）跳入無參構造

? ? ? ? 如下圖所示：

????????可以看到， LinkedList 類的無參構造其實什么也沒有做，這里只會利用隱藏的 super() 調用父類的無參構造器。因為它底層使用鏈表實現的，所以不需要創建數組

? ? ? ? 直接跳出無參構造，可以看到 LinkedList 對象已經初始化完畢， LinkedList 維護的 first、last 屬性經過了默認初始化 ---> 顯式初始化 ---> 構造器初始化，最后仍為默認值 null，如下圖所示 :

????????此時 first 和 last 均為 null。所以，鏈表此時的結構如下圖所示：

????????（2）跳入add方法

? ? ? ? ?由于我們向鏈表中添加的元素為 int 類型，所以跳入 add 方法之前會進行自動裝箱 int ---> Integer，如下圖所示：

? ? ? ? 自動裝箱結束后，跳入 add 方法，如下圖所示：

????????形參列表的 "e" 表示我們當前要添加的元素，所以此時 e = 11 。 add 方法中調用了 linkLast 方法，在 linkLast 方法里面完成了添加元素的操作

????????（3）跳入linkLast方法

? ? ? ? 跳入 linkLast 方法，如下圖所示：

????????一步一步來看

? ? ? ? 首先，Node 是"結點"的意思，就是 Node<E> 類型

? ? ? ? 其次，本文上面提到說——此時 first == null，last == null。所以，linkLast 方法內，第一步是定義了一個 Node 類型的常指針? $\color{red}l$ ，并令其指向為 last，所以此時? $\color{red}l=last=null$

????????接著，又定義了一個 Node 類型的常量 newNode 。見名知意，"newNode" 就是我們要添加的新結點。那么，為 newNode 初始化的這個帶參構造 new Node<>(l，e，null) 是怎么執行的呢？這三個實參分別是干嘛的？

????????我們追入這個帶參構造看個究竟：

? ? ? ? 可以看到，構造器的三個形參就是 Node 對象的三個屬性。所以，對應此處的三個實參， $\color{red}l$ ?就是 prev，此時為 null ；e 就是已經裝箱好的 11 ；null 就是 next 的值

????????因此， newNode 引用此時指向的就是一個前后結點均為空，值為 11 的新結點

? ? ? ? 執行完帶參構造，就是?last = newNode，即又令 last 指向了添加的新結點，使得 last 始終指向鏈表中的最后一個結點，這是典型的鏈表尾插法

????????繼續向下執行，是一個 if-else 的復合條件語句。判斷條件 "l == null" 顯然滿足，令 first 也指向了該新結點；之后，又令 size 自增 1?(size表示當前鏈表中結點的個數)，modCount 也自增 1（modCount表示鏈表的修改次數)

????????（4）增加第一個元素成功?

? ? ? ? linkLast 執行完畢后，此時的鏈表結構如下圖所示：

????????接下來，我們可以逐層跳出直到演示類中驗證一下上面的鏈表結構圖是否正確。此時鏈表的狀態，如下圖所示：

????????可以看到，first 和 last 確實是指向了同一個結點，并且該結點中 prev = null，next = null，item = 11??

????????（5）向鏈表中添加第二個元素

????????向鏈表中添加第?2 個元素，前面幾個步驟都一樣，這里就不再贅述了，直接從 linkLast 方法開始說起，如下 :??

????????還是一步一步來看

????????首先，令 Node 類型的常指針? $\color{red}l$ ?指向了 last 所指向的結點(即我們前面添加的第一個結點，此時它也為鏈表中的最后一個結點)

????????其次，第二個新結點 newNode 進行初始化工作。注意，第一個實參? $\color{red}l$ ?代表的是新結點的prev，而? $\color{red}l$ ?此時指向的是第一個結點，因此，這一步實現了——令新節點 newNode 的 prev 指向了第一個結點

????????接著，執行完帶參構造，就是?last = newNode，即又令 last 指向了添加的新結點 newNode ，使得 last 始終指向鏈表中的最后一個結點，這是典型的鏈表尾插法

? ? ? ? 之后，就是 if-else 的判斷語句了，此時? $\color{red}l$ ?指向的是鏈表中的第一個結點，不為空，所以執行 else 中的語句，l.next = newNode，令第一個結點的 next 指向了新結點?

????????最后，就是更新 size 、modCount

? ? ? ? 綜上，第二次 linkLast 方法執行完畢后，鏈表結構如下圖所示：

🆗，以上就是 LinkedList 的 add(E e) 方法源碼分析

5.2 remove()

LinkedList 類的 remove 有三個重載方法：

①?remove( )：刪除鏈表的第一個結點

②?remove(int index)：刪除鏈表中第 index-1 個結點

③?remove(Object o)：刪除鏈表中與 o 值匹配的第一個結點

????????（1）準備工作

????????用以下代碼演示 remove() ，進行?Debug?操作：

import java.util.LinkedList;
public class demo {public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add(11);linkedList.add(141);linkedList.add(5);System.out.println("添加三個元素后，當前鏈表 = " + linkedList);linkedList.remove();System.out.println("刪除第一個元素后，當前鏈表 = " + linkedList);}
}

????????運行結果：?