鏈表(Linked List)

鏈表（Linked List）是一種線性數據結構，它由一系列節點（Node）組成，每個節點包含兩部分：數據和指向下（上）一個節點的引用（或指針）。鏈表中的節點按照線性順序連接在一起（相鄰節點不需要存儲在連續記憶體位置），不像數組一樣存儲在連續的記憶體位置。鏈表通常由頭節點（Head）來表示整個鏈表，而尾節點的下一個節點指向null，表示鏈表的結束。

鏈表有幾種常見的類型，其中最常見的包括單鏈表、雙鏈表。

 // Java LinkedList 中Node的結構
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;

        }
}

基本概念

鏈表基本結構是節點，節點一般包含數據和指向節點的指針；節點只有指向下一個節點指針的叫單鏈表（Singly Linked List），有指向上一個節點的指針的叫雙鏈表（Doubly Linked List）。

鏈表的一些關鍵特點：

• 節點（Node）： 鏈表的基本構建塊是節點，每個節點包含兩(三)部分，即 數據 element 和 指向下一個節點的指針 next（指向上一個節點的指針 prev）。
• 單鏈表（Singly Linked List）： 單鏈表中每個節點只有一個指針，即指向下一個節點的指針。
• 雙鏈表（Doubly Linked List）： 雙鏈表中每個節點有兩個指針，一個指向下一個節點，另一個指向前一個節點，使得可以雙向遍歷鏈表。
• 頭節點（Head）： 鏈表的頭節點是鏈表的第一個節點，用於標識整個鏈表的起始位置。
• 尾節點（Tail）： 鏈表的尾節點是最後一個節點，其下一個節點引用通常指向null。

鏈表的性質：

• 插入和刪除元素的時間複雜度通常為O(1)，因為只需要調整節點的指針。
• 鏈表大小可以動態增長，不受固定記憶體大小的限制。
• 訪問元素的時間複雜度為O(n)，因為必須從頭節點開始遍歷鏈表，直到找到目標元素。
• 存儲上占用較多記憶體空間，因為每個節點都需要存儲數據和指針。

基本應用（Basic）

鏈表最基本的一些演算法應用 是 根據要求操作節點指針 next 指針。

Leetcode 83. 刪除排序鏈表中的重覆元素【簡單】

給你一個 非嚴格遞增排列 的數組 nums ，請你 原地 刪除重覆出現的元素，使每個元素 只出現一次 ，返回刪除後數組的新長度。元素的 相對順序 應該保持 一致 。然後返回 nums 中唯一元素的個數。

Leetcode 203. 移除鏈表元素【簡單】

給你一個鏈表的頭節點 head 和一個整數 val ，請你刪除鏈表中所有滿足 Node.val == val 的節點，並返回 新的頭節點 。

多節點（More Node）

在解決一些演算法問題，同樣可以定義多個指針指向多個鏈表節點（Node）來進行操作來完成解答。

Leetcode 19. 刪除鏈表的倒數第 N 個結點【中等】

給你一個鏈表，刪除鏈表的倒數第 n 個結點，並且返回鏈表的頭結點。

Leetcode 2. 兩數相加【中等】

給你兩個 非空 的鏈表，表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的，並且每個節點只能存儲 一位 數字。
請你將兩個數相加，並以相同形式返回一個表示和的鏈表。
你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

總結下

本篇主要介紹了鏈表基本結構，以及相關一些演算法問題分析。鏈表還可以結合其他數據結構、演算法思想比如 哈希（Hash）、優先隊列（Priority Queue）等解決一些演算法問題；考慮到本系列文章希望能夠承前啟後，不至於出現一些先前文章未介紹到的數據結構與演算法，因此後續文章中再代入分析。

另外，從出題人的角度分析演算法的問題也是一個不錯的選擇，可能會帶來不一樣的總結與經驗。

歡迎點個小紅心，關註公眾號 Java研究者 聯繫、交流~