基本情報 科目B 連結リスト（単方向リスト）のトレース練習
基本情報技術者試験の科目Bで、配列の次に立ちはだかるデータ構造が 連結リスト（単方向リスト） です。配列が「番号で位置を指す」のに対し、連結リストは各要素が「次の要素への参照」を持って数珠つなぎになります。この「参照を付け替える」感覚がつかめないと、空欄補充がまるごと外れます。本記事は、連結リストの操作を 参照を 1 本ずつ付け替える ようすを図と表で追う トレース で攻略する練習帳です。スタックとキューのトレース練習・再帰のトレース練習 の続編にあたります。
本記事は 過去問AI が学習用に作成したオリジナルの例題です。掲載している擬似言語は IPA の過去問・公式サンプルの転載ではなく、説明用に書き起こしたものです。擬似言語の正式な記述形式は必ず IPA 公式ページ で確認してください。クラス・メンバ変数・参照・未定義の記法そのものは 基本情報 科目Bの擬似言語 記法早見表 にまとめています。
連結リストは「参照でつながる」
配列は値を番号順にきっちり並べますが、連結リストは要素どうしを 参照 でつなぎます。各要素は次の 2 つを持ちます。
- 値：その要素が格納しているデータ
- 次への参照（next）：すぐ後ろの要素を指す情報。後ろが無い（末尾）なら 未定義
科目Bでは、こうした要素を クラス で表します。本記事ではクラス名を Node、値を持つメンバ変数を val、次の要素への参照を next とします（問題ごとにクラス名やメンバ名は変わるので、設問に添えられたクラスの説明を必ず先に読んでください）。
- メンバは 変数名.メンバ名 のドットでたどります。要素 p の値は p.val、次の要素は p.next
- Node 型の変数には、要素の実体ではなく インスタンスの参照 が入ります。だから 先頭 ← 先頭.next は「先頭が指す先を、1 つ後ろへ付け替える」という意味です
- リストの先頭は 大域: Node: 先頭 で保持します。リストが空のとき 先頭 は 未定義 です
- Node(値) と書くと、val に 値・next に 未定義の値 を入れた 新しい要素を作り、その参照を返す（コンストラクタ）
記法そのものが不安なら、先に 記法早見表のクラス・メンバの節 でドット（.）と未定義の読み方を確認してから戻ってくるとスムーズです。
例題1：先頭に追加する
新しい値をいつもリストの先頭にはさみ込む手続です。
大域: Node: 先頭 ← 未定義の値
○先頭に追加(整数型: 値)
Node: 新ノード
新ノード ← Node(値)
新ノード.next ← 先頭
先頭 ← 新ノード
読み方は「新しい要素を作り、その next を 今の先頭 に向け、最後に先頭をその新要素へ付け替える」。順番が命です。
先頭への追加をトレースする
空のリストに 先頭に追加(3) → 先頭に追加(7) → 先頭に追加(1) の順で操作します。作られた要素を A（値3）・B（値7）・C（値1）と呼び、参照の向きを矢印で書きます（→ は next、× は未定義）。
| 操作 | 作る要素 | 付け替え | 先頭 | リスト（先頭→末尾） |
|---|---|---|---|---|
| （初期） | — | — | 未定義 | （空） |
| 先頭に追加(3) | A(val=3) | A.next ← 先頭(未定義) | A | 3 × |
| 先頭に追加(7) | B(val=7) | B.next ← 先頭(A) | B | 7 → 3 × |
| 先頭に追加(1) | C(val=1) | C.next ← 先頭(B) | C | 1 → 7 → 3 × |
入れた順は 3 → 7 → 1 なのに、リストは 1 → 7 → 3 の並びになりました。先頭に挿し続けると、あとから入れたものほど前に来ます。ここが配列の「末尾に足す」と違う最初のポイントです。
例題2：先頭から末尾まで走査する
リストを 1 個ずつたどって値を読む、最も基本の操作です。
○表示()
Node: p
p ← 先頭
while (p が 未定義でない)
p.val を出力する
p ← p.next
endwhile
p という「いま見ている要素を指す変数」を、先頭から next 方向へ進めます。p が未定義になったら末尾を越えた合図 なのでループを抜けます。
走査をトレースする
例題1で作った 1 → 7 → 3 のリストを走査します。
| 周回 | p が指す要素 | p が未定義でない？ | 出力 | 次の p（p.next） |
|---|---|---|---|---|
| 1 | C(val=1) | はい | 1 | B |
| 2 | B(val=7) | はい | 7 | A |
| 3 | A(val=3) | はい | 3 | 未定義 |
| 4 | 未定義 | いいえ → 終了 | — | — |
出力は 1 → 7 → 3。「p が未定義でない間だけ読む」「読んだら p ← p.next で進める」の 2 つを守れば、長さがいくつでも迷いません。
例題3：途中に挿入する（参照の付け替えが山場）
ここが連結リストの最重要ポイントです。ある要素 p の すぐ後ろ に新しい値を割り込ませます。
○後ろに挿入(Node: p, 整数型: 値)
Node: 新ノード
新ノード ← Node(値)
新ノード.next ← p.next
p.next ← 新ノード
1 → 7 → 3 のリストで、値7の要素（B）を p として 後ろに挿入(B, 5) を実行します。作る要素を D（値5）とします。
| 手順 | 実行する代入 | 結果 |
|---|---|---|
| 1 | 新ノード ← Node(5) | D(val=5, next=未定義) ができる |
| 2 | 新ノード.next ← p.next | D.next ← B.next、つまり D が A(値3) を指す |
| 3 | p.next ← 新ノード | B.next ← D、つまり B が D を指す |
結果は 1 → 7 → 5 → 3。B と A の間に D がきれいに割り込みました。
順番を逆にすると壊れます。 もし手順3（p.next ← 新ノード）を先にやると、B.next は D を指してしまい、もともと B.next が指していた A（値3）への参照が消えます。その後で 新ノード.next ← p.next をしても、p.next はもう D 自身なので、D が自分を指す輪っかになり、3 から後ろが永久に行方不明です。「新しい要素の next を先につないでから、手前の next を付け替える」 という順序を、呪文のように覚えてください。
つまずきやすい3つのポイント
- 未定義をたどろうとする。末尾要素の next は未定義です。p.next.val のように 未定義の要素の中身を読もうとすると破綻 します。走査は必ず「p が未定義でない」を確認してから p.val を読む順序にします。
- 付け替えの順序。例題3のとおり、挿入も削除も つなぎ先を確保してから、手前のリンクを切り替える のが鉄則。順序を逆にすると後ろのリストを丸ごと失います。
- 先頭は特別扱い。先頭の要素には「手前の要素」がありません。先頭を消したり先頭に挿したりするときは、手前の next ではなく 大域変数 先頭 そのもの を付け替えます（先頭 ← 先頭.next など）。
木構造への橋渡し
連結リストの「要素が参照で次をつなぐ」考え方を、1 つの要素が複数の参照（左の子・右の子）を持つ ように広げると 木構造 になります。二分木なら各要素が left・right の 2 本の参照を持ち、深さ優先・幅優先で全要素をたどります。まずは本記事の単方向リストで「参照を 1 本ずつ追う・付け替える」感覚を固めてから、複数本に枝分かれする 木構造（二分木）のトレース練習 へ進むのが遠回りに見えて近道です。
トレースで詰まらないためのコツ
連結リストは、要素を 丸、next を 矢印 で紙に描くのが最強です。操作のたびに「どの矢印を消して、どの矢印を引き直したか」を 1 本ずつ書き換えれば、頭の中だけで追うより圧倒的にミスが減ります。先頭を指す矢印（大域変数 先頭）も忘れずに描いてください。p のような「いま見ている要素」を指す変数も、別の色の矢印にすると進み方が一目で分かります。
次のステップ
連結リストまで追えれば、科目Bのデータ構造はかなり守備範囲が広がります。データ構造のもう一つの定番 スタックとキューのトレース練習 で後入れ先出し・先入れ先出しの動きも押さえましょう。アルゴリズム側がまだなら、基礎の 合計・最大値・線形探索のトレース練習、二分探索のトレース練習、ソート（整列）のトレース練習、再帰のトレース練習 を先にどうぞ。読む速度を上げる訓練法は 基本情報科目B｜擬似言語アルゴリズム読解の3ステップ訓練法、つまずきの切り分けは 科目Bがわからない人へ、科目B 全体の進め方は 基本情報技術者 科目B完全対策 が地図になります。
手を動かす練習台としては、過去問AI の 基本情報 アルゴリズムとプログラミング分野の過去問 が使えます（こちらは科目A 相当の選択式で、科目B そのものの形式ではない点だけ意識してください）。各問題ページの AI コパイロットに「この連結リストの操作を、要素を丸と矢印で描いて参照の付け替えを 1 本ずつトレースして」と頼めば、本記事と同じ追い方を対話でその場で再現できます。
よくある質問
Q. 連結リストと配列は何が違いますか？ 配列は要素を番号順にきっちり並べ、番号で直接アクセスします。連結リストは各要素が「次の要素への参照」を持って数珠つなぎになり、先頭からたどって目的の要素に着きます。途中への挿入や削除が参照の付け替えだけで済む反面、n 番目に一発で飛べない（先頭から数える）のが配列との違いです。科目Bでは要素をクラスで表し、メンバ変数 next が次の要素を指します。
Q. 連結リストの「未定義」はどこに出てきますか？ 参照が何も指していない場所に出てきます。具体的には、リストが空のときの先頭と、末尾の要素の next が未定義です。走査では while (p が 未定義でない) のように「未定義かどうか」で末尾を判定してループを止めます。未定義の要素に対して .val や .next を読もうとすると処理が破綻するので、未定義でないことを確かめてから中身を読む順序を守ってください。
Q. 挿入や削除で順番を間違えると、なぜリストが壊れるのですか？ 参照を付け替える順序が逆だと、まだつなぎ替えていない側のリンクを先に消してしまうからです。途中に挿入する例なら、先に手前の要素の next を新要素へ向けてしまうと、その手前の要素が元々指していた後ろの要素への参照が失われ、そこから先のリストが全て行方不明になります。「新しい要素の next を先につないでから、手前の next を付け替える」の順を守るのが鉄則です。