大家好，我是栗箏i，這篇文章是我的 “栗箏i 的 Java 技術?！?專欄的第 014 篇文章，在 “栗箏i 的 Java 技術棧” 這個專欄中我會持續(xù)為大家更新 Java 技術相關全套技術棧內(nèi)容。專欄的主要目標是已經(jīng)有一定 Java 開發(fā)經(jīng)驗，并希望進一步完善自己對整個 Java 技術體系來充實自己的技術棧的同學。與此同時，本專欄的所有文章，也都會準備充足的代碼示例和完善的知識點梳理，因此也十分適合零基礎的小白和要準備工作面試的同學學習。當然，我也會在必要的時候進行相關技術深度的技術解讀，相信即使是擁有多年 Java 開發(fā)經(jīng)驗的從業(yè)者和大佬們也會有所收獲并找到樂趣。

–

Java 集合框架中包含了多種用于數(shù)據(jù)存儲和操作的類，其中 LinkedList 是一個重要且常用的實現(xiàn)。LinkedList 作為一個雙向鏈表，提供了高效的插入和刪除操作，特別適用于頻繁進行元素增刪的場景。對于很多開發(fā)者而言，深入理解 LinkedList 的特性和工作原理是提高代碼性能和優(yōu)化數(shù)據(jù)處理邏輯的關鍵。本文將對 LinkedList 進行全面的介紹和解析，幫助讀者掌握其使用方法、內(nèi)部原理以及源碼實現(xiàn)。

---

---

1、LinkedList 概述

LinkedList 是 List 接口的一個實現(xiàn)，它是一個雙向鏈表。與 ArrayList 相比，LinkedList 的元素在內(nèi)存中不是連續(xù)存放的。每個元素（稱為節(jié)點）都包含兩部分數(shù)據(jù)：一部分是存儲的數(shù)據(jù)，另一部分是指向前一個節(jié)點和后一個節(jié)點的鏈接（指針）。

LinkedList 的優(yōu)點在于插入和刪除元素時效率很高。因為鏈表的數(shù)據(jù)結(jié)構(gòu)使得它只需要修改前后節(jié)點的指針即可，而不需要像 ArrayList 那樣移動其他元素。因此，LinkedList 適合用在需要頻繁執(zhí)行添加和刪除操作的場景。

然而，LinkedList 的隨機訪問效率不高，每次查找某個元素都需要從頭開始遍歷鏈表直到找到目標元素。這使得 LinkedList 在執(zhí)行隨機訪問操作時速度較慢，不如 ArrayList。

在 Java 中，LinkedList 除了實現(xiàn) List 接口外，還實現(xiàn)了 Deque 接口，這意味著它還可以被當作隊列（Queue）、雙端隊列（Deque）使用，提供了更加豐富的方法，如 addFirst(), addLast(), removeFirst(), removeLast() 等。

LinkedList 也是非線程安全的。如果在多線程環(huán)境中使用，需要外部同步或者考慮使用 java.util.concurrent 包中的線程安全類，如 LinkedBlockingDeque 等。

總的來說，LinkedList 由于其結(jié)構(gòu)的特點，適合于數(shù)據(jù)量不大但插入和刪除操作頻繁的場景，而不適合大量的隨機訪問操作。

---

2、LinkedList 的具體實現(xiàn)原理

2.1、LinkedList 底層的數(shù)據(jù)結(jié)構(gòu)

