第2章 陣列與鏈結串列#

本章目標#

• 理解動態陣列的擴容機制與攤攤分析。
• 能用 Python 實作單向與雙向鏈結串列。
• 學會依操作型態在陣列與串列之間做出取捨。

章前言#

陣列與鏈結串列是最基本、也最能體現「取捨」精神的兩種線性資料結構。它們都是「把一串資料排成一列」，但內部安排截然不同：陣列把資料連續放在記憶體裡，靠「起點 + 位移」直接計算出任何元素的位置，因此隨機存取是 O(1)，但插入刪除必須搬動後方元素；鏈結串列把資料分散成一個個節點，每個節點記住下一個（或上一個）節點的位置，因此在已知位置上插入刪除只需改幾個指標，是 O(1)，但想存取第 k 個元素就必須從頭一個個走過去，是 O(n)。

這一章會先拆解 Python list 底下的動態陣列：容量滿了怎麼加倍、為什麼 append 是攤攤 O(1)、為什麼 insert(0, x) 那麼慢。接著親手實作單向與雙向鏈結串列，處理指標操作的各種細節（頭節點、邊界、反轉）。最後把兩者放上同一張表格比較，討論實務上（例如編輯器的游標操作、作業系統的串流緩衝）各自適合的場景。

學完本章，你應該建立一個終身受用的直覺：「連續」換來快速隨機存取與快取友善，「分散」換來彈性的插入刪除。這個直覺在後續章節（跳躍串列、B 樹、環形緩衝）會不斷重現。