Hello 算法之鏈結串列全解析節點結構、五大操作與典型應用【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo記憶體空間是所有程式的公共資源在複雜的系統執行環境下空閒記憶體往往散落在各處。儲存陣列需要連續記憶體當陣列規模很大時系統可能無法提供如此大的連續空間此時鏈結串列linked list的靈活性優勢便顯現出來。本文以《Hello 算法》繁中版 鏈結串列章節 為主體結合倉庫內 Python、C、C、Go 等語言的完整可執行原始碼系統講解鏈結串列的節點結構、初始化、插入、刪除、訪問、查詢五大操作的時間複雜度以及單向、雙向、環形三種鏈結串列的區別與真實應用場景。讀完本文你將掌握鏈結串列的底層原理、多語言實作範式並能在堆疊、佇列、雜湊表、圖、LRU 快取等場景中自如選用鏈結串列。鏈結串列的本質分散儲存的節點與引用鏈結串列linked list是一種線性資料結構其中的每個元素都是一個**節點node**物件各節點之間透過「引用」相連接。引用記錄了下一個節點的記憶體位址透過它可以從當前節點訪問到下一個節點。這種設計使得各節點可以分散儲存在記憶體各處節點的記憶體位址無須連續——這正是鏈結串列與陣列最根本的區別。關於鏈結串列有幾個基本概念需要明確鏈結串列的首個節點被稱為頭節點最後一個節點被稱為尾節點尾節點指向的是「空」它在 Java、C 和 Python 中分別被記為null、nullptr和None在 C、C、Go 和 Rust 等支援指標的語言中上述「引用」應被理解為「指標」。每個節點都包含兩項資料節點的「值」和指向下一節點的「引用」。也就是說在相同資料量下鏈結串列比陣列佔用更多的記憶體空間因為每個節點除了儲存資料本身還必須額外儲存一個引用指標欄位。節點定義十四種語言一次看懂鏈結串列的核心是節點結構不同語言對「引用」的表述方式各有特色。以下是《Hello 算法》倉庫中節點定義的多語言對照你可以直接複製到自己的專案中使用。 Pythonpython title class ListNode: 鏈結串列節點類別 def __init__(self, val: int): self.val: int val # 節點值 self.next: ListNode | None None # 指向下一節點的引用 Ccpp title /* 鏈結串列節點結構體 */ struct ListNode { int val; // 節點值 ListNode *next; // 指向下一節點的指標 ListNode(int x) : val(x), next(nullptr) {} // 建構子 }; Javajava title /* 鏈結串列節點類別 */ class ListNode { int val; // 節點值 ListNode next; // 指向下一節點的引用 ListNode(int x) { val x; } // 建構子 } C#csharp title /* 鏈結串列節點類別 */ class ListNode(int x) { // 建構子 int val x; // 節點值 ListNode? next; // 指向下一節點的引用 } Gogo title /* 鏈結串列節點結構體 */ type ListNode struct { Val int // 節點值 Next *ListNode // 指向下一節點的指標 } // NewListNode 建構子建立一個新的鏈結串列 func NewListNode(val int) *ListNode { return ListNode{ Val: val, Next: nil, } } Swiftswift title /* 鏈結串列節點類別 */ class ListNode { var val: Int // 節點值 var next: ListNode? // 指向下一節點的引用 init(x: Int) { // 建構子 val x } } JSjavascript title /* 鏈結串列節點類別 */ class ListNode { constructor(val, next) { this.val (val undefined ? 0 : val); // 節點值 this.next (next undefined ? null : next); // 指向下一節點的引用 } } TStypescript title /* 鏈結串列節點類別 */ class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val val undefined ? 0 : val; // 節點值 this.next next undefined ? null : next; // 指向下一節點的引用 } } Dartdart title /* 鏈結串列節點類別 */ class ListNode { int val; // 節點值 ListNode? next; // 指向下一節點的引用 ListNode(this.val, [this.next]); // 建構子 } Rustrust title use std::rc::Rc; use std::cell::RefCell; /* 鏈結串列節點類別 */ #[derive(Debug)] struct ListNode { val: i32, // 節點值 next: OptionRcRefCellListNode, // 指向下一節點的指標 } Cc title /* 鏈結串列節點結構體 */ typedef struct ListNode { int val; // 節點值 struct ListNode *next; // 指向下一節點的指標 } ListNode; /* 建構子 */ ListNode *newListNode(int val) { ListNode *node; node (ListNode *) malloc(sizeof(ListNode)); node-val val; node-next NULL; return node; } Kotlinkotlin title /* 鏈結串列節點類別 */ // 建構子 class ListNode(x: Int) { val _val: Int x // 節點值 var next: ListNode? null // 指向下一個節點的引用 } Rubyruby title # 鏈結串列節點類別 class ListNode attr_accessor :val # 節點值 attr_accessor :next # 指向下一節點的引用 def initialize(val0, next_nodenil) val val next next_node end end 值得注意的是 Rust 的寫法出於所有權與記憶體安全的考量Rust 使用OptionRcRefCellListNode來表達「可空、可共享、可變的節點引用」這與 C 語言中樸素的指標表達形成了鮮明對照也體現了不同語言對同一資料結構的不同落地方式。此外在 Python 倉庫中節點類別定義在 modules/list_node.py並提供了list_to_linked_list將陣列反序列化為鏈結串列與linked_list_to_list將鏈結串列序列化為陣列兩個實用函式方便測試與驗證C 語言的節點結構與建構子則收錄於 utils/list_node.h。鏈結串列常用操作初始化鏈結串列建立鏈結串列分為兩步第一步是初始化各節點物件第二步是構建節點之間的引用關係。初始化完成後就可以從頭節點出發透過next引用依次訪問所有節點。例如建立鏈結串列1 - 3 - 2 - 5 - 4 Pythonpython titlelinked_list.py # 初始化鏈結串列 1 - 3 - 2 - 5 - 4 # 初始化各個節點 n0 ListNode(1) n1 ListNode(3) n2 ListNode(2) n3 ListNode(5) n4 ListNode(4) # 構建節點之間的引用 n0.next n1 n1.next n2 n2.next n3 n3.next n4 Ccpp titlelinked_list.cpp /* 初始化鏈結串列 1 - 3 - 2 - 5 - 4 */ // 初始化各個節點 ListNode* n0 new ListNode(1); ListNode* n1 new ListNode(3); ListNode* n2 new ListNode(2); ListNode* n3 new ListNode(5); ListNode* n4 new ListNode(4); // 構建節點之間的引用 n0-next n1; n1-next n2; n2-next n3; n3-next n4; Javajava titlelinked_list.java /* 初始化鏈結串列 1 - 3 - 2 - 5 - 4 */ // 初始化各個節點 ListNode n0 new ListNode(1); ListNode n1 new ListNode(3); ListNode n2 new ListNode(2); ListNode n3 new ListNode(5); ListNode n4 new ListNode(4); // 構建節點之間的引用 n0.next n1; n1.next n2; n2.next n3; n3.next n4; Cc titlelinked_list.c /* 初始化鏈結串列 1 - 3 - 2 - 5 - 4 */ // 初始化各個節點 ListNode* n0 newListNode(1); ListNode* n1 newListNode(3); ListNode* n2 newListNode(2); ListNode* n3 newListNode(5); ListNode* n4 newListNode(4); // 構建節點之間的引用 n0-next n1; n1-next n2; n2-next n3; n3-next n4; Gogo titlelinked_list.go /* 初始化鏈結串列 1 - 3 - 2 - 5 - 4 */ // 初始化各個節點 n0 : NewListNode(1) n1 : NewListNode(3) n2 : NewListNode(2) n3 : NewListNode(5) n4 : NewListNode(4) // 構建節點之間的引用 n0.Next n1 n1.Next n2 n2.Next n3 n3.Next n4 陣列整體是一個變數例如陣列nums包含元素nums[0]、nums[1]等而鏈結串列是由多個獨立的節點物件組成的。我們通常將頭節點當作鏈結串列的代稱例如以上程式碼中的鏈結串列可記作鏈結串列n0。插入節點O(1) 時間複雜度在鏈結串列中插入節點非常容易。如下圖所示假設想在相鄰的兩個節點n0和n1之間插入一個新節點P只需改變兩個節點引用指標即可時間複雜度為 O(1)。相比之下在陣列中插入元素的時間複雜度為 O(n)在大資料量下效率較低。以 Python 為例插入操作的核心實作如下完整程式見 linked_list.pydef insert(n0: ListNode, P: ListNode): 在鏈結串列的節點 n0 之後插入節點 P n1 n0.next P.next n1 n0.next P這個函式雖然只有三行卻精準地表達了插入的全部語意先記錄後繼節點n1讓P指向n1再讓n0指向P。注意順序不能顛倒——如果先執行n0.next P就會遺失n1的引用。C 語言版本與之完全同構可見 linked_list.cC 版本見 linked_list.cpp。刪除節點只需改變一個引用刪除節點同樣方便只需改變一個節點的引用指標即可。請注意儘管在刪除操作完成後節點P仍然指向n1但實際上走訪此鏈結串列已經無法訪問到P這意味著P已經不再屬於該鏈結串列了。Python 實作如下見 linked_list.pydef remove(n0: ListNode): 刪除鏈結串列的節點 n0 之後的首個節點 if not n0.next: return # n0 - P - n1 P n0.next n1 P.next n0.next n1C/C/Go 版本在刪除後還需要處理記憶體釋放問題C 語言使用free(P)C 使用delete P見 linked_list.cpp而 Go 依賴垃圾回收機制無需手動釋放見 linked_list.go。另外一個實作細節是C 語言中remove與stdio.h的函式名衝突因此在倉庫中 C 版本將刪除函式命名為removeItem見 linked_list.c。訪問節點O(n) 的線性走訪在鏈結串列中訪問節點的效率較低。陣列可以在 O(1) 時間下訪問任意元素鏈結串列則不然——程式需要從頭節點出發逐個向後走訪直至找到目標節點。訪問鏈結串列的第i個節點需要迴圈i - 1輪時間複雜度為 O(n)。Python 實作如下見 linked_list.pydef access(head: ListNode, index: int) - ListNode | None: 訪問鏈結串列中索引為 index 的節點 for _ in range(index): if not head: return None head head.next return head查詢節點線性查詢走訪鏈結串列查詢其中值為target的節點輸出該節點在鏈結串列中的索引。此過程也屬於線性查詢最壞情況下需要走訪完整條鏈結串列。Python 實作如下見 linked_list.pydef find(head: ListNode, target: int) - int: 在鏈結串列中查找值為 target 的首個節點 index 0 while head: if head.val target: return index head head.next index 1 return -1值得一提的是查不到時返回-1是鏈結串列查詢的通用約定在 C、C、Go 等語言的倉庫實作中也保持一致例如 linked_list.go。上述五種操作的完整可執行範例含print_linked_list輸出驗證可以在 linked_list.py 中一鍵執行Python 的鏈結串列列印工具實作於 print_util.py其原理是先將鏈結串列序列化為陣列再以-連接列印。陣列 vs. 鏈結串列兩種相反的儲存策略陣列與鏈結串列採用兩種相反的儲存策略——前者依賴連續記憶體空間後者依賴分散記憶體空間因此各種性質與操作效率也呈現對立特點。下表總結了二者的完整對比陣列鏈結串列儲存方式連續記憶體空間分散記憶體空間容量擴展長度不可變可靈活擴展記憶體效率元素佔用記憶體少、但可能浪費空間元素佔用記憶體多訪問元素O(1)O(n)新增元素O(n)O(1)刪除元素O(n)O(1)這張對比表是選擇資料結構的核心依據若應用以隨機訪問為主如按下標取數、二分查找陣列是首選若應用以頻繁的插入刪除為主如實現佇列、快取淘汰鏈結串列的 O(1) 插入刪除優勢則不可替代。當然實際工程中還需要考慮 CPU 快取友好性、記憶體碎片等因素詳見本章 陣列 與 記憶體與快取 兩篇文檔。常見鏈結串列型別如下圖所示常見的鏈結串列型別包括三種。單向鏈結串列即前面介紹的普通鏈結串列。節點包含值和指向下一節點的引用兩項資料。首個節點稱為頭節點最後一個節點稱為尾節點尾節點指向空None。環形鏈結串列如果令單向鏈結串列的尾節點指向頭節點首尾相接則得到一個環形鏈結串列。在環形鏈結串列中任意節點都可以視作頭節點。雙向鏈結串列與單向鏈結串列相比雙向鏈結串列記錄了兩個方向的引用——節點定義同時包含指向後繼節點下一個節點和前驅節點上一個節點的引用指標。相較於單向鏈結串列雙向鏈結串列更具靈活性可以朝兩個方向走訪但相應地也需要佔用更多記憶體空間。以 Python 與 C 為例雙向鏈結串列的節點定義如下 Pythonpython title class ListNode: 雙向鏈結串列節點類別 def __init__(self, val: int): self.val: int val # 節點值 self.next: ListNode | None None # 指向後繼節點的引用 self.prev: ListNode | None None # 指向前驅節點的引用 Cc title /* 雙向鏈結串列節點結構體 */ typedef struct ListNode { int val; // 節點值 struct ListNode *next; // 指向後繼節點的指標 struct ListNode *prev; // 指向前驅節點的指標 } ListNode; 其餘語言的雙向節點定義C、Java、C#、Go、Swift、JS、TS、Dart、Rust、Kotlin、Ruby均可在 linked_list.md 中查看。此外倉庫的 array_deque.c 與 linkedlist_deque.c 中還有基於雙向鏈結串列實作雙端佇列的完整範例是理解雙向引用實戰價值的絕佳補充材料。鏈結串列典型應用單向鏈結串列通常用於實現堆疊、佇列、雜湊表和圖等資料結構堆疊與佇列當插入和刪除操作都在鏈結串列的一端進行時表現的特性為先進後出FILO對應堆疊當插入操作在鏈結串列的一端進行、刪除操作在另一端進行時表現的特性為先進先出FIFO對應佇列。倉庫中的 linkedlist_stack.c 與 linkedlist_queue.c 正是基於這一特性用鏈結串列實作堆疊與佇列。雜湊表鏈式位址是解決雜湊衝突的主流方案之一在該方案中所有衝突的元素都會被放到一個鏈結串列中。可參見 hash_map_chaining.c 的完整實作。圖鄰接表是表示圖的一種常用方式圖的每個頂點都與一個鏈結串列相關聯鏈結串列中的每個元素代表與該頂點相連的其他頂點。可參見 graph_adjacency_list.c。雙向鏈結串列常用於需要快速查詢前一個和後一個元素的場景高階資料結構在紅黑樹、B 樹中需要訪問節點的父節點這可以透過在節點中儲存一個指向父節點的引用來實現類似於雙向鏈結串列。瀏覽器歷史用戶點擊前進或後退按鈕時瀏覽器需要知道用戶訪問過的前一個和後一個網頁雙向鏈結串列使這種操作變得簡單。LRU 演算法在快取淘汰LRU演算法中需要快速找到最近最少使用的資料同時支援快速新增和刪除節點雙向鏈結串列非常合適。環形鏈結串列常用於需要週期性操作的場景例如作業系統的資源排程時間片輪轉排程演算法這是一種常見的 CPU 排程演算法需要對一組程序進行迴圈——每個程序被賦予一個時間片用完後 CPU 切換到下一個程序。這種迴圈操作可以透過環形鏈結串列來實現。資料緩衝區在某些資料緩衝區的實作中例如音訊、影片播放器資料流會被分成多個緩衝塊並放入一個環形鏈結串列以實現無縫播放。小結與學習路徑鏈結串列以「分散儲存 引用連接」的方式換取了 O(1) 的插入與刪除代價是 O(n) 的隨機訪問與更高的記憶體開銷。掌握它的關鍵在於三點理解節點與引用的結構本質、吃透插入刪除時指標操作的順序細節、分清單向/雙向/環形三種型別的適用場景。如果想深入實踐推薦的學習路徑是先運行 linked_list.py 觀察五種操作的實際輸出再對照 linked_list.c 體會手動記憶體管理與 C 語言指標的細節最後透過本章的 練習題 鞏固所學。鏈結串列也是後續學習樹、圖、堆疊、佇列等更高階資料結構的基石打好這一基礎至關重要。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法之鏈結串列全解析：節點結構、五大操作與典型應用
Hello 算法之鏈結串列全解析節點結構、五大操作與典型應用【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo記憶體空間是所有程式的公共資源在複雜的系統執行環境下空閒記憶體往往散落在各處。儲存陣列需要連續記憶體當陣列規模很大時系統可能無法提供如此大的連續空間此時鏈結串列linked list的靈活性優勢便顯現出來。本文以《Hello 算法》繁中版 鏈結串列章節 為主體結合倉庫內 Python、C、C、Go 等語言的完整可執行原始碼系統講解鏈結串列的節點結構、初始化、插入、刪除、訪問、查詢五大操作的時間複雜度以及單向、雙向、環形三種鏈結串列的區別與真實應用場景。讀完本文你將掌握鏈結串列的底層原理、多語言實作範式並能在堆疊、佇列、雜湊表、圖、LRU 快取等場景中自如選用鏈結串列。鏈結串列的本質分散儲存的節點與引用鏈結串列linked list是一種線性資料結構其中的每個元素都是一個**節點node**物件各節點之間透過「引用」相連接。引用記錄了下一個節點的記憶體位址透過它可以從當前節點訪問到下一個節點。這種設計使得各節點可以分散儲存在記憶體各處節點的記憶體位址無須連續——這正是鏈結串列與陣列最根本的區別。關於鏈結串列有幾個基本概念需要明確鏈結串列的首個節點被稱為頭節點最後一個節點被稱為尾節點尾節點指向的是「空」它在 Java、C 和 Python 中分別被記為null、nullptr和None在 C、C、Go 和 Rust 等支援指標的語言中上述「引用」應被理解為「指標」。每個節點都包含兩項資料節點的「值」和指向下一節點的「引用」。也就是說在相同資料量下鏈結串列比陣列佔用更多的記憶體空間因為每個節點除了儲存資料本身還必須額外儲存一個引用指標欄位。節點定義十四種語言一次看懂鏈結串列的核心是節點結構不同語言對「引用」的表述方式各有特色。以下是《Hello 算法》倉庫中節點定義的多語言對照你可以直接複製到自己的專案中使用。 Pythonpython title class ListNode: 鏈結串列節點類別 def __init__(self, val: int): self.val: int val # 節點值 self.next: ListNode | None None # 指向下一節點的引用 Ccpp title /* 鏈結串列節點結構體 */ struct ListNode { int val; // 節點值 ListNode *next; // 指向下一節點的指標 ListNode(int x) : val(x), next(nullptr) {} // 建構子 }; Javajava title /* 鏈結串列節點類別 */ class ListNode { int val; // 節點值 ListNode next; // 指向下一節點的引用 ListNode(int x) { val x; } // 建構子 } C#csharp title /* 鏈結串列節點類別 */ class ListNode(int x) { // 建構子 int val x; // 節點值 ListNode? next; // 指向下一節點的引用 } Gogo title /* 鏈結串列節點結構體 */ type ListNode struct { Val int // 節點值 Next *ListNode // 指向下一節點的指標 } // NewListNode 建構子建立一個新的鏈結串列 func NewListNode(val int) *ListNode { return ListNode{ Val: val, Next: nil, } } Swiftswift title /* 鏈結串列節點類別 */ class ListNode { var val: Int // 節點值 var next: ListNode? // 指向下一節點的引用 init(x: Int) { // 建構子 val x } } JSjavascript title /* 鏈結串列節點類別 */ class ListNode { constructor(val, next) { this.val (val undefined ? 0 : val); // 節點值 this.next (next undefined ? null : next); // 指向下一節點的引用 } } TStypescript title /* 鏈結串列節點類別 */ class ListNode { val: number; next: ListNode | null; constructor(val?: number, next?: ListNode | null) { this.val val undefined ? 0 : val; // 節點值 this.next next undefined ? null : next; // 指向下一節點的引用 } } Dartdart title /* 鏈結串列節點類別 */ class ListNode { int val; // 節點值 ListNode? next; // 指向下一節點的引用 ListNode(this.val, [this.next]); // 建構子 } Rustrust title use std::rc::Rc; use std::cell::RefCell; /* 鏈結串列節點類別 */ #[derive(Debug)] struct ListNode { val: i32, // 節點值 next: OptionRcRefCellListNode, // 指向下一節點的指標 } Cc title /* 鏈結串列節點結構體 */ typedef struct ListNode { int val; // 節點值 struct ListNode *next; // 指向下一節點的指標 } ListNode; /* 建構子 */ ListNode *newListNode(int val) { ListNode *node; node (ListNode *) malloc(sizeof(ListNode)); node-val val; node-next NULL; return node; } Kotlinkotlin title /* 鏈結串列節點類別 */ // 建構子 class ListNode(x: Int) { val _val: Int x // 節點值 var next: ListNode? null // 指向下一個節點的引用 } Rubyruby title # 鏈結串列節點類別 class ListNode attr_accessor :val # 節點值 attr_accessor :next # 指向下一節點的引用 def initialize(val0, next_nodenil) val val next next_node end end 值得注意的是 Rust 的寫法出於所有權與記憶體安全的考量Rust 使用OptionRcRefCellListNode來表達「可空、可共享、可變的節點引用」這與 C 語言中樸素的指標表達形成了鮮明對照也體現了不同語言對同一資料結構的不同落地方式。此外在 Python 倉庫中節點類別定義在 modules/list_node.py並提供了list_to_linked_list將陣列反序列化為鏈結串列與linked_list_to_list將鏈結串列序列化為陣列兩個實用函式方便測試與驗證C 語言的節點結構與建構子則收錄於 utils/list_node.h。鏈結串列常用操作初始化鏈結串列建立鏈結串列分為兩步第一步是初始化各節點物件第二步是構建節點之間的引用關係。初始化完成後就可以從頭節點出發透過next引用依次訪問所有節點。例如建立鏈結串列1 - 3 - 2 - 5 - 4 Pythonpython titlelinked_list.py # 初始化鏈結串列 1 - 3 - 2 - 5 - 4 # 初始化各個節點 n0 ListNode(1) n1 ListNode(3) n2 ListNode(2) n3 ListNode(5) n4 ListNode(4) # 構建節點之間的引用 n0.next n1 n1.next n2 n2.next n3 n3.next n4 Ccpp titlelinked_list.cpp /* 初始化鏈結串列 1 - 3 - 2 - 5 - 4 */ // 初始化各個節點 ListNode* n0 new ListNode(1); ListNode* n1 new ListNode(3); ListNode* n2 new ListNode(2); ListNode* n3 new ListNode(5); ListNode* n4 new ListNode(4); // 構建節點之間的引用 n0-next n1; n1-next n2; n2-next n3; n3-next n4; Javajava titlelinked_list.java /* 初始化鏈結串列 1 - 3 - 2 - 5 - 4 */ // 初始化各個節點 ListNode n0 new ListNode(1); ListNode n1 new ListNode(3); ListNode n2 new ListNode(2); ListNode n3 new ListNode(5); ListNode n4 new ListNode(4); // 構建節點之間的引用 n0.next n1; n1.next n2; n2.next n3; n3.next n4; Cc titlelinked_list.c /* 初始化鏈結串列 1 - 3 - 2 - 5 - 4 */ // 初始化各個節點 ListNode* n0 newListNode(1); ListNode* n1 newListNode(3); ListNode* n2 newListNode(2); ListNode* n3 newListNode(5); ListNode* n4 newListNode(4); // 構建節點之間的引用 n0-next n1; n1-next n2; n2-next n3; n3-next n4; Gogo titlelinked_list.go /* 初始化鏈結串列 1 - 3 - 2 - 5 - 4 */ // 初始化各個節點 n0 : NewListNode(1) n1 : NewListNode(3) n2 : NewListNode(2) n3 : NewListNode(5) n4 : NewListNode(4) // 構建節點之間的引用 n0.Next n1 n1.Next n2 n2.Next n3 n3.Next n4 陣列整體是一個變數例如陣列nums包含元素nums[0]、nums[1]等而鏈結串列是由多個獨立的節點物件組成的。我們通常將頭節點當作鏈結串列的代稱例如以上程式碼中的鏈結串列可記作鏈結串列n0。插入節點O(1) 時間複雜度在鏈結串列中插入節點非常容易。如下圖所示假設想在相鄰的兩個節點n0和n1之間插入一個新節點P只需改變兩個節點引用指標即可時間複雜度為 O(1)。相比之下在陣列中插入元素的時間複雜度為 O(n)在大資料量下效率較低。以 Python 為例插入操作的核心實作如下完整程式見 linked_list.pydef insert(n0: ListNode, P: ListNode): 在鏈結串列的節點 n0 之後插入節點 P n1 n0.next P.next n1 n0.next P這個函式雖然只有三行卻精準地表達了插入的全部語意先記錄後繼節點n1讓P指向n1再讓n0指向P。注意順序不能顛倒——如果先執行n0.next P就會遺失n1的引用。C 語言版本與之完全同構可見 linked_list.cC 版本見 linked_list.cpp。刪除節點只需改變一個引用刪除節點同樣方便只需改變一個節點的引用指標即可。請注意儘管在刪除操作完成後節點P仍然指向n1但實際上走訪此鏈結串列已經無法訪問到P這意味著P已經不再屬於該鏈結串列了。Python 實作如下見 linked_list.pydef remove(n0: ListNode): 刪除鏈結串列的節點 n0 之後的首個節點 if not n0.next: return # n0 - P - n1 P n0.next n1 P.next n0.next n1C/C/Go 版本在刪除後還需要處理記憶體釋放問題C 語言使用free(P)C 使用delete P見 linked_list.cpp而 Go 依賴垃圾回收機制無需手動釋放見 linked_list.go。另外一個實作細節是C 語言中remove與stdio.h的函式名衝突因此在倉庫中 C 版本將刪除函式命名為removeItem見 linked_list.c。訪問節點O(n) 的線性走訪在鏈結串列中訪問節點的效率較低。陣列可以在 O(1) 時間下訪問任意元素鏈結串列則不然——程式需要從頭節點出發逐個向後走訪直至找到目標節點。訪問鏈結串列的第i個節點需要迴圈i - 1輪時間複雜度為 O(n)。Python 實作如下見 linked_list.pydef access(head: ListNode, index: int) - ListNode | None: 訪問鏈結串列中索引為 index 的節點 for _ in range(index): if not head: return None head head.next return head查詢節點線性查詢走訪鏈結串列查詢其中值為target的節點輸出該節點在鏈結串列中的索引。此過程也屬於線性查詢最壞情況下需要走訪完整條鏈結串列。Python 實作如下見 linked_list.pydef find(head: ListNode, target: int) - int: 在鏈結串列中查找值為 target 的首個節點 index 0 while head: if head.val target: return index head head.next index 1 return -1值得一提的是查不到時返回-1是鏈結串列查詢的通用約定在 C、C、Go 等語言的倉庫實作中也保持一致例如 linked_list.go。上述五種操作的完整可執行範例含print_linked_list輸出驗證可以在 linked_list.py 中一鍵執行Python 的鏈結串列列印工具實作於 print_util.py其原理是先將鏈結串列序列化為陣列再以-連接列印。陣列 vs. 鏈結串列兩種相反的儲存策略陣列與鏈結串列採用兩種相反的儲存策略——前者依賴連續記憶體空間後者依賴分散記憶體空間因此各種性質與操作效率也呈現對立特點。下表總結了二者的完整對比陣列鏈結串列儲存方式連續記憶體空間分散記憶體空間容量擴展長度不可變可靈活擴展記憶體效率元素佔用記憶體少、但可能浪費空間元素佔用記憶體多訪問元素O(1)O(n)新增元素O(n)O(1)刪除元素O(n)O(1)這張對比表是選擇資料結構的核心依據若應用以隨機訪問為主如按下標取數、二分查找陣列是首選若應用以頻繁的插入刪除為主如實現佇列、快取淘汰鏈結串列的 O(1) 插入刪除優勢則不可替代。當然實際工程中還需要考慮 CPU 快取友好性、記憶體碎片等因素詳見本章 陣列 與 記憶體與快取 兩篇文檔。常見鏈結串列型別如下圖所示常見的鏈結串列型別包括三種。單向鏈結串列即前面介紹的普通鏈結串列。節點包含值和指向下一節點的引用兩項資料。首個節點稱為頭節點最後一個節點稱為尾節點尾節點指向空None。環形鏈結串列如果令單向鏈結串列的尾節點指向頭節點首尾相接則得到一個環形鏈結串列。在環形鏈結串列中任意節點都可以視作頭節點。雙向鏈結串列與單向鏈結串列相比雙向鏈結串列記錄了兩個方向的引用——節點定義同時包含指向後繼節點下一個節點和前驅節點上一個節點的引用指標。相較於單向鏈結串列雙向鏈結串列更具靈活性可以朝兩個方向走訪但相應地也需要佔用更多記憶體空間。以 Python 與 C 為例雙向鏈結串列的節點定義如下 Pythonpython title class ListNode: 雙向鏈結串列節點類別 def __init__(self, val: int): self.val: int val # 節點值 self.next: ListNode | None None # 指向後繼節點的引用 self.prev: ListNode | None None # 指向前驅節點的引用 Cc title /* 雙向鏈結串列節點結構體 */ typedef struct ListNode { int val; // 節點值 struct ListNode *next; // 指向後繼節點的指標 struct ListNode *prev; // 指向前驅節點的指標 } ListNode; 其餘語言的雙向節點定義C、Java、C#、Go、Swift、JS、TS、Dart、Rust、Kotlin、Ruby均可在 linked_list.md 中查看。此外倉庫的 array_deque.c 與 linkedlist_deque.c 中還有基於雙向鏈結串列實作雙端佇列的完整範例是理解雙向引用實戰價值的絕佳補充材料。鏈結串列典型應用單向鏈結串列通常用於實現堆疊、佇列、雜湊表和圖等資料結構堆疊與佇列當插入和刪除操作都在鏈結串列的一端進行時表現的特性為先進後出FILO對應堆疊當插入操作在鏈結串列的一端進行、刪除操作在另一端進行時表現的特性為先進先出FIFO對應佇列。倉庫中的 linkedlist_stack.c 與 linkedlist_queue.c 正是基於這一特性用鏈結串列實作堆疊與佇列。雜湊表鏈式位址是解決雜湊衝突的主流方案之一在該方案中所有衝突的元素都會被放到一個鏈結串列中。可參見 hash_map_chaining.c 的完整實作。圖鄰接表是表示圖的一種常用方式圖的每個頂點都與一個鏈結串列相關聯鏈結串列中的每個元素代表與該頂點相連的其他頂點。可參見 graph_adjacency_list.c。雙向鏈結串列常用於需要快速查詢前一個和後一個元素的場景高階資料結構在紅黑樹、B 樹中需要訪問節點的父節點這可以透過在節點中儲存一個指向父節點的引用來實現類似於雙向鏈結串列。瀏覽器歷史用戶點擊前進或後退按鈕時瀏覽器需要知道用戶訪問過的前一個和後一個網頁雙向鏈結串列使這種操作變得簡單。LRU 演算法在快取淘汰LRU演算法中需要快速找到最近最少使用的資料同時支援快速新增和刪除節點雙向鏈結串列非常合適。環形鏈結串列常用於需要週期性操作的場景例如作業系統的資源排程時間片輪轉排程演算法這是一種常見的 CPU 排程演算法需要對一組程序進行迴圈——每個程序被賦予一個時間片用完後 CPU 切換到下一個程序。這種迴圈操作可以透過環形鏈結串列來實現。資料緩衝區在某些資料緩衝區的實作中例如音訊、影片播放器資料流會被分成多個緩衝塊並放入一個環形鏈結串列以實現無縫播放。小結與學習路徑鏈結串列以「分散儲存 引用連接」的方式換取了 O(1) 的插入與刪除代價是 O(n) 的隨機訪問與更高的記憶體開銷。掌握它的關鍵在於三點理解節點與引用的結構本質、吃透插入刪除時指標操作的順序細節、分清單向/雙向/環形三種型別的適用場景。如果想深入實踐推薦的學習路徑是先運行 linked_list.py 觀察五種操作的實際輸出再對照 linked_list.c 體會手動記憶體管理與 C 語言指標的細節最後透過本章的 練習題 鞏固所學。鏈結串列也是後續學習樹、圖、堆疊、佇列等更高階資料結構的基石打好這一基礎至關重要。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考