LinkedList 是基于鏈表數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，它包含一系列的節(jié)點（Node），每個節(jié)點包括三個部分：前一個節(jié)點的引用（previous），儲存的元素（data），和下一個節(jié)點的引用（next）。這種數(shù)據(jù)結(jié)構(gòu)支持高效的元素插入和刪除操作。

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{transient int size = 0;// 鏈表中元素的數(shù)量transient int size = 0;/*** 指向第一個節(jié)點的指針*/transient Node<E> first;/*** 指向最后一個節(jié)點的指針*/transient Node<E> last;/*** 構(gòu)造一個空的鏈表*/public LinkedList() {}/*** 構(gòu)造一個包含指定集合元素的鏈表，這些元素按集合的迭代器返回的順序排列。** @param  c 要放入鏈表中的集合* @throws NullPointerException 如果指定的集合為 null*/public LinkedList(Collection<? extends E> c) {this();// 將集合中的所有元素添加到鏈表中addAll(c);}// 省略其他方法和實現(xiàn)細節(jié).../*** Node 是一個私有的靜態(tài)內(nèi)部類，用于表示 LinkedList 中的每個節(jié)點** @param <E>*/private static class Node<E> {// 節(jié)點存儲的元素E item;// 指向下一個節(jié)點的引用Node<E> next;// 指向前一個節(jié)點的引用Node<E> prev;/*** 構(gòu)造方法，創(chuàng)建一個新的節(jié)點** @param prev    該節(jié)點的前一個節(jié)點* @param element 該節(jié)點存儲的元素* @param next    該節(jié)點的后一個節(jié)點*/Node(Node<E> prev, E element, Node<E> next) {// 設置節(jié)點存儲的元素this.item = element;// 設置指向下一個節(jié)點的引用this.next = next;// 設置指向前一個節(jié)點的引用this.prev = prev;}}// 省略其他方法和實現(xiàn)細節(jié)...
}

2.2、LinkedList 增刪改查的實現(xiàn)

2.2.1、LinkedList 的插入

LinkedList 的插入的實現(xiàn)并不復雜，其插入式，主要會有兩種場景，一種是在鏈表的末尾插入，另一種是在指定節(jié)點之前插入一個新節(jié)點，二者的實現(xiàn)都是通過創(chuàng)建一個新節(jié)點并更新其前驅(qū)和后繼節(jié)點的引用，唯一的區(qū)別就是，linkBefore 是在指定節(jié)點之后插入該新節(jié)點，而 linkAfter 是在指定節(jié)點之后插入該新節(jié)點。

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 省略其他方法和實現(xiàn)細節(jié).../*** 在鏈表末尾添加一個元素** @param e 要添加的元素* @return 總是返回 true*/@Overridepublic boolean add(E e) {// 在鏈表末尾鏈接一個新的節(jié)點linkLast(e);return true;}/*** 在鏈表末尾鏈接一個新的節(jié)點** @param e 新節(jié)點存儲的元素*/void linkLast(E e) {// 保存當前鏈表的最后一個節(jié)點final Node<E> l = last;// 創(chuàng)建一個新的節(jié)點，前驅(qū)節(jié)點是當前最后一個節(jié)點，后繼節(jié)點是 nullfinal Node<E> newNode = new Node<>(l, e, null);// 將鏈表的最后一個節(jié)點更新為新節(jié)點last = newNode;if (l == null)// 如果鏈表之前是空的，即沒有任何元素// 將新節(jié)點設置為鏈表的第一個節(jié)點first = newNode;else// 如果鏈表中已有元素// 將原最后一個節(jié)點的 next 指針指向新節(jié)點l.next = newNode;// 鏈表大小增加 1size++;  }/*** 在指定索引處插入元素** @param index 要插入元素的位置* @param element 要插入的元素*/public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}/*** 在指定節(jié)點之前插入一個新節(jié)點** @param e 新節(jié)點存儲的元素* @param succ 指定的節(jié)點，新節(jié)點將插入在其之前*/void linkBefore(E e, Node<E> succ) {// assert succ != null;  // 確保 succ 不為 null，確保在調(diào)用該方法前 succ 一定存在// 保存指定節(jié)點的前驅(qū)節(jié)點final Node<E> pred = succ.prev;// 創(chuàng)建一個新的節(jié)點，其前驅(qū)是 pred，后繼是 succfinal Node<E> newNode = new Node<>(pred, e, succ);// 將指定節(jié)點的前驅(qū)更新為新節(jié)點succ.prev = newNode;if (pred == null)// 如果 pred 為 null，說明 succ 是第一個節(jié)點// 將新節(jié)點設置為鏈表的第一個節(jié)點first = newNode;else// 如果 pred 不為 null，說明 succ 不是第一個節(jié)點// 將 pred 的后繼節(jié)點更新為新節(jié)點pred.next = newNode;// 鏈表大小增加 1size++;// 修改計數(shù)器增加 1，用于快速失敗機制modCount++;  }// 省略其他方法和實現(xiàn)細節(jié)...
}

