23張圖！萬字詳解「鏈表」，從小白到大佬！
鏈表和數(shù)組是數(shù)據(jù)類型中兩個重要又常用的基礎數(shù)據(jù)類型。
數(shù)組是連續(xù)存儲在內(nèi)存中的數(shù)據(jù)結構，因此它的優(yōu)勢是可以通過下標迅速的找到元素的位置，而它的缺點則是在插入和刪除元素時會導致大量元素的被迫移動，為了解決和平衡此問題于是就有了鏈表這種數(shù)據(jù)類型。
鏈表和數(shù)組可以形成有效的互補，這樣我們就可以根據(jù)不同的業(yè)務場景選擇對應的數(shù)據(jù)類型了。那么，本文我們就來重點介紹學習一下鏈表，一是因為它非常重要，二是因為面試必考，先來看本文大綱：
看過某些抗日神劇我們都知道，某些秘密組織為了防止組織的成員被“一窩端”，通常會采用上下級單線聯(lián)系的方式來保護其他成員，而這種“行為”則是鏈表的主要特征。
簡介
鏈表(Linked List)是一種常見的基礎數(shù)據(jù)結構，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的指針(Pointer)。
鏈表是由數(shù)據(jù)域和指針域兩部分組成的，它的組成結構如下：
復雜度分析
由于鏈表無需按順序存儲，因此鏈表在插入的時可以達到 O(1) 的復雜度，比順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要 O(n) 的時間，而順序表插入和查詢的時間復雜度分別是 O(log n) 和 O(1)。
優(yōu)缺點分析
使用鏈表結構可以克服數(shù)組鏈表需要預先知道數(shù)據(jù)大小的缺點，鏈表結構可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結點的指針域，空間開銷比較大。
分類
鏈表通常會分為以下三類：
- 單向鏈表
- 雙向鏈表
- 循環(huán)鏈表
- 單循鏈表
- 雙循環(huán)鏈表
1.單向鏈表
鏈表中最簡單的一種是單向鏈表，或叫單鏈表，它包含兩個域，一個數(shù)據(jù)域和一個指針域，指針域用于指向下一個節(jié)點，而最后一個節(jié)點則指向一個空值，如下圖所示：
單鏈表的遍歷方向單一，只能從鏈頭一直遍歷到鏈尾。它的缺點是當要查詢某一個節(jié)點的前一個節(jié)點時，只能再次從頭進行遍歷查詢，因此效率比較低，而雙向鏈表的出現(xiàn)恰好解決了這個問題。
接下來，我們用代碼來實現(xiàn)一下單向鏈表的節(jié)點：
- private static class Node<E> {
- E item;
- Node<E> next;
- Node(E element, Node<E> next) {
- this.item = element;
- this.next = next;
- }
- }
2.雙向鏈表
雙向鏈表也叫雙面鏈表，它的每個節(jié)點由三部分組成：prev 指針指向前置節(jié)點，此節(jié)點的數(shù)據(jù)和 next 指針指向后置節(jié)點，如下圖所示：
接下來，我們用代碼來實現(xiàn)一下雙向鏈表的節(jié)點：
- 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.循環(huán)鏈表
循環(huán)鏈表又分為單循環(huán)鏈表和雙循環(huán)鏈表，也就是將單向鏈表或雙向鏈表的首尾節(jié)點進行連接，這樣就實現(xiàn)了單循環(huán)鏈表或雙循環(huán)鏈表了，如下圖所示：
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);
- }
- // 添加頭部元素的具體執(zhí)行方法
- 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++;
- }
- // 查詢鏈表個數(shù)
- 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++;
- }
- // 根據(jù)下標獲取元素
- 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;
- }
- }
- // 忽略其他方法......
- }
從上述節(jié)點 Node 的定義可以看出：LinkedList 其實是一個雙向鏈表，因為它定義了兩個指針 next 和 prev 分別用來指向自己的下一個和上一個節(jié)點。
鏈表常用方法
LinkedList 的設計還是很巧妙的，了解了它的實現(xiàn)代碼之后，下面我們來看看它是如何使用的?或者說它的常用方法有哪些。
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);
- }
- }
以上代碼的執(zhí)行結果為：
- [頭部添加, Java, 中文, 社群, 尾部添加]
出來以上的 3 個增加方法之外，LinkedList 還包含了其他的添加方法，如下所示：
- add(int index, E element)：向指定位置插入元素;
- offer(E e)：向鏈表末尾添加元素，返回是否成功;
- offerFirst(E e)：頭部插入元素，返回是否成功;
- offerLast(E e)：尾部插入元素，返回是否成功。
add 和 offer 的區(qū)別
它們的區(qū)別主要體現(xiàn)在以下兩點：
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);
- }
- }
以上代碼的執(zhí)行結果為：
[中間]
除了以上刪除方法之外，更多的刪除方法如下所示：
- 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);
- }
- }
以上代碼的執(zhí)行結果為：
- [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());
- // 根據(jù)下標獲取
- System.out.println(list.get(1));
- // peekXXX() 獲取
- System.out.println("--- peek() ---");
- // 獲取最后一個
- System.out.println(list.peekLast());
- // 獲取首個
- System.out.println(list.peekFirst());
- // 根據(jù)首個
- System.out.println(list.peek());
- }
- }
以上代碼的執(zhí)行結果為：
- 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.用鏈表實現(xiàn)棧
接下來我們用鏈表來實現(xiàn)一個先進先出的“隊列”，實現(xiàn)代碼如下：
- LinkedList list = new LinkedList();
- // 元素入列
- list.add("Java");
- list.add("中文");
- list.add("社群");
- while (!list.isEmpty()) {
- // 打印并移除隊頭元素
- System.out.println(list.poll());
- }
以上程序的執(zhí)行結果如下：
- Java
- 中文
- 社群
2.用鏈表實現(xiàn)隊列
然后我們用鏈表來實現(xiàn)一個后進先出的“棧”，實現(xiàn)代碼如下：
- LinkedList list = new LinkedList();
- // 元素入棧
- list.add("Java");
- list.add("中文");
- list.add("社群");
- while (!list.isEmpty()) {
- // 打印并移除棧頂元素
- System.out.println(list.pollLast());
- }
以上程序的執(zhí)行結果如下：
- 社群
- 中文
- Java
鏈表使用場景
鏈表作為一種基本的物理結構，常被用來構建許多其它的邏輯結構，如堆棧、隊列都可以基于鏈表實現(xiàn)。
所謂的物理結構是指可以將數(shù)據(jù)存儲在物理空間中，比如數(shù)組和鏈表都屬于物理數(shù)據(jù)結構;而邏輯結構則是用于描述數(shù)據(jù)間的邏輯關系的，它可以由多種不同的物理結構來實現(xiàn)，比如隊列和棧都屬于邏輯結構。
鏈表常見筆試題
鏈表最常見的筆試題就是鏈表的反轉(zhuǎn)了，之前的文章《鏈表反轉(zhuǎn)的兩種實現(xiàn)方法，后一種擊敗了100%的用戶!》我們提供了 2 種鏈表反轉(zhuǎn)的方法，而本文我們再來擴充一下，提供 3 種鏈表反轉(zhuǎn)的方法。
實現(xiàn)方法 1：Stack我們先用圖解的方式來演示一下，使用棧實現(xiàn)鏈表反轉(zhuǎn)的具體過程，如下圖所示。
全部入棧：
全部入棧：
因為棧是先進后出的數(shù)據(jù)結構，因此它的執(zhí)行過程如下圖所示：
最終的執(zhí)行結果如下圖所示：
實現(xiàn)代碼如下所示：
- public ListNode reverseList(ListNode head) {
- if (head == null) return null;
- Stack<ListNode> stack = new Stack<>();
- stack.push(head); // 存入第一個節(jié)點
- while (head.next != null) {
- stack.push(head.next); // 存入其他節(jié)點
- head = head.next; // 指針移動的下一位
- }
- // 反轉(zhuǎn)鏈表
- ListNode listNode = stack.pop(); // 反轉(zhuǎn)第一個元素
- ListNode lastNode = listNode; // 臨時節(jié)點，在下面的 while 中記錄上一個節(jié)點
- while (!stack.isEmpty()) {
- ListNode item = stack.pop(); // 當前節(jié)點
- lastNode.next = item;
- lastNode = item;
- }
- lastNode.next = null; // 最后一個節(jié)點賦為null（不然會造成死循環(huán)）
- return listNode;
- }
LeetCode 驗證結果如下圖所示：
可以看出使用棧的方式來實現(xiàn)鏈表的反轉(zhuǎn)執(zhí)行的效率比較低。
實現(xiàn)方法2：遞歸
同樣的，我們先用圖解的方式來演示一下，此方法實現(xiàn)的具體過程，如下圖所示。
實現(xiàn)代碼如下所示：
- public static ListNode reverseList(ListNode head) {
- if (head == null || head.next == null) return head;
- // 從下一個節(jié)點開始遞歸
- ListNode reverse = reverseList(head.next);
- head.next.next = head; // 設置下一個節(jié)點的 next 為當前節(jié)點
- head.next = null; // 把當前節(jié)點的 next 賦值為 null，避免循環(huán)引用
- return reverse;
- }
LeetCode 驗證結果如下圖所示：
可以看出這種實現(xiàn)方法在執(zhí)行效率方面已經(jīng)滿足我們的需求了，性能還是很高的。
實現(xiàn)方法 3：循環(huán)
我們也可以通過循環(huán)的方式來實現(xiàn)鏈表反轉(zhuǎn)，只是這種方法無需重復調(diào)用自身方法，只需要一個循環(huán)就搞定了，實現(xiàn)代碼如下：
- class Solution {
- public ListNode reverseList(ListNode head) {
- if (head == null) return null;
- // 最終排序的倒序鏈表
- ListNode prev = null;
- while (head != null) {
- // 循環(huán)的下個節(jié)點
- ListNode next = head.next;
- // 反轉(zhuǎn)節(jié)點操作
- head.next = prev;
- // 存儲下個節(jié)點的上個節(jié)點
- prev = head;
- // 移動指針到下一個循環(huán)
- head = next;
- }
- return prev;
- }
- }
LeetCode 驗證結果如下圖所示：
從上述圖片可以看出，使用此方法在時間復雜度和空間復雜度上都是目前的最優(yōu)解，比之前的兩種方法更加理想。
總結
本文我們講了鏈表的定義，它是由數(shù)據(jù)域和指針域兩部分組成的。鏈表可分為：單向鏈表、雙向鏈表和循環(huán)鏈表，其中循環(huán)鏈表又可以分為單循鏈表和雙循環(huán)鏈表。通過 JDK 的源碼可知，Java 中的 LinkedList 其實是雙向鏈表，我們可以使用它來實現(xiàn)隊列或者棧，最后我們講了反轉(zhuǎn)鏈表的 3 種實現(xiàn)方法，希望本文的內(nèi)容對你有幫助。
