資料結構與演算法
與陣列相比，鏈結串列（各元素持有指向下一個元素位置之指標的串列）的特徵，下列何者正確？
- A若已知插入位置的前一個元素，只要改接指標就能插入，不必移動其他元素；但要讀取第 i 個元素，必須從開頭依序走訪
- B可以計算出第 i 個元素的位置，因此任何元素都能以固定時間 O(1) 讀取
- C元素在記憶體中緊密連續排列，因此依序讀取時快取與預取容易發揮效果
查看答案與解析
正確答案：A. 若已知插入位置的前一個元素，只要改接指標就能插入，不必移動其他元素；但要讀取第 i 個元素，必須從開頭依序走訪
在鏈結串列中，只要知道插入或刪除的位置，改寫前後的指標即可，只需 O(1)。另一方面，要讀取第 i 個元素必須從開頭追蹤 i 次指標，需要 O(n)。陣列可由起始位址與元素大小算出第 i 個元素的位址，因此能以 O(1) 讀取，但在中間插入時需要把後面的元素往後挪，要花 O(n)。此外，陣列的元素連續排列，快取與預取容易發揮效果；鏈結串列的節點容易散落在記憶體各處，即使同樣是 O(n) 的走訪，也可能慢上許多。
- A. 正確。插入與刪除只需改接指標，但依位置讀取時要從開頭走訪。
- B. 以計算求出位址並以 O(1) 讀取，是陣列的特徵。
- C. 元素連續排列、快取容易發揮效果的是陣列。鏈結串列的元素容易分散。