此外，另一個十分值得注意的點是，add(int index, E element) 在調(diào)用指定節(jié)點之前插入一個新節(jié)點方法時，調(diào)用了 node(int index) 方法來返回指定索引處的節(jié)點。該方法可以看作是 LinkedList 的核心實現(xiàn)之一，除插入方法之外，LinkedList 在查詢、刪除、修改等方法除也需要調(diào)用當前方法：

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 省略其他方法和實現(xiàn)細節(jié).../*** 返回指定索引處的節(jié)點。** @param index 要獲取節(jié)點的位置* @return 指定索引處的節(jié)點*/Node<E> node(int index) {// assert isElementIndex(index);  // 確保索引在有效范圍內(nèi)// 判斷索引是否在鏈表的前半部分if (index < (size >> 1)) {// 從鏈表的第一個節(jié)點開始遍歷Node<E> x = first;// 遍歷到指定索引位置for (int i = 0; i < index; i++)// 依次移動到下一個節(jié)點x = x.next;// 返回找到的節(jié)點return x;} else {// 索引在鏈表的后半部分Node<E> x = last;// 從鏈表的最后一個節(jié)點開始遍歷for (int i = size - 1; i > index; i--)// 依次移動到前一個節(jié)點x = x.prev;// 返回找到的節(jié)點return x;}}// 省略其他方法和實現(xiàn)細節(jié)...
}

2.2.2、LinkedList 的刪除

LinkedList 的刪除的實現(xiàn)同樣十分簡單，是使用 unlink 方法，即通過更新前驅(qū)和后繼節(jié)點的引用，移除指定節(jié)點并返回其存儲的元素實現(xiàn)的。

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 省略其他方法和實現(xiàn)細節(jié).../*** 解除并移除指定節(jié)點。** @param x 要移除的節(jié)點* @return 被移除節(jié)點存儲的元素*/E unlink(Node<E> x) {// assert x != null;  // 確保 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) {// 如果前驅(qū)節(jié)點為 null，說明 x 是第一個節(jié)點// 將鏈表的第一個節(jié)點更新為 x 的后繼節(jié)點first = next;} else {// 如果前驅(qū)節(jié)點不為 null// 將前驅(qū)節(jié)點的后繼更新為 x 的后繼節(jié)點prev.next = next;// 將 x 的前驅(qū)設為 null，幫助垃圾回收x.prev = null;}if (next == null) {// 如果后繼節(jié)點為 null，說明 x 是最后一個節(jié)點// 將鏈表的最后一個節(jié)點更新為 x 的前驅(qū)節(jié)點last = prev;} else {// 如果后繼節(jié)點不為 null// 將后繼節(jié)點的前驅(qū)更新為 x 的前驅(qū)節(jié)點next.prev = prev;// 將 x 的后繼設為 null，幫助垃圾回收x.next = null;}// 將 x 中的元素設為 null，幫助垃圾回收x.item = null;// 鏈表大小減 1size--;// 修改計數(shù)器增加 1，用于快速失敗機制modCount++;// 返回被移除節(jié)點中的元素return element;}/*** 移除指定索引處的元素。** @param index 要移除元素的位置* @return 被移除的元素*/public E remove(int index) {checkElementIndex(index);return unlink(node(index));}/*** 從鏈表中移除第一次出現(xiàn)的指定元素（如果存在）。* 如果列表不包含該元素，則不做改變。** @param o 要移除的元素* @return 如果列表包含指定元素并移除成功則返回 true，否則返回 false*/public boolean remove(Object o) {// 如果要移除的元素為 nullif (o == null) { for (Node<E> x = first; x != null; x = x.next) {// 從鏈表的第一個節(jié)點開始遍歷if (x.item == null) {// 如果當前節(jié)點的元素為 nullunlink(x);  // 解除并移除當前節(jié)點// 返回 true，表示移除成功return true;  }}} else {  // 如果要移除的元素不為 nullfor (Node<E> x = first; x != null; x = x.next) {  // 從鏈表的第一個節(jié)點開始遍歷// 如果當前節(jié)點的元素等于要移除的元素if (o.equals(x.item)) {// 解除并移除當前節(jié)點unlink(x);// 返回 true，表示移除成功return true;  }}}// 如果沒有找到要移除的元素，返回 falsereturn false;  }// 省略其他方法和實現(xiàn)細節(jié)...
}

