鏈表和數組是數據類型中兩個重要又常用地基礎數據類型，數組是連續存儲在內存中的數據結構，因此它的優勢是可以通過下標迅速的找到元素的位置，而它的缺點則是在插入和刪除元素時會導致大量元素的被迫移動，為了解決和平衡此問題于是就有了鏈表這種數據類型。

鏈表和數組可以形成有效的互補，這樣我們就可以根據不同的業務場景選擇對應的數據類型了。那么，本文我們就來重點介紹學習一下鏈表，一是因為它非常重要，二是因為面試面試必考，先來看本文的大綱：

看過某些抗日神劇我們都知道，某些秘密組織為了防止組織的成員被“一窩端”，通常會采用上下級單線聯系的方式來保護其他成員，而這種“行為”則是鏈表的主要特征。

簡介

鏈表(Linked List)是一種常見的基礎數據結構，是一種線性表，但是并不會按線性的順序存儲數據，而是在每一個節點里存到下一個節點的指針(Pointer)。

鏈表是由數據域和指針域兩部分組成的，它的組成結構如下：

復雜度分析

由于鏈表無需按順序存儲，因此鏈表在插入的時可以達到 O(1) 的復雜度，比順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要 O(n) 的時間，而順序表插入和查詢的時間復雜度分別是 O(log n) 和 O(1)。

優缺點分析

使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由于增加了節點的指針域，空間開銷比較大。

分類

鏈表通常會分為以下三類：

• 單向鏈表
• 雙向鏈表
• 循環鏈表 單循鏈表雙循環鏈表

1.單向鏈表

鏈表中最簡單的一種是單向鏈表，或叫單鏈表，它包含兩個域，一個數據域和一個指針域，指針域用于指向下一個節點，而最后一個節點則指向一個空值，如下圖所示：

單鏈表的遍歷方向單一，只能從鏈頭一直遍歷到鏈尾。它的缺點是當要查詢某一個節點的前一個節點時，只能再次從頭進行遍歷查詢，因此效率比較低，而雙向鏈表的出現恰好解決了這個問題。

接下來，我們用代碼來實現一下單向鏈表的節點：

private static class Node { E item; Node next; Node(E element, Node next) { this.item = element; this.next = next; }}

2.雙向鏈表

雙向鏈表也叫雙面鏈表，它的每個節點由三部分組成：prev 指針指向前置節點，此節點的數據和 next 指針指向后置節點，如下圖所示：

image.png

接下來，我們用代碼來實現一下雙向鏈表的節點：

private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node 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 extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable{ // 鏈表大小 transient int size = 0; // 鏈表頭部 transient Node first; // 鏈表尾部 transient Node last; public LinkedList() { } public LinkedList(Collection extends E> c) { this(); addAll(c); } // 獲取頭部元素 public E getFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return f.item; } // 獲取尾部元素 public E getLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return l.item; } // 刪除頭部元素 public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } // 刪除尾部元素 public E removeLast() { final Node 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 f = first; final Node 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 l = last; final Node 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 x = first; x != null; ) { Node 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 item; Node next; Node prev; Node(Node prev, E element, Node 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

中文

社群

image.png

2.用鏈表實現隊列

然后我們用鏈表來實現一個后進先出的“棧”，實現代碼如下：

LinkedList list = new LinkedList();// 元素入棧list.add("Java");list.add("中文");list.add("社群");while (!list.isEmpty()) { // 打印并移除棧頂元素 System.out.println(list.pollLast());}

以上程序的執行結果如下：

社群

中文

Java

image.png

鏈表使用場景

鏈表作為一種基本的物理結構，常被用來構建許多其它的邏輯結構，如堆棧、隊列都可以基于鏈表實現。

所謂的物理結構是指可以將數據存儲在物理空間中，比如數組和鏈表都屬于物理數據結構；而邏輯結構則是用于描述數據間的邏輯關系的，它可以由多種不同的物理結構來實現，比如隊列和棧都屬于邏輯結構。

鏈表常見筆試題

鏈表最常見的筆試題就是鏈表的反轉了，之前的文章《鏈表反轉的兩種實現方法，后一種擊敗了100%的用戶！》我們提供了 2 種鏈表反轉的方法，而本文我們再來擴充一下，提供 3 種鏈表反轉的方法。

實現方法 1：Stack

我們先用圖解的方式來演示一下，使用棧實現鏈表反轉的具體過程，如下圖所示。

image.png

全部入棧：

因為棧是先進后出的數據結構，因此它的執行過程如下圖所示：

最終的執行結果如下圖所示：

實現代碼如下所示：

public ListNode reverseList(ListNode head) { if (head == null) return null; Stack 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：遞歸

同樣的，我們先用圖解的方式來演示一下，此方法實現的具體過程，如下圖所示。

image.png

實現代碼如下所示：

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 種實現方法，希望本文的內容對你有幫助。

如果覺得有用請各位老爺多多點贊和分享，原創不易，謝謝您了！

總結

以上是生活随笔為你收集整理的java 双向链表_23张图！万字详解「链表」，从小白到大佬的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。