23 張圖！萬字詳解 Java 「鏈表」，從小白到大佬！
鏈表和數組是數據類型中兩個重要又常用的基礎數據類型。
數組是連續存儲在內存中的數據結構，因此它的優勢是可以通過下標迅速的找到元素的位置，而它的缺點則是在插入和刪除元素時會導致大量元素的被迫移動，爲了解決和平衡此問題於是就有了鏈表這種數據類型。
鏈表和數組可以形成有效的互補，這樣我們就可以根據不同的業務場景選擇對應的數據類型了。
那麼，本文我們就來重點介紹學習一下鏈表，一是因爲它非常重要，二是因爲面試必考，先來看本文大綱：
看過某些抗日神劇我們都知道，某些祕密組織爲了防止組織的成員被 “一窩端”，通常會採用上下級單線聯繫的方式來保護其他成員，而這種“行爲” 則是鏈表的主要特徵。
簡介
鏈表（Linked List）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裏存到下一個節點的指針（Pointer）。
鏈表是由數據域和指針域兩部分組成的，它的組成結構如下：
複雜度分析
由於鏈表無需按順序存儲，因此鏈表在插入的時可以達到 O(1) 的複雜度，比順序錶快得多，但是查找一個節點或者訪問特定編號的節點則需要 O(n) 的時間，而順序表插入和查詢的時間複雜度分別是 O(log n) 和 O(1)。
優缺點分析
使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由於增加了結點的指針域，空間開銷比較大。
分類
鏈表通常會分爲以下三類：
-
單向鏈表
-
雙向鏈表
-
循環鏈表
-
單循鏈表
-
雙循環鏈表
1. 單向鏈表
鏈表中最簡單的一種是單向鏈表，或叫單鏈表，它包含兩個域，一個數據域和一個指針域，指針域用於指向下一個節點，而最後一個節點則指向一個空值，如下圖所示：
接下來，我們用代碼來實現一下單向鏈表的節點：
private static class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}2. 雙向鏈表
雙向鏈表也叫雙面鏈表，它的每個節點由三部分組成：prev 指針指向前置節點，此節點的數據和 next 指針指向後置節點，如下圖所示：
接下來，我們用代碼來實現一下雙向鏈表的節點：
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. 循環鏈表
循環鏈表又分爲單循環鏈表和雙循環鏈表，也就是將單向鏈表或雙向鏈表的首尾節點進行連接，這樣就實現了單循環鏈表或雙循環鏈表了，如下圖所示：
Java 中的鏈表
學習了鏈表的基礎知識之後，我們來思考一個問題：Java 中的鏈表 LinkedList 是屬於哪種類型的鏈表呢？單向鏈表還是雙向鏈表？
要回答這個問題，首先我們要來看 JDK 中的源碼，如下所示：
package java.util;
import java.util.function.Consumer;
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 鏈表大小
transient int size = 0;
// 鏈表頭部
transient Node<E> first;
// 鏈表尾部
transient Node<E> last;
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
// 獲取頭部元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
// 獲取尾部元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
// 刪除頭部元素
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 刪除尾部元素
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// 添加頭部元素
public void addFirst(E e) {
linkFirst(e);
}
// 添加頭部元素的具體執行方法
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;
size++;
modCount++;
}
// 添加尾部元素
public void addLast(E e) {
linkLast(e);
}
// 添加尾部元素的具體方法
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;
else
l.next = newNode;
size++;
modCount++;
}
// 查詢鏈表個數
public int size() {
return size;
}
// 清空鏈表
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
// 根據下標獲取元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
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;
}
}
// 忽略其他方法......
}從上述節點 Node 的定義可以看出：LinkedList 其實是一個雙向鏈表，因爲它定義了兩個指針 next 和 prev 分別用來指向自己的下一個和上一個節點。
鏈表常用方法
LinkedList 的設計還是很巧妙的，瞭解了它的實現代碼之後，下面我們來看看它是如何使用的？或者說它的常用方法有哪些。
1. 增加
接下來我們來演示一下增加方法的使用：
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.add("Java");
list.add("中文");
list.add("社羣");
list.addFirst("頭部添加"); // 添加元素到頭部
list.addLast("尾部添加"); // 添加元素到最後
System.out.println(list);
}
}以上代碼的執行結果爲：
[頭部添加, Java, 中文, 社羣, 尾部添加]
出來以上的 3 個增加方法之外，LinkedList 還包含了其他的添加方法，如下所示：
-
add(int index, E element)：向指定位置插入元素；
-
offer(E e)：向鏈表末尾添加元素，返回是否成功；
-
offerFirst(E e)：頭部插入元素，返回是否成功；
-
offerLast(E e)：尾部插入元素，返回是否成功。
add 和 offer 的區別
它們的區別主要體現在以下兩點：
-
offer 方法屬於 Deque 接口，add 方法屬於 Collection 的接口；
-
當隊列添加失敗時，如果使用 add 方法會報錯，而 offer 方法會返回 false。
2. 刪除
刪除功能的演示代碼如下：
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.offer("頭部");
list.offer("中間");
list.offer("尾部");
list.removeFirst(); // 刪除頭部元素
list.removeLast(); // 刪除尾部元素
System.out.println(list);
}
}以上代碼的執行結果爲：
[中間]
除了以上刪除方法之外，更多的刪除方法如下所示：
-
clear()：清空鏈表；
-
removeFirst()：刪除並返回第一個元素；
-
removeLast()：刪除並返回最後一個元素；
-
remove(Object o)：刪除某一元素，返回是否成功；
-
remove(int index)：刪除指定位置的元素；
-
poll()：刪除並返回第一個元素；
-
remove()：刪除並返回第一個元素。
3. 修改
修改方法的演示代碼如下：
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.offer("Java");
list.offer("MySQL");
list.offer("DB");
// 修改
list.set(2, "Oracle");
System.out.println(list);
}
}以上代碼的執行結果爲：
[Java, MySQL, Oracle]
4. 查詢
查詢方法的演示代碼如下：
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.offer("Java");
list.offer("MySQL");
list.offer("DB");
// --- getXXX() 獲取 ---
// 獲取最後一個
System.out.println(list.getLast());
// 獲取首個
System.out.println(list.getFirst());
// 根據下標獲取
System.out.println(list.get(1));
// peekXXX() 獲取
System.out.println("--- peek() ---");
// 獲取最後一個
System.out.println(list.peekLast());
// 獲取首個
System.out.println(list.peekFirst());
// 根據首個
System.out.println(list.peek());
}
}以上代碼的執行結果爲：
DB
Java
MySQL
--- peek() ---
DB
Java
Java
5. 遍歷
LinkedList 的遍歷方法包含以下三種。
遍歷方法一：
for (int size = linkedList.size(), i = 0; i < size; i++) {
System.out.println(linkedList.get(i));
}遍歷方法二：
for (String str: linkedList) {
System.out.println(str);
}遍歷方法三：
Iterator iter = linkedList.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}鏈表應用：隊列 & 棧
1. 用鏈表實現棧
接下來我們用鏈表來實現一個先進先出的 “隊列”，實現代碼如下：
LinkedList list = new LinkedList();
// 元素入列
list.add("Java");
list.add("中文");
list.add("社羣");
while (!list.isEmpty()) {
// 打印並移除隊頭元素
System.out.println(list.poll());
}以上程序的執行結果如下：
Java
中文
社羣
2. 用鏈表實現隊列
然後我們用鏈表來實現一個後進先出的 “棧”，實現代碼如下：
LinkedList list = new LinkedList();
// 元素入棧
list.add("Java");
list.add("中文");
list.add("社羣");
while (!list.isEmpty()) {
// 打印並移除棧頂元素
System.out.println(list.pollLast());
}以上程序的執行結果如下：
社羣
中文
Java
鏈表使用場景
鏈表作爲一種基本的物理結構，常被用來構建許多其它的邏輯結構，如堆棧、隊列都可以基於鏈表實現。
所謂的物理結構是指可以將數據存儲在物理空間中，比如數組和鏈表都屬於物理數據結構；而邏輯結構則是用於描述數據間的邏輯關係的，它可以由多種不同的物理結構來實現，比如隊列和棧都屬於邏輯結構。
鏈表常見筆試題
鏈表最常見的筆試題就是鏈表的反轉了，之前的文章《鏈表反轉的兩種實現方法，後一種擊敗了 100% 的用戶！》我們提供了 2 種鏈表反轉的方法，而本文我們再來擴充一下，提供 3 種鏈表反轉的方法。
實現方法 1：Stack
我們先用圖解的方式來演示一下，使用棧實現鏈表反轉的具體過程，如下圖所示。
全部入棧：
public ListNode reverseList(ListNode head) {
if (head == null) return null;
Stack<ListNode> stack = new Stack<>();
stack.push(head); // 存入第一個節點
while (head.next != null) {
stack.push(head.next); // 存入其他節點
head = head.next; // 指針移動的下一位
}
// 反轉鏈表
ListNode listNode = stack.pop(); // 反轉第一個元素
ListNode lastNode = listNode; // 臨時節點，在下面的 while 中記錄上一個節點
while (!stack.isEmpty()) {
ListNode item = stack.pop(); // 當前節點
lastNode.next = item;
lastNode = item;
}
lastNode.next = null; // 最後一個節點賦爲null（不然會造成死循環）
return listNode;
}LeetCode 驗證結果如下圖所示：
可以看出使用棧的方式來實現鏈表的反轉執行的效率比較低。
實現方法 2：遞歸
同樣的，我們先用圖解的方式來演示一下，此方法實現的具體過程，如下圖所示。
實現代碼如下所示：
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
// 從下一個節點開始遞歸
ListNode reverse = reverseList(head.next);
head.next.next = head; // 設置下一個節點的 next 爲當前節點
head.next = null; // 把當前節點的 next 賦值爲 null，避免循環引用
return reverse;
}LeetCode 驗證結果如下圖所示：
實現方法 3：循環
我們也可以通過循環的方式來實現鏈表反轉，只是這種方法無需重複調用自身方法，只需要一個循環就搞定了，實現代碼如下：
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
// 最終排序的倒序鏈表
ListNode prev = null;
while (head != null) {
// 循環的下個節點
ListNode next = head.next;
// 反轉節點操作
head.next = prev;
// 存儲下個節點的上個節點
prev = head;
// 移動指針到下一個循環
head = next;
}
return prev;
}
}LeetCode 驗證結果如下圖所示：
總結
本文我們講了鏈表的定義，它是由數據域和指針域兩部分組成的。鏈表可分爲：單向鏈表、雙向鏈表和循環鏈表，其中循環鏈表又可以分爲單循鏈表和雙循環鏈表。通過 JDK 的源碼可知，Java 中的 LinkedList 其實是雙向鏈表，我們可以使用它來實現隊列或者棧，最後我們講了反轉鏈表的 3 種實現方法，希望本文的內容對你有幫助。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ev1nTEyGiPYbjV5bX7d9XQ