2.2.3、LinkedList 的修改

LinkedList 對于修改的則是通過找到原位置的 Node 并修改其 item 值實現(xiàn)的。

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 省略其他方法和實現(xiàn)細節(jié).../*** 替換指定索引處的元素，并返回被替換的元素。** @param index 要替換元素的位置* @param element 要設置的新元素* @return 被替換的舊元素* @throws IndexOutOfBoundsException 如果索引超出范圍*/public E set(int index, E element) {// 檢查索引是否在范圍內(nèi)checkElementIndex(index);// 獲取指定索引處的節(jié)點Node<E> x = node(index);// 保存當前節(jié)點的舊元素E oldVal = x.item;// 將節(jié)點的元素設置為新元素x.item = element;// 返回被替換的舊元素return oldVal;}/*** 將迭代器返回的最后一個元素替換為指定的元素。** @param e 要設置的新元素* @throws IllegalStateException 如果沒有調(diào)用 next() 或 previous() 方法*/public void set(E e) {if (lastReturned == null)// 如果 lastReturned 為 null，表示未調(diào)用 next() 或 previous()// 拋出非法狀態(tài)異常throw new IllegalStateException();// 檢查是否發(fā)生并發(fā)修改checkForComodification();// 將 lastReturned 節(jié)點的元素設置為新元素 elastReturned.item = e;}// 省略其他方法和實現(xiàn)細節(jié)...
}

2.2.4、LinkedList 的查詢

LinkedList 的查詢即獲取指定索引處的元素。它的實現(xiàn)同前面的其他方法獲取索引處元素一樣，依賴 node(int index) 方法。

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 省略其他方法和實現(xiàn)細節(jié).../*** 獲取指定索引處的元素** @param index 要獲取元素的位置* @return 指定索引處的元素*/public E get(int index) {checkElementIndex(index);return node(index).item;}/*** 返回指定索引處的節(jié)點。** @param index 要獲取節(jié)點的位置* @return 指定索引處的節(jié)點*/Node<E> node(int index) {// assert isElementIndex(index);  // 確保索引在有效范圍內(nèi)// 判斷索引是否在鏈表的前半部分if (index < (size >> 1)) {// 從鏈表的第一個節(jié)點開始遍歷Node<E> x = first;// 遍歷到指定索引位置for (int i = 0; i < index; i++)// 依次移動到下一個節(jié)點x = x.next;// 返回找到的節(jié)點return x;} else {// 索引在鏈表的后半部分Node<E> x = last;// 從鏈表的最后一個節(jié)點開始遍歷for (int i = size - 1; i > index; i--)// 依次移動到前一個節(jié)點x = x.prev;// 返回找到的節(jié)點return x;}}// 省略其他方法和實現(xiàn)細節(jié)...
}

2.3、LinkedList 對鏈表結(jié)構(gòu)的實現(xiàn)

LinkedList 類實現(xiàn)了 Queue 接口，因此提供了隊列相關的方法。這些方法允許 LinkedList 作為一個雙端隊列（Deque）使用，支持在隊列的頭部和尾部進行插入和刪除操作。下面是對 LinkedList 中與 Queue 相關方法的概括說明：

