在 Java 集合框架中，LinkedList 與 ArrayList 是兩種截然不同的線性表實現。如果說 ArrayList 像一個可以伸縮的“盒子陣列”，那么 LinkedList 就像一條由“節點”串聯而成的“雙向鏈條”。
今天，我們將深入 LinkedList 的源碼，一步步剖析它作為雙向鏈表的精妙設計。通過這篇解析，你將徹底明白 LinkedList 是如何通過 first 和 last 指針，高效地管理元素的。
一、LinkedList?的誕生：空鏈的起點
當我們執行 new LinkedList<>() 時，LinkedList 在底層做了什么？
// 代碼塊
LinkedList<String> list = new LinkedList<>();核心真相：此時，LinkedList 并沒有創建任何節點。它只初始化了兩個至關重要的指針（引用）：
first：指向鏈表的頭節點（第一個節點）。last：指向鏈表的尾節點（最后一個節點）。
在創建之初，鏈表為空，因此 first 和 last 都被初始化為 null。
// 代碼塊
// LinkedList 源碼中的定義
transient Node<E> first;
transient Node<E> last;二、成長的第一步：添加第一個元素
當我們調用 list.add("Hello") 時，發生了什么？
- 創建新節點：
LinkedList?會創建一個全新的?Node?對象。這個節點的結構非常簡單，包含三部分：item：存儲元素?"Hello"。next：指向下一個節點的引用。prev：指向前一個節點的引用。
- 初始化節點：由于這是第一個節點，它的?
prev?和?next?都指向?null。 - 更新指針：
first?和?last?這兩個指針，都指向這個新創建的節點。因為此時，這個節點既是頭節點，也是尾節點。
// 代碼塊
// Node 類的定義 (簡化)
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;}
}此時，LinkedList 的內部結構如下圖所示：
三、鏈的延伸：添加第二個元素
當我們調用 list.add("World") 時，鏈表開始延伸。
- 創建新節點：創建一個新的?
Node?對象，存儲元素?"World"。 - 建立連接：
- 前向連接：第一個節點（當前的?
last）的?next?指針，將指向這個新節點。 - 后向連接：新節點的?
prev?指針，將指向第一個節點。
- 前向連接：第一個節點（當前的?
- 更新尾指針：
last?指針不再指向第一個節點，而是更新為指向這個新創建的節點。first?指針保持不變，仍然指向第一個節點。
此時，鏈表的結構變成了：
first -> [item: "Hello", prev: null, next: ->] <-> [item: "World", prev: <-, next: null] <- last四、雙向鏈表的魅力：高效的操作
LinkedList 的雙向鏈表結構賦予了它獨特的優勢：
1.?頭尾操作的極致效率
addFirst()?/?addLast()：由于?first?和?last?指針的存在，向鏈表頭部或尾部添加元素的時間復雜度都是?O(1)。removeFirst()?/?removeLast()：同理，刪除頭尾元素也是?O(1)。
2.?中間插入/刪除的“局部性”
- 在鏈表中間插入或刪除元素，雖然需要先通過遍歷找到位置（O(n)），但一旦找到，實際的插入/刪除操作本身是 O(1)?的，因為它只需要修改相鄰節點的指針，而不需要像?
ArrayList?那樣移動大量元素。
3.?內存的“按需分配”
- 與?
ArrayList?預先分配數組不同，LinkedList?的每個節點都是在需要時才創建，內存使用更“靈活”，但每個節點有額外的?prev?和?next?引用開銷。
最終效果：
五、總結：LinkedList?的設計哲學
通過這次源碼級的剖析，我們可以總結出 LinkedList 的核心工作原理：
| 階段 | 關鍵動作 | 指針變化 |
|---|---|---|
| 創建 | 初始化?first?和?last?指針 | first = null,?last = null |
| 首次添加 | 創建節點，first?和?last?都指向它 | first -> Node1,?last -> Node1 |
| 后續添加 | 創建新節點，修改相鄰節點指針，更新?last | Node1.next -> Node2,?Node2.prev -> Node1,?last -> Node2 |
LinkedList 的“動態”源于其節點化和指針鏈接的設計。它用 first 和 last 兩個指針高效地管理鏈表的兩端，用 prev 和 next 構建了雙向的連接，使得頭尾操作異常迅速。
何時選擇 LinkedList？
- 頻繁在列表的頭部或尾部進行插入/刪除操作。
- 需要實現棧（Stack）?或?隊列（Queue）?的數據結構（
LinkedList?實現了?Deque?接口）。
何時避免 LinkedList？
- 需要頻繁進行隨機訪問（
get(index)），因為需要從頭或尾遍歷。 - 內存非常緊張，因為每個節點有額外的引用開銷。
理解了 LinkedList 的雙向鏈表本質，你就能在 ArrayList 和 LinkedList 之間做出更明智的選擇。
希望這篇解析能幫你徹底掌握 LinkedList 的源碼精髓！
)
