2.3 兩者的取捨與應用#

概念說明#

陣列與鏈結串列代表兩種記憶體哲學：連續與分散。要把誰用在什麼地方，關鍵是看操作的比例與模式。

考量	動態陣列	鏈結串列
隨機存取第 i 個	O(1)	O(n)
頭/尾增刪	尾 O(1)、頭 O(n)	皆 O(1)（雙向）
中間插入刪除	O(n) 搬移	已知位置 O(1)
搜尋	未排序 O(n)、可二元搜尋 O(log n)	一律 O(n)
快取表現	極佳（連續記憶體）	差（節點散落各處）
額外空間	約 0~100% 浪費	每元素多 1~2 個指標

許多人以為「中間插入多就用串列」，但實務上未必：即使插入次數多，串列要先花 O(n) 找到位置，總成本仍是 O(n)；而陣列的搬移因為快取友善、又只是資料複製，常數很小。Python、Java 等語言的標準函式庫都傾向用動態陣列當預設，正反映了這一點。

什麼時候串列真的贏？#

需要 O(1) 刪除已知節點，且可以從別處拿到節點參考——例如 LRU 快取：雜湊表存「鍵 → 節點」，串列負責維持使用順序，命中時把節點搬到最前面，兩者都是 O(1)。
兩端頻繁操作：collections.deque 底層就是「區塊陣列串成的雙向串列」，兼得兩端 O(1) 與大致 O(1) 的索引。
結構隨時重組、無法預估大小：如自由串列（free list）、垃圾回收的物件追蹤。
串接（splice）：把整段節點直接搬家，O(1) 完成兩串列合併。

實作：LRU 快取（雜湊表 + 雙向串列）#

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.od = OrderedDict()   # 有序：最舊在最前

    def get(self, key):
        if key not in self.od:
            return -1
        self.od.move_to_end(key)  # 剛用過 → 標記為最新
        return self.od[key]

    def put(self, key, value):
        if key in self.od:
            self.od.move_to_end(key)
        self.od[key] = value
        if len(self.od) > self.cap:
            self.od.popitem(last=False)  # 逐出最舊

cache = LRUCache(2)
cache.put(1, "A")
cache.put(2, "B")
print(cache.get(1))   # 1 → 命中，1 變最新
cache.put(3, "C")     # 容量滿，逐出最舊的 2
print(cache.get(2))   # -1
print(cache.get(3))   # "C"

OrderedDict 底層就是雜湊表加雙向串列的組合，move_to_end 與 popitem 都是 O(1)——這正是「串列強項」的最佳示範。

複雜度分析#

LRU 快取的 get 與 put 都是 O(1)：雜湊表負責定位，雙向串列負責順序維護。空間為 O(capacity)。這個例子揭示了一個重要思維——組合兩個結構，各取所長，第10章會再深入。

練習#

某程式對 100 萬筆資料反覆做「隨機讀取 + 偶爾尾端新增」，該用陣列還是串列？若改成「反覆從頭刪除」呢？
實作 deque 的簡化版：用「多個小區塊（每區塊 64 格）串成雙向串列」，支援 append、appendleft、pop、popleft 全部 O(1)。
為什麼演算法課本常用鏈結串列，工程實務卻少用？從快取局部性與操作模式兩個角度討論。