• offer(E e)：將指定的元素添加到隊列的尾部并返回 true。實現(xiàn)：調(diào)用 linkLast(E e) 方法，將元素添加到鏈表的尾部；
• poll()：獲取并移除此隊列的頭部，如果隊列為空，則返回 null。實現(xiàn)：調(diào)用 unlinkFirst(Node<E> f) 方法，移除并返回鏈表的第一個元素；
• remove()：獲取并移除此隊列的頭部，如果隊列為空，則拋出 NoSuchElementException。實現(xiàn)：調(diào)用 unlinkFirst(Node<E> f) 方法，移除并返回鏈表的第一個元素。如果鏈表為空，拋出 NoSuchElementException；
• peek()：獲取但不移除此隊列的頭部；如果隊列為空，則返回 null。實現(xiàn)：返回鏈表的第一個元素 first.item，如果鏈表為空返回 null。
• element()：獲取但不移除此隊列的頭部；如果隊列為空，則拋出 NoSuchElementException。實現(xiàn)：返回鏈表的第一個元素 first.item，如果鏈表為空拋出 NoSuchElementException。

具體實現(xiàn)：

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 省略其他方法和實現(xiàn)細節(jié).../*** 將指定的元素添加到隊列的尾部。** @param e 要添加的元素* @return 添加成功返回 true*/public boolean offer(E e) {// 調(diào)用 add 方法，將元素添加到鏈表的尾部return add(e);}/*** 獲取并移除此隊列的頭部，如果隊列為空，則返回 null。** @return 隊列頭部的元素，如果隊列為空則返回 null*/public E poll() {// 保存鏈表的第一個節(jié)點final Node<E> f = first;// 如果鏈表為空返回 null，否則移除并返回第一個元素return (f == null) ? null : unlinkFirst(f);}/*** 獲取并移除此隊列的頭部，如果隊列為空，則拋出 NoSuchElementException。** @return 隊列頭部的元素* @throws NoSuchElementException 如果隊列為空*/public E remove() {// 保存鏈表的第一個節(jié)點final Node<E> f = first;// 如果鏈表為空，拋出 NoSuchElementExceptionif (f == null)throw new NoSuchElementException();// 移除并返回第一個元素return unlinkFirst(f);}/*** 獲取但不移除此隊列的頭部；如果隊列為空，則返回 null。** @return 隊列頭部的元素，如果隊列為空則返回 null*/public E peek() {// 保存鏈表的第一個節(jié)點final Node<E> f = first;// 返回第一個元素但不移除，如果鏈表為空返回 nullreturn (f == null) ? null : f.item;}/*** 獲取但不移除此隊列的頭部；如果隊列為空，則拋出 NoSuchElementException。** @return 隊列頭部的元素* @throws NoSuchElementException 如果隊列為空*/public E element() {return getFirst();}/*** 返回鏈表的第一個元素；如果鏈表為空，則拋出 NoSuchElementException。** @return 鏈表的第一個元素* @throws NoSuchElementException 如果鏈表為空*/public E getFirst() {// 保存鏈表的第一個節(jié)點final Node<E> f = first;// 如果鏈表為空，拋出 NoSuchElementExceptionif (f == null)throw new NoSuchElementException();// 返回第一個元素return f.item;}// 省略其他方法和實現(xiàn)細節(jié)...
}

