配列と連結リストの違い：読み出し・挿入と削除・メモリの並び・キャッシュ・計算量を比較
配列は、同じ型の要素をメモリ上に隙間なく連続して並べ、要素番号(添字)から位置を計算して、どの要素も一定の時間で読み書きできるデータ構造です。連結リストは、各要素が値と次の要素の位置を指すポインタを持ち、それをたどってつながるデータ構造で、要素はメモリ上の離れた場所に置けます。配列は読み出しが速い代わりに、途中への挿入や削除では後ろの要素をずらす必要があります。連結リストは、位置が分かっていればポインタの付け替えだけで挿入や削除ができる代わりに、i番目の要素を読むには先頭から順にたどる必要があります。番号で読むことが多いなら配列、決まった位置での挿入や削除が多いなら連結リスト、というのが基本の使い分けです。
| 項目 | 配列 | 連結リスト |
|---|---|---|
| メモリ上の並び方 | 要素が、連続した領域に隙間なく並ぶ | 要素はばらばらの場所に置かれ、ポインタでつながる |
| i番目の要素の読み出し | O(1)。先頭の番地 + i × 要素の大きさ で位置を計算できる | O(n)。先頭から i 回ポインタをたどる |
| 値の探索 | 整列していなければ O(n) の線形探索。整列済みなら、二分探索で O(log n) | 整列していても O(n)。途中の要素へ一度に移れないので、二分探索は使えない |
| 途中への挿入・削除 | O(n)。後ろの要素を1つずつずらす | 挿入する位置(直前の要素)が分かっていれば O(1)。ポインタの付け替えだけで済む |
| 末尾への追加 | 空きがあれば O(1)。可変長配列で容量を2倍ずつ増やす方式では、ときどき全体をコピーするが、平均すると O(1)(償却) | 末尾の要素を指すポインタを持っていれば O(1) |
| 大きさの変更 | 固定長の配列は、作るときに大きさを決める。広げるには、新しい領域を確保してコピーする | 要素ごとに領域を確保するので、必要な分だけ増やせる |
| 使うメモリ | 要素の分だけで済む(可変長配列では、予備の容量を持つ) | 要素ごとに、ポインタの分が余計にかかる(双方向リストなら2つ分) |
| キャッシュの効きやすさ | 効きやすい。連続して並ぶので、順に読むとキャッシュやプリフェッチがよく働く | 効きにくい。要素が散らばりやすいので、同じ O(n) の走査でも、配列より大幅に遅くなることがある |
| 主な用途 | 添字で読み書きする表、行列や画像、ソートや二分探索の対象、スタックやキューの実装 | 挿入や削除が頻繁な列、ハッシュテーブルのチェイン法、空き領域の管理 |
数値は代表的な目安で、世代や製品によって異なります。