両者は列を格納しますが、逆のコストプロフィールを持っています。配列は連続したメモリでO(1)のインデックスアクセスが可能です。一方、連結リストは散在したノードをポインタで結合したもので、末尾でのO(1)の挿入/削除が可能ですがインデックスアクセスはできません。
両者は列を格納しますが、逆のコストプロフィールを持っています。配列は連続したメモリでO(1)のインデックスアクセスが可能です。一方、連結リストは散在したノードをポインタで結合したもので、末尾でのO(1)の挿入/削除が可能ですがインデックスアクセスはできません。
| 操作 | 配列（動的） | 連結リスト |
|---|
| インデックスでのアクセス | O(1) | O(n) |
| 検索 | O(n) | O(n) |
| 先頭での挿入/削除 | O(n) | O(1) |
| 末尾での挿入/削除 | O(1) 償却 | O(1) テールポインタ付き |
| 中間での挿入/削除 | O(n) | O(n) 探索 + O(1) スプライス |
| メモリオーバーヘッド | 低い | 高い（ノード当たりポインタ） |
| キャッシュの局所性 | 優秀 | 悪い |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
実際には、典型的なサイズではキャッシュの局所性がBig-Oの差を圧倒するため、配列がほとんどの場合に勝ります。
両者を知っていれば、インタビューで盲目的にデフォルトを選ぶのではなく、自分の選択を正当化できます。また、「O(1)の挿入」が連続配列を上回ることがめったにない理由を説明できます。