內(nèi)部輔助方法，unlinkFirst(Node<E> f)：移除并返回鏈表的第一個節(jié)點。實現(xiàn)：更新鏈表的頭節(jié)點 first 為當前頭節(jié)點 f 的下一個節(jié)點 f.next，并將舊頭節(jié)點的前驅(qū)引用設為 null。

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 省略其他方法和實現(xiàn)細節(jié).../*** 移除并返回鏈表的第一個節(jié)點。** @param f 要移除的第一個節(jié)點* @return 被移除節(jié)點存儲的元素*/private E unlinkFirst(Node<E> f) {// 保存第一個節(jié)點的元素final E element = f.item;// 保存第一個節(jié)點的后繼節(jié)點final Node<E> next = f.next;// 清空第一個節(jié)點的元素f.item = null;// 清空第一個節(jié)點的后繼引用，幫助垃圾回收f.next = null;// 更新鏈表的頭節(jié)點為原頭節(jié)點的后繼節(jié)點first = next;// 如果新的頭節(jié)點為 null，說明鏈表現(xiàn)在為空if (next == null) {// 更新鏈表的尾節(jié)點為 nulllast = null;} else {// 將新的頭節(jié)點的前驅(qū)引用設為 nullnext.prev = null;}// 鏈表大小減 1size--;// 修改計數(shù)器增加 1，用于快速失敗機制modCount++;// 返回被移除的元素return element;}// 省略其他方法和實現(xiàn)細節(jié)...
}

---

3、LinkedList 相關知識點

3.1、關于 Queue 隊列

隊列（Queue）：也是一種操作受限的線性表，只允許在表的一端進行插入，而在表的另一端進行刪除。向隊列中插入元素稱為入隊或進隊；刪除元素稱為出隊或離隊。

這和我們?nèi)粘Ｉ钪械呐抨犑且恢碌?#xff0c;最早排隊的也是最早離隊的。其操作的特性是先進先出（First In First Out, FIFO），故又稱為先進先出的線性表。基本上，一個隊列就是一個先入先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)

在Java 中 Queue 接口與 List、Set 同一級別，都是繼承了 Collection 接口。LinkedList 實現(xiàn)了 Deque 接口。

3.2、關于 ArrayList 和 LinkedList 的區(qū)別

ArrayList 和 LinkedList 都是 List 接口的實現(xiàn)，但它們在內(nèi)部數(shù)據(jù)結(jié)構(gòu)和性能上有一些區(qū)別：

1. 內(nèi)部數(shù)據(jù)結(jié)構(gòu)：ArrayList 是基于動態(tài)數(shù)組實現(xiàn)的，支持隨機訪問，按索引訪問元素非常快，時間復雜度為 O(1)。LinkedList 是基于雙向鏈表實現(xiàn)的，不支持高效的隨機訪問，按索引訪問元素需要從頭（或尾）開始遍歷，時間復雜度為 O(n)。
2. 插入和刪除：ArrayList 的插入和刪除操作需要進行數(shù)組元素的移動（除非插入和刪除操作在列表末尾進行），所以插入和刪除元素的時間復雜度為 O(n)。LinkedList 的插入和刪除操作只需要改變節(jié)點的引用，所以在列表中間插入和刪除元素的時間復雜度為 O(1)（前提是已經(jīng)獲取到了要插入位置的節(jié)點）。
3. 內(nèi)存占用：ArrayList 的內(nèi)存占用相對較低，因為它只需要存儲元素數(shù)據(jù)和數(shù)組的引用。LinkedList 的內(nèi)存占用較高，因為它需要額外存儲節(jié)點之間的引用。

總的來說，ArrayList 更適合隨機訪問場景，LinkedList 更適合插入和刪除操作頻繁的場景。

3.3、算法：翻轉(zhuǎn)鏈表

假設鏈表為 1→2→3→?，我們想要把它改成 ?←1←2←3。

在遍歷鏈表時，將當前節(jié)點的 next 指針改為指向前一個節(jié)點。由于節(jié)點沒有引用其前一個節(jié)點，因此必須事先存儲其前一個節(jié)點。在更改引用之前，還需要存儲后一個節(jié)點。最后返回新的頭引用。

