連結リスト
まず結論
連結リストはノード（データ＋次のノードへのポインタ）を鎖のようにつないだデータ構造です。配列と異なり挿入・削除がO(1)でできますが、特定要素へのランダムアクセスはO(n)になります。
連結リストのしくみ
各ノードは「データ」と「次のノードへのポインタ（参照）」を持ちます。
先頭
↓
↓
→
→
→
各ノード: [データ | 次のノードへのポインタ] ／ 最後のノードのポインタはNULL
挿入・削除がO(1)な理由
AとBの間に「X」を挿入するには？
① 新しいノードXを作る
② XのポインタをBに向ける
③ AのポインタをXに変える
→ ポインタを2か所変えるだけ！要素をずらす必要がない → O(1)
① 新しいノードXを作る
② XのポインタをBに向ける
③ AのポインタをXに変える
→ ポインタを2か所変えるだけ！要素をずらす必要がない → O(1)
挿入後：A → X → B → C → D
→
→
… →
配列との比較：アクセス
配列: O(1)（インデックスで直接）
連結リスト: O(n)（先頭から順にたどる必要）
配列との比較：挿入・削除
配列: O(n)（要素をずらす必要）
連結リスト: O(1)（ポインタ付け替えのみ）
単方向リストと双方向リスト
単方向リスト
ポインタが次のノードのみを指す。シンプルだが前には戻れない。
A → B → C → NULL
双方向リスト
前後両方のノードへのポインタを持つ。前後を自由に移動できる。
NULL ⇔ A ⇔ B ⇔ C ⇔ NULL
🎯 試験での出方
- 「連結リストの要素追加の計算量」→ O(1)（ポインタの付け替えだけ）
- 「連結リストでn番目の要素にアクセスする計算量」→ O(n)（先頭からたどる）
- 配列 vs 連結リストの特徴比較問題がよく出る
- ポインタの付け替えによる挿入・削除の手順を理解しておく
⚠️ よくある間違い
- 「連結リストは全ての操作が速い」→ ✗ ランダムアクセス（n番目の要素取得）はO(n)
- 「配列の方が常に優れている」→ ✗ 挿入・削除が多い場合は連結リストが有利
- 「ポインタ（参照）はデータそのもの」→ ✗ ポインタは次のノードの場所を指す「住所」
✍️ 確認クイズ
Q1. 連結リストにおいて、先頭への要素挿入の計算量はどれか。
✅ 正解は①。連結リストへの挿入はポインタを付け替えるだけなのでO(1)。ただし特定位置まで移動する時間は別途O(n)かかる場合があります。
Q2. 連結リストと配列を比較したとき、連結リストの方が優れているのはどれか。
✅ 正解は②。連結リストの挿入・削除はO(1)（ポインタ付け替え）で配列のO(n)より優れています。ランダムアクセスは配列のO(1)に対し連結リストはO(n)です。
Q3. 連結リストの各ノードが持つ情報として適切なものはどれか。
✅ 正解は③。連結リストの各ノードは「データ（値）」と「次のノードへのポインタ（参照・住所）」を持ちます。これでノードがチェーン状につながります。
Q4. 単方向リストと双方向リストの違いとして正しいものはどれか。
✅ 正解は②。単方向リストは各ノードが「次→」のポインタのみを持ち前には戻れません。双方向リストは「←前」「次→」の両方のポインタを持つため前後自由に移動できます。双方向リストはメモリを多く使いますが、柔軟な操作が可能です。
Q5. 連結リストのn番目の要素にアクセスする計算量はどれか。
✅ 正解は②。連結リストはメモリ上に連続していないため、n番目の要素にアクセスするには先頭ノードから「次→」を辿って1つずつ進む必要があります。これがO(n)。対して配列はa[n]で直接アクセスできるためO(1)。連結リストの弱点がランダムアクセスの遅さ（O(n)）です。
Sponsor Link