鏈表（Linked List）：動態數據結構的基石
鏈表（Linked List） 鏈表是一種常見的線性數據結構，它通過「節點」將數據元素順序連接。與數組不同，鏈表中的元素在內存中不必連續存儲，而是通過指針或引用彼此相連。 鏈表的基本結構 每個鏈表節點包含兩部分： 數據域：存儲節點的值 指針域：指向下一個節點的引用 +-------------+ +-------------+ +-------------+ | 數據 | 下一個 |--->| 數據 | 下一個 |--->| 數據 | 下一個 |--->NULL +-------------+ +-------------+ +-------------+ 鏈表的種類 1. 單向鏈表（Singly Linked List） 每個節點只有一個指向下一節點的指針。 Head -> [Data|Next] -> [Data|Next] -> [Data|Next] -> NULL 2. 雙向鏈表（Doubly Linked List） 每個節點有兩個指針，分別指向前一個和後一個節點。 NULL <- [Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next] -> NULL ^ | Head 3. 循環鏈表（Circular Linked List） 最後一個節點指向第一個節點，形成一個環。 +------------------------------------------+ | | v | Head -> [Data|Next] -> [Data|Next] -> [Data|Next] 鏈表操作的時間複雜度 操作 單向鏈表 雙向鏈表 訪問元素 O(n) O(n) 在頭部插入 O(1) O(1) 在尾部插入 O(n)/O(1)* O(1) 在中間插入 O(n) O(n) 刪除節點 O(n) O(1)** * 如果保存了尾指針 ** 已知節點位置的情況下 ...