class Solution {/*** 反轉(zhuǎn)鏈表。** @param head 鏈表的頭節(jié)點* @return 反轉(zhuǎn)后的鏈表的頭節(jié)點*/public ListNode reverseList(ListNode head) {// 初始化前一個節(jié)點為 nullListNode prev = null;// 初始化當前節(jié)點為頭節(jié)點ListNode curr = head;// 遍歷鏈表直到當前節(jié)點為 nullwhile (curr != null) {// 保存當前節(jié)點的下一個節(jié)點ListNode next = curr.next;// 將當前節(jié)點的下一個節(jié)點指向前一個節(jié)點，完成反轉(zhuǎn)curr.next = prev;// 將前一個節(jié)點更新為當前節(jié)點prev = curr;// 將當前節(jié)點更新為下一個節(jié)點curr = next;}// 返回反轉(zhuǎn)后的鏈表頭節(jié)點return prev;}
}

---

4、LinkedList 的使用（常用方法）

下面是對 LinkedList 的常用方法和 Collections 類中的一些涉及 LinkedList 的方法進行詳細介紹：

4.1、LinkedList 的常用方法

1. add(E e)

• 功能：將元素添加到鏈表的末尾。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");

2. add(int index, E element)

• 功能：在指定位置插入元素。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add(1, "Orange"); // 將 "Orange" 插入在 "Banana" 前面

3. remove(Object o)

• 功能：刪除鏈表中首次出現(xiàn)的指定元素。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.remove("Apple");

4. remove(int index)

• 功能：刪除指定索引處的元素。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.remove(0); // 刪除 "Apple"

5. get(int index)

• 功能：返回鏈表中指定位置的元素。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
String item = list.get(0); // 獲取第一個元素 "Apple"

6. set(int index, E element)

• 功能：替換指定位置的元素，并返回舊值。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
String oldItem = list.set(0, "Orange"); // 將 "Apple" 替換為 "Orange"

7. size()

• 功能：返回鏈表中的元素數(shù)量。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
int size = list.size(); // size 為 1

8. isEmpty()

• 功能：檢查鏈表是否為空。
• 用例：

LinkedList<String> list = new LinkedList<>();
boolean empty = list.isEmpty(); // 判斷鏈表是否為空

9. clear()

• 功能：清空鏈表中的所有元素。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.clear(); // 清空鏈表

10. contains(Object o)

• 功能：檢查鏈表是否包含指定的元素。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
boolean contains = list.contains("Apple"); // 檢查是否包含 "Apple"

11. indexOf(Object o) 和 lastIndexOf(Object o)

• 功能：返回指定元素首次出現(xiàn)和最后一次出現(xiàn)的索引位置。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Apple");
int firstIndex = list.indexOf("Apple"); // 返回 0
int lastIndex = list.lastIndexOf("Apple"); // 返回 2

12. toArray()

• 功能：將鏈表中的元素轉(zhuǎn)換為數(shù)組。
• 用例：

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
Object[] array = list.toArray(); // 轉(zhuǎn)換為數(shù)組

13. addAll(Collection<? extends E> c)

• 功能：將指定集合中的所有元素添加到鏈表的尾部。
• 用例：

LinkedList<Integer> list = new LinkedList<>();
LinkedList<Integer> newElements = new LinkedList<>(Arrays.asList(1, 2, 3));
list.addAll(newElements);  // 添加多個元素

14. addAll(int index, Collection<? extends E> c)

• 功能：將指定集合中的所有元素添加到鏈表中的指定位置。
• 用例：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c"));
LinkedList<String> newElements = new LinkedList<>(Arrays.asList("x", "y"));
list.addAll(1, newElements);  // 在索引1的位置添加多個元素

15. removeAll(Collection<?> c)

• 功能：從鏈表中移除指定集合中也存在的所有元素。
• 用例：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c", "b"));
list.removeAll(Collections.singleton("b"));  // 移除所有 "b"

16. retainAll(Collection<?> c)

• 功能：僅保留鏈表中那些也包含在指定集合中的元素。
• 用例：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c"));
list.retainAll(Arrays.asList("a", "b"));  // 保留 "a" 和 "b"

17. containsAll(Collection<?> c)

• 功能：如果鏈表包含指定集合中的所有元素，則返回 true。
• 用例：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c"));
boolean contains = list.containsAll(Arrays.asList("a", "b"));  // 檢查是否包含 "a" 和 "b"

4.2、繼承自 Queue 接口的方法

1. offer(E e)

• 功能：將指定的元素添加到隊列的尾部。
• 用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");

2. poll()

• 功能：獲取并移除隊列的頭部元素，如果隊列為空，則返回 null。
• 用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");
String item = queue.poll(); // 獲取并移除 "Apple"

3. remove()

• 功能：獲取并移除隊列的頭部元素，如果隊列為空，則拋出 NoSuchElementException。
• 用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");
String item = queue.remove(); // 獲取并移除 "Apple"

4. peek()

• 功能：獲取但不移除隊列的頭部元素，如果隊列為空，則返回 null。
• 用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");
String item = queue.peek(); // 獲取但不移除 "Apple"

5. element()

• 功能：獲取但不移除隊列的頭部元素，如果隊列為空，則拋出 NoSuchElementException。
• 用例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Apple");
String item = queue.element(); // 獲取但不移除 "Apple"

4.3、Collections 類中涉及 LinkedList 的常用方法

1. sort(List<T> list)

• 功能：對鏈表進行排序（自然順序）。
• 用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(3, 1, 4, 1, 5));
Collections.sort(list); // 對鏈表排序

