Day 2：陣列 vs 鏈結串列
2026-05-03·
#後醫#計概
核心觀念
資料結構 = 整理資料的方式。選用看「最常做什麼操作」。
圖書館比喻
- 書架法(連續、編號) → 陣列(Array)
- 藏寶圖法(分散、指標) → 鏈結串列(Linked List)
對照總表
| 比較項 | 陣列 | 鏈結串列 |
|---|---|---|
| 記憶體配置 | 連續 | 分散(用指標串) |
| 大小 | 固定 | 可變 |
| 索引存取 | O(1) ⚡ | O(n) 🐢 |
| 中間插入/刪除 | O(n) 🐢 | O(1) ⚡ |
| 快取效率 | 高 | 低 |
Big O 入門
| 記號 | 意思 |
|---|---|
| O(1) | 不管資料多少,都一樣快 ⚡ |
| O(n) | 資料越多越慢,跟資料量成正比 🐢 |
進階:Python list
動態陣列(Dynamic Array),不是鏈結串列
list[5]是 O(1) → 只有陣列做得到list.append()→ 平均 O(1) = 攤銷 O(1)
一句話總結
陣列像書架(連續、編號好找),鏈結串列像藏寶圖(分散、好插好刪)。