鏈表(Linked List)

鏈表（Linked List）是一種線性數據結構，它由一系列節(jié)點（Node）組成，每個節(jié)點包含兩部分：數據和指向下（上）一個節(jié)點的引用（或指針）。鏈表中的節(jié)點按照線性順序連接在一起（相鄰節(jié)點不需要存儲在連續(xù)內存位置），不像數組一樣存儲在連續(xù)的內存位置。鏈表通常由頭節(jié)點（Head）來表示整個鏈表，而尾節(jié)點的下一個節(jié)點指向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;

        }
}

基本概念

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

鏈表的一些關鍵特點：

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

鏈表的性質：

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

基本應用（Basic）

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

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

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

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

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

多節(jié)點（More Node）

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

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

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

Leetcode 2. 兩數相加【中等】

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

總結下

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

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

歡迎點個小紅心，關注公眾號 Java研究者 聯(lián)系、交流~文章來源地址http://www.zghlxwxcb.cn/news/detail-711525.html

到了這里，關于數據結構與算法 | 鏈表（Linked List）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！