連結リスト vs 配列：パフォーマンス比較とトレードオフ
アクセス時間、挿入、削除、メモリ使用量、キャッシュパフォーマンスにわたって連結リストと配列を比較します。最適なパフォーマンスのためにいつ各データ構造を使用すべきかを学びます。
Linked List
詳細な説明
連結リスト vs 配列
連結リストと配列の選択は、データ構造設計における最も基本的な決定の一つです。それぞれに異なる強みと弱みがあります。
時間計算量の比較
| 操作 | 配列 | 連結リスト |
|---|---|---|
| インデックスによるアクセス | O(1) | O(n) |
| 検索（未ソート） | O(n) | O(n) |
| 先頭への挿入 | O(n) | O(1) |
| 末尾への挿入 | O(1)* | O(1)** |
| 中間への挿入 | O(n) | O(1)*** |
| 先頭の削除 | O(n) | O(1) |
| 末尾の削除 | O(1) | O(n)**** |
| 中間の削除 | O(n) | O(1)*** |
メモリ使用量
配列： 連続したメモリブロック、要素ごとのポインタオーバーヘッドなし。 連結リスト： 非連続（メモリ上に散在）、ノードごとに追加のポインタ。
キャッシュパフォーマンス
これが実際にはしばしば決定的な要因となります：
- 配列は優れた空間的局所性を持つ。要素がメモリ上で隣接しているため、CPUキャッシュが一度に複数の要素をロード。
- 連結リストはキャッシュパフォーマンスが悪い。ノードがメモリ上のどこにでもあり得るため、ほぼすべてのアクセスでキャッシュミスが発生。
実践的な現実
ほとんどの実世界のシナリオでは、キャッシュ効果により配列（およびそのArrayList、Vec、sliceなどの動的バリアント）が連結リストを上回ります。連結リストが輝くのは主にLRUキャッシュのような特殊なシナリオで、O(1)の任意削除が重要な場合です。
ユースケース
この比較の理解はシステム設計やコーディング面接に不可欠です。面接官はしばしば候補者にデータ構造の選択を正当化するよう求めます。配列がキャッシュパフォーマンスで勝ち、連結リストが挿入/削除の柔軟性で勝つことを知っていることは、コンピュータアーキテクチャとアルゴリズムのトレードオフへの深い理解を示します。