????????在 Java 的集合框架中，LinkedList是一個獨特且常用的成員。它基于雙向鏈表實現，與數組結構的集合類如ArrayList有著顯著差異。深入探究LinkedList的底層源碼，有助于我們更好地理解其工作原理和性能特點，以便在實際開發中做出更合適的選擇。
????????這里如何具體在idea里查看底層源碼的教程在我ArrayList那篇文章有，基本大差不差，具體步驟我就不再演示了，我直接把所有底層源碼總結下來供大家參考。
咱們可以根據這個代碼邏輯自己推一下，捋清楚了思路就好理解多了。
一、基本結構與成員變量
LinkedList的底層核心是一個雙向鏈表，其內部通過節點來存儲數據。以下是LinkedList源碼中關鍵的成員變量定義：
// 頭節點
transient Node<E> first;
// 尾節點
transient Node<E> last;
// 元素數量
transient int size = 0;
// 底層雙向鏈表節點的內部類
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;}
}
first和last分別指向雙向鏈表的頭節點和尾節點，通過它們可以方便地對鏈表進行遍歷和操作。size變量用于記錄鏈表中元素的個數。Node內部類則定義了鏈表節點的結構，每個節點不僅存儲了元素值item，還持有指向前驅節點prev和后繼節點next的引用，這使得雙向鏈表能夠靈活地在兩個方向上進行遍歷和元素的插入、刪除等操作。
二、構造函數剖析
無參構造函數
public LinkedList() {
}
無參構造函數非常簡潔，它只是創建了一個空的LinkedList對象。此時，first和last都為null，size為 0，鏈表中沒有任何元素。
帶集合參數的構造函數
public LinkedList(Collection<? extends E> c) {this();addAll(c);
}
該構造函數先調用無參構造函數創建一個空鏈表，然后通過addAll方法將傳入集合中的所有元素添加到新創建的LinkedList中。這為我們在初始化LinkedList時提供了一種便捷的方式，可以直接將其他集合中的元素導入進來。
三、元素添加操作
在鏈表尾部添加元素
add(E e)方法用于在鏈表尾部添加一個元素，它是LinkedList中最常用的添加元素的方式之一。
public boolean add(E e) {linkLast(e);return true;
}
void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;
}
add(E e)方法內部調用了linkLast方法。linkLast方法首先記錄原鏈表的尾節點l，然后創建一個新的節點newNode，使其前驅指向原尾節點l，后繼為null。接著更新last指向新節點，如果原尾節點為空，說明鏈表之前是空的，此時first也指向新節點；否則將原尾節點的后繼指向新節點。最后，更新元素數量size和修改次數modCount。這個過程使得在鏈表尾部添加元素的操作非常高效，時間復雜度為 O (1)。
在指定位置插入元素
add(int index, E element)方法可以在鏈表的指定位置插入一個元素。
public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));
}
該方法首先調用checkPositionIndex方法檢查索引是否越界（要求0 <= index <= size）。如果索引等于size，說明要在鏈表尾部插入元素，直接調用linkLast方法即可；否則，調用linkBefore方法在指定節點前插入元素。這里的node(index)方法用于獲取指定索引位置的節點：
Node<E> node(int 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;}
}
node(index)方法通過判斷索引與鏈表長度一半的大小關系，決定從鏈表頭部還是尾部開始遍歷查找指定索引位置的節點。如果索引小于鏈表長度的一半，從鏈表頭部開始遍歷；否則從鏈表尾部開始遍歷。這種優化策略可以減少遍歷的節點數量，提高查找效率。
四、元素刪除操作
移除指定位置的元素
remove(int index)方法用于移除鏈表中指定位置的元素。
public E remove(int index) {checkElementIndex(index);return unlink(node(index));
}
該方法先調用checkElementIndex方法檢查索引是否越界（要求0 <= index < size），然后通過node(index)方法獲取指定索引位置的節點，最后調用unlink方法移除該節點并返回其存儲的元素。
E unlink(Node<E> x) {final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;
}
unlink方法通過調整節點之間的引用關系，將指定節點從鏈表中移除。它先保存要移除節點的元素值、后繼節點和前驅節點，然后根據前驅和后繼節點的情況更新鏈表的頭節點first或尾節點last，以及相關節點的前驅和后繼引用。最后將被移除節點的元素值置為null，更新元素數量size和修改次數modCount，并返回被移除的元素。
移除指定元素的第一個匹配項
remove(Object o)方法用于移除鏈表中指定元素的第一個匹配項。
public boolean remove(Object o) {if (o == null) {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;
}
該方法通過遍歷鏈表，分別處理要移除的元素為null和不為null的情況。找到匹配的元素后，調用unlink方法將其移除并返回true；如果遍歷完鏈表都沒有找到匹配元素，則返回false。
五、元素查找操作
查找指定元素首次出現的索引
indexOf(Object o)方法用于返回指定元素在鏈表中首次出現的索引，如果不存在則返回 -1。
public int indexOf(Object o) {int index = 0;if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;
}
該方法從鏈表頭部開始遍歷，分別處理查找元素為null和不為null的情況，找到匹配元素時返回其索引，遍歷完鏈表都未找到則返回 -1。
查找指定元素最后一次出現的索引
lastIndexOf(Object o)方法用于返回指定元素在鏈表中最后一次出現的索引，如果不存在則返回 -1。
public int lastIndexOf(Object o) {int index = size;if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else {for (Node<E> x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}return -1;
}
該方法從鏈表尾部開始遍歷，分別處理查找元素為null和不為null的情況，找到匹配元素時返回其索引，遍歷完鏈表都未找到則返回 -1。
通過對LinkedList底層源碼的剖析，我們清楚地了解了它的結構和各種操作的實現原理。LinkedList在插入和刪除元素時具有高效性，尤其是在鏈表中間位置進行操作時，不需要像ArrayList那樣進行大量元素的移動。然而，由于其基于鏈表結構，隨機訪問元素的時間復雜度較高，需要遍歷鏈表來查找指定位置的元素。因此，在實際開發中，我們應根據具體的需求和操作場景，合理選擇使用LinkedList或其他集合類，以達到最佳的性能和功能實現。
