Array vs Linked List

術語庫 — 點擊任一術語查看解釋

索引 index 元素 element 隨機存取節點 node 指標 pointer 頭節點 head NULL 時間複雜度循序存取

📍 這個頁籤的學習路徑建議照順序走，效果最好

先說直覺

音樂清單要常常新增刪歌，你覺得哪個比較好用？

↓

Array

操作 Array

試試插入、刪除、存取
觀察元素如何搬移

↓

操作 Linked List

同樣的操作，觀察指標如何改變

↓

🔮

預測再驗證

操作前先猜移動幾步
猜錯最有印象！

↓

寫下反思

用自己的話說出
兩者根本差異

💡 操作建議：Array 和 Linked List 同時進行相同操作（如都插入位置 2），才能直接看出差異！

Array（陣列）

🎬 電影院座位比喻連續的座位，要加人進中間得叫大家都往後移一格。

Q. 🔮 預測插入時需要移動幾個元素？（先猜再按插入）

位置值

等待你的操作...

等待操作...

Linked List（鏈結串列）

🗺️ 尋寶遊戲比喻每個節點帶著「下一個在哪」，插入新節點只要改指標，不用搬別人。

Q. 🔮 預測插入時需要走幾步找到位置？（先猜再按插入）

位置值

等待你的操作...

等待操作...

❓ LL 也有「第幾個」的概念嗎？
有的，但 LL 沒有捷徑（沒有 index 公式）。
要找第 n 個節點，必須從 head 走 n 步（O(n)）。
所以 LL 的「插入/刪除」實際上是：先走 O(n) 找位置，再花 O(1) 改指標。
LL 的優勢是「改指標那一步不需要搬移其他節點」，Array 則是每個元素都要搬。

💭 反思一下後設認知練習

操作完之後，試著用自己的話回答：
Array 和 Linked List 在「插入」這件事上，根本差異是什麼？

REFERENCE ANSWER

Array：必須把後面所有元素物理搬移一格，時間複雜度 O(n)。
Linked List：只修改前後兩個節點的指標，本身 O(1)；但需先從 head 走到位置，O(n)。
根本差異：Array 慢在「搬移資料」；Linked List 慢在「尋找位置」，兩者慢的原因不同。

你覺得自己理解了多少？

時間複雜度一覽

操作	Array	Linked List	誰快？
隨機存取（第 i 個）	O(1)	O(n)	🏆 Array
開頭插入	O(n) 全部後移	O(1)	🏆 Linked List
中間插入	O(n)	O(n)+O(1)	🤝 差不多
尾端插入	O(1)*	O(n)或O(1)**	⚡ Array 略勝
搜尋特定值	O(n)	O(n)	🤝 一樣
記憶體用量	緊湊	多出指標	🏆 Array

* 未超出容量　** 若有 tail pointer

選一個操作，看兩者速度差異（n=100）

Array 耗時

O(1)

Linked List 耗時

O(n)

📍 隨機存取：Array 直接計算記憶體位址，一步到位。Linked List 要從 head 走 n 步。

💭反思一下後設認知練習

看完效能比較，用一句話總結：什麼情況選 Array，什麼情況選 Linked List？

REFERENCE ANSWER

選 Array：頻繁隨機存取、資料量已知、希望省記憶體。
選 Linked List：頻繁插入/刪除、資料量動態變化。
口訣：「讀多選 Array，改多選 Linked List。」

你覺得自己理解了多少？

💡 記憶體到底長什麼樣？Array 的資料住在「連棟公寓」——地址是連續的，CPU 找起來超快。
Linked List 的資料可能住在城市各地——每棟還要貼一張「下一棟在哪」的紙條。

Array 記憶體配置

每個元素占相同大小、地址連續

MEMORY ADDRESS →

✅ 知道 index → 直接算出地址
公式：位址 = 起始 + index × 元素大小

Linked List 記憶體配置

節點散落各處，靠指標串起來

MEMORY ADDRESS →

⚠️ 每個節點 = 資料 + 指標（多佔空間）
data | next → 指向下一節點

💭反思一下後設認知練習

從記憶體角度解釋：為什麼 Array 能「一步」存取第 i 個，而 Linked List 必須「一步一步走」？

REFERENCE ANSWER

Array：元素連續排列，大小固定，用公式 起始+index×大小 直接計算位址，O(1)。
Linked List：節點散落各處，只能從 head 逐一跟隨指標，無法跳過，O(n)。
根本原因：Array 靠「數學計算」；Linked List 靠「逐節跟隨指標」。

你覺得自己理解了多少？

🎯 挑戰：每個情境，你會選哪個？點選一張情境卡片，再點 Array 或 Linked List，立刻得到回饋！支援拖曳。

得分0 / 8

📋 情境 — 點選或拖曳

📦 放到這裡

Array

連續座位

Linked List

尋寶串鏈

📊 你的學習前後對比

開始前的直覺判斷

—

連連看實際得分

—

📦 ArrayVSLinked List

Array（陣列）

Linked List（鏈結串列）

選一個操作，看兩者速度差異（n=100）

Array 記憶體配置

Linked List 記憶體配置

📊 你的學習前後對比

全部答對！