2. reverse(List<?> list)

• 功能：反轉(zhuǎn)鏈表中元素的順序。
• 用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3));
Collections.reverse(list); // 鏈表變?yōu)?[3, 2, 1]

3. shuffle(List<?> list)

• 功能：隨機打亂鏈表中元素的順序。
• 用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3));
Collections.shuffle(list); // 打亂鏈表元素的順序

4. binarySearch(List<? extends Comparable<? super T>> list, T key)

• 功能：在已排序的鏈表中使用二分查找法查找指定元素的索引。
• 用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
Collections.sort(list);
int index = Collections.binarySearch(list, 3); // 在鏈表中查找數(shù)字 3 的索引

5. copy(List<? super T> dest, List<? extends T> src)

• 功能：將一個鏈表中的所有元素復制到另一個鏈表中。
• 用例：

LinkedList<Integer> src = new LinkedList<>(Arrays.asList(1, 2, 3));
LinkedList<Integer> dest = new LinkedList<>(Arrays.asList(5, 6, 7, 8));
Collections.copy(dest, src); // 將 src 復制到 dest

6. fill(List<? super T> list, T obj)

• 功能：使用指定元素替換鏈表中的所有元素。
• 用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3));
Collections.fill(list, 0); // 將鏈表中的所有元素替換為 0

7. addAll(Collection<? super T> c, T... elements)

• 功能：向集合中添加多個元素。
• 用例：

LinkedList<Integer> list = new LinkedList<>();
Collections.addAll(list, 1, 2, 3, 4);  // 向鏈表中添加多個元素

8. replaceAll(List<T> list, T oldVal, T newVal)

• 功能：替換鏈表中所有的舊值為新值。
• 用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 1, 3));
Collections.replaceAll(list, 1, 99);  // 將所有1替換為99

9. frequency(Collection<?> c, Object o)

• 功能：返回指定元素在集合中出現(xiàn)的次數(shù)。
• 用例：

LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 1, 3));
int freq = Collections.frequency(list, 1);  // 計算1在鏈表中出現(xiàn)的次數(shù)

10. disjoint(Collection<?> c1, Collection<?> c2)

• 功能：如果兩個集合沒有共同的元素，則返回 true。
• 用例：

LinkedList<Integer> list1 = new LinkedList<>(Arrays.asList(1, 2, 3));
LinkedList<Integer> list2 = new LinkedList<>(Arrays.asList(4, 5, 6));
boolean isDisjoint = Collections.disjoint(list1, list2);  // 檢查兩個鏈表是否沒有共同元素

通過以上方法，可以對 LinkedList 進行各種常用操作，如添加、刪除、獲取元素等，以及使用 Collections 類中的方法對 LinkedList 進行排序、反轉(zhuǎn)、打亂順序等批量操作。特別是繼承自 Queue 接口的方法，可以使 LinkedList 作為隊列使用，提供了隊列相關的操作。