連結串列(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研究者聯絡、交流~

資料結構與演演算法 | 連結串列（Linked List）