04 リスト（list）
【知識】
データをポインタ（次のデータの位置）でつないだ構造。各要素は「セル」と呼ばれ、
データ部＋ポインタ部からなる。
単方向（片方向）リスト
head→
A●→
B●→
C●→
D●→
E✕
NULL
各セル＝データ部＋ポインタ部（●＝次のセルを指す）。末尾のポインタは NULL。
双方向（両方向）リスト … 前後どちらへもたどれる
head⇄
A⇄
B⇄
C⇄
D⇄
E⇄
tail
各セルが前後2つのポインタをもつ。環状リストでは末尾のポインタが先頭を指す。
- 環状（循環）リスト：末尾のポインタが先頭を指す。単方向・双方向どちらもある。
配列との違い（超重要）
| 操作 | 配列 | リスト |
|---|
| 参照（ランダムアクセス） | 速い（添字で一発） | 遅い（先頭からたどる） |
| 挿入・削除 | 遅い（要素をずらす） | 速い（ポインタ数個の付け替え） |
ひとことで：配列は「読むのが得意」、リストは「入れ替えが得意」。
【演習】理解度チェック
Q1（H21春 問6）★配列 vs 連結リスト・頻出
配列と比較した場合の連結リストの特徴として、適切なものはどれか。
解説を表示
正解：エ
- ア×：更新対象までたどるので配列より遅い。
- イ×：後ろをずらすのは配列の欠点。リストは付け替えで速い。
- ウ×：連結リストはランダムアクセス不可（先頭から順にたどる）。
- エ○：挿入はポインタ数個の書き換えのみで速い。
過去問道場で確認
Q2（H24春 問7）★単方向リストのポインタ参照回数
先頭ポインタと末尾ポインタをもつ単方向リストで、ポインタを参照する回数が最も多い操作はどれか。
解説を表示
正解：エ
ポイントは「単方向リストは逆向きにたどれない」こと。
- ア（先頭に挿入）：1回
- イ（先頭を削除）：1〜2回
- ウ（末尾に挿入）：末尾ポインタから1回で届く
- エ（末尾を削除）：末尾の1つ前のセルを書き換える必要があるが、逆にたどれないので先頭から順に全部たどる。→ 参照回数がデータ数ぶんかかり最多。
▼速解法：「単方向リストで末尾側をいじる／1つ前が必要な操作」は、先頭から全部たどるので一番重い。
過去問道場で確認
Q3 ★挿入で書き換えるポインタの数
あるノードの直後に新しいノードを1個挿入する。書き換える（付け替える）ポインタの数は、単方向リストと双方向リストでそれぞれいくつか。
解説を表示
正解：ウ（単方向 2本／双方向 4本）
単方向リスト：2本
- 新ノードの next ← 後続ノード
- 前ノードの next ← 新ノード
双方向リスト：4本
- 新ノードの next ← 後続ノード
- 新ノードの prev ← 前ノード
- 前ノードの next ← 新ノード
- 後続ノードの prev ← 新ノード
ポイント：要素の移動は一切不要（配列なら後ろを全部ずらす）。だからリストは挿入・削除が速い。
▼ 解説つきの類題を探す：過去問道場・分野別「データ構造」
Q4 ★構造の使い分け
次の2つの用途に向くデータ構造の組み合わせとして適切なものはどれか。
① 先頭・途中への挿入や削除が頻繁に起こる
② 「n 番目の要素」を何度もランダムに読み出す
解説を表示
正解：イ
- ① リスト（ポインタの付け替えだけで済む）
- ② 配列（添字で一発アクセス O(1)）
「入れ替えが多い＝リスト、読み出しが多い＝配列」で判断する。
▼ 解説つきの類題を探す：過去問道場・分野別「データ構造」
Q5 ★ノード挿入のポインタ付け替え
次の単方向リストで、ノード B と C の間に新しいノード X を挿入したい。付け替える（設定する）ポインタの組合せとして正しいものはどれか。
head→
A●→
B●→
C●→
D✕NULL
挿入するノード X を、B と C の間に入れる。
解説を表示
正解：ア
単方向リストの挿入はポインタ2本の付け替えだけ（要素の移動は不要）。順番も大事：
- まず X の next ← C（C への道を X に持たせる）
- 次に B の next ← X（B の行き先を X に変える）
順番のワナ：先に「B の next ← X」をすると、元の C の位置（B の next）が上書きされて C 以降を見失う。だから X の next ← C を先に。
ウは A を、エは D を書き換えていて挿入位置が違う。イは向きが逆。
▼ 解説つきの類題を探す：過去問道場・分野別「データ構造」
【練習リンク】