Please enable JavaScript.
Coggle requires JavaScript to display documents.
串列（List） - Coggle Diagram
串列（List）
實際應用案例或生活中的例子
插入排序法 (Insertion Sort)
凱薩密碼 (Caesar Cipher)
遊戲高分榜 (Game High Scores)
圓桌公平排程 (Round-Robin Scheduling)
各主題的基本定義與特性
抽象資料型態 (Abstract Data Type, ADT)
定義
ADT 是一種對資料型態的邏輯性描述，它只定義了資料結構「做什麼」（介面/API），而不涉及底層「怎麼做」（實作）
特性
如同汽車的黑盒子概念，使用者只需透過方向盤與踏板（介面）來操控，而不需要理解引擎內部如何燃燒（實作）
陣列與循序結構 (Array-Based Sequences)
低階陣列 (Low-Level Array)
在記憶體中是一塊連續的空間，每個儲存單元（儲存格）的大小皆相同，因此支援 O(1) 的常數時間隨機存取
參照陣列 (Referential Array)
Python 的 list 與 tuple 屬於此類。陣列中不直接存放物件資料，而是存放指向物件的記憶體位址（指標
動態陣列 (Dynamic Array)
Python 的 list 具有動態增長特性 。系統會預先分配超出目前所需的容量，當陣列填滿時，會自動建立一個更大的新陣列（通常是原來的 2 倍或 1.125 倍），將舊資料複製過去，並回收舊陣列
緊湊陣列 (Compact Array)
Python 的 array 模組即是此實作，直接在連續空間內儲存原始的 C 語言基本資料型態（如整數、浮點數）
鏈結串列 (Linked List)
定義
鏈結串列是一種由多個節點（Node）組成的線性資料結構，節點在記憶體中是不連續的，透過指標（Pointer）相互串聯。每個節點包含兩個部分：實際的資料（Data）與指向下一個節點的參照（Next）
特性
動態分配記憶體，不需要預先指定大小 ；在已知位置進行插入或刪除非常高效，但無法像陣列一樣進行隨機存取
單向鏈結串列 (Singly Linked List)
節點僅包含指向 Next 的單向指針，尾節點（Tail）的 Next 為 None
循環鏈結串列 (Circular Linked List)
尾節點的 Next 指針不為 None，而是重新指向頭節點（Head），形成一個無始無終的環
雙向鏈結串列 (Doubly Linked List)
節點同時包含指向下一個（Next）與上一個（Prev）節點的參照，允許雙向遍歷
常見操作與演算法
串列基礎操作
get_item(L, i)
set_item(L, i, e)
append(L, e)
insert(L, index, e)
串列反轉演算法 (List Reversal)
迭代法 (Iterative Approach)
時間複雜度 O(n)，空間複雜度 O(1)
遞迴法 (Recursive Approach)
時間複雜度O(n)，但因為需要隱式呼叫棧，空間複雜度退化為O(n)
鏈結串列的節點操作演算法
尾部插入
必須先從 Head 開始向後遍歷，直到找到 Next 為 None 的尾節點，再將其 Next 指向新節點（O(n)）
指定位置插入/刪除
遍歷至目標 index 的前一個節點（i-1）
頭部插入
建立新節點，將其 Next 指向現有的 Head，再將 Head 更新為新節點（O(1))
各單元實作 Lab 中學到的內容與心得
凱薩密碼加解密實作
鏈結串列（Linked List）底層純手工實作
Rich 終端機美化套件應用
不同資料結構之間的關聯性
陣列（Array） vs. 鏈結串列（Linked List）
記憶體布局
陣列使用集中、連續的記憶體；鏈結串列則使用分散的節點
存取與修改成本
陣列支援 O(1) 按索引存取，但插入與刪除需要搬移元素，成本為 O(n)
鏈結串列按索引存取需要遍歷，成本為 O(n)，但在已知節點位置插入或刪除只需修改指針，成本為 O(1)
基礎結構衍生的高階 ADT
Deque（雙端隊列）
使用帶有哨兵節點的雙向鏈結串列實作，可以讓前端與後端的增刪操作均達到 Worst-Case O(1) 效能，優於陣列動態調整大小所帶來的時間波動
Stack（堆疊）與 Queue（隊列）
Stack 在 Head 進行 Push 與 Pop，所有操作皆為 O(1)
Queue 則維護 Head 與 Tail 兩個指針，從 Tail 進行 Enqueue，從 Head 進行 Dequeue，同樣可達到 O(1) 效能