配列 vs 連結リスト
このトピックを修了すると
配列と連結リストのメモリ構造の違いを説明でき、状況に応じてどちらを選択すべきかを判断できるようになります。
配列 — 連続したメモリ
配列（Array）は、データをメモリ上に連続して格納します。
text
メモリ番地: 100 104 108 112 116
+----+----+----+----+----+
値: | 10 | 20 | 30 | 40 | 50 |
+----+----+----+----+----+
インデックス: 0 1 2 3 4利点は、インデックスによる即時アクセスが可能であることです。
python
arr = [10, 20, 30, 40, 50]print(arr[3]) # 40 — 即時アクセス (O(1))「3番目の要素」と言えば、開始アドレス + (3 × サイズ) = その場所がすぐにわかります。要素数が多くても、一度に検索できます。
配列の弱点：挿入と削除
text
[10, 20, 30, 40, 50] にインデックス 1 に 15 を挿入するには？
1. 20, 30, 40, 50 をすべて 1 つずつ後ろに移動
2. 空いた場所に 15 を挿入
[10, 15, 20, 30, 40, 50]データが 100 万個の場合、一番最初の要素に挿入すると、100 万個のデータをすべて移動させる必要があります。
連結リスト — 散在したメモリ
連結リスト（Linked List）は、各データが次のデータの場所を記憶します。
text
[10|→] → [20|→] → [30|→] → [40|→] → [50|∅]
各ノード = 値 + 次のノードのアドレス（ポインタ）メモリ上に連続して配置されている必要はありません。各ノードが「次はどこか」を知っていれば良いのです。
連結リストの利点：挿入と削除
text
[10|→] → [20|→] → [30|→] で、20 の後に 25 を挿入：
1. 新しいノード [25|→] を作成
2. 20 のポインタを 25 に、25 のポインタを 30 に変更
[10|→] → [20|→] → [25|→] → [30|→]他のノードを移動させる必要はありません。ポインタを 2 つ変更するだけで完了です。O(1)。
連結リストの弱点：アクセス
python
# 「3 番目の値は？」# 配列: arr[3] → 即時 (O(1))# 連結リスト: 最初から 1→2→3 とたどる必要がある (O(n))インデックスがないため、n 番目の値を見つけるには、最初から n 回たどる必要があります。
比較まとめ
| 演算 | 配列 | 連結リスト |
|---|---|---|
| インデックスアクセス | O(1) 即時 | O(n) 走査が必要 |
| 検索 | O(n) 走査 | O(n) 走査 |
| 先頭への挿入 | O(n) すべて移動 | O(1) ポインタ変更 |
| 末尾への挿入 | O(1) 末尾に追加 | O(1) 末尾ポインタがあれば |
| 中間への挿入 | O(n) 移動 | O(1) ポインタ変更 |
| メモリ | 連続が必要 | 散らされても良い |
選択基準
| 状況 | 推奨 |
|---|---|
| インデックスによる頻繁なアクセス | 配列 |
| 頻繁な挿入/削除 | 連結リスト |
| サイズが頻繁に変化 | 連結リスト |
| メモリ効率が重要 | 配列（ポインタのオーバーヘッドがない） |
| キャッシュの効率が必要 | 配列（連続したメモリ） |
実際には、ほとんどの場合、配列（Python の list、JavaScript の Array）を使用します。 現代の言語の動的配列は、サイズ調整も自動で行われ、CPU キャッシュにも有利です。連結リストは、特殊な状況（キュー、スタックの実装、大規模な挿入/削除）で使用します。