科目Bの連結リスト問題の解き方｜nextを図にして追う

連結リストの問題になると、どこがどこにつながっているのか分からなくなる。

next を目で追っているうちに、迷子になっていませんか？

配列の問題なら、添字の表を書けばなんとかなります。ところが連結リストは、値が並んでいる場所そのものが見えません。

でも大丈夫です。見えないものを見えるようにする方法があります。図を1枚描くだけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務で連結リストを自分で書くことはほとんどありませんが、参照をつなぎ替える順番を逆にして、データが丸ごと消える。この事故は何度か見てきました。

つまり連結リストで間違えるのは、理解力の問題ではありません。順番の問題です。

この記事では、科目Bの連結リスト問題を5つの段に分けて追っていきます。科目B全体の形をまだつかめていない人は、先に親記事を読んでおくと話が早くなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

科目Bの連結リスト問題は何を聞いているのか¶

最初に、この分野で何が問われるのかをはっきりさせておきましょう。

連結リストの問題で聞かれるのは、リストの中身ではありません。つなぎ替えたあと、どういう並びになるかです。

出題のされ方を整理すると、だいたい次の4つに収まります。

表を見て分かるとおり、どれも途中の参照がどこを向いているかを追えていないと答えが出ません。

狙われるのは、いつも先頭と末尾¶

真ん中のノードを消したりつないだりする処理は、書き方が1つに決まります。試験が好んで聞くのは、先頭を消すときと、末尾に足すときです。

先頭には前のノードがありません。末尾の next は、どこも指していません。この2つだけ処理が変わるので、そこが問題になります。

だから練習するときは、必ず先頭と末尾でも1回ずつ追ってみてください。

用語の暗記は要らない¶

ノード、参照、ポインタ。呼び方はいろいろありますが、覚えても点にはなりません。

必要なのは、目の前のコードで next がどこを向いたかを読み取る力だけです。そこだけ見てください。

リストの文法そのものに自信がない場合は、先にこちらで土台を作っておくと読みやすくなります。

【関連記事】擬似言語のリスト（連結リスト）がわからない人へ｜ノードと参照のたどり方を解説

段1：登場する参照が何本あるかを数える¶

問題文を読み終えたら、1行目から追い始める前に変数の宣言だけを眺めます。数えるのは、ノードを指す変数の本数です。

1本なら、ただたどるだけの処理。2本あるなら、つなぎ替えが起きると考えて構いません。

まずは、たどるだけのコードを見てみましょう。出題形式に合わせた自作の例です。

○整数型: 要素数を数える(ノード: head)
  ノード: curr ← head
  整数型: count ← 0
  while (curr が 未定義 でない)
    count ← count + 1
    curr ← curr.next
  endwhile
  return count

参照は curr の1本だけです。先頭から next をたどって、未定義に当たったら終わります。

参照が2本あればつなぎ替えが起きる¶

prev と curr のように変数が2つ宣言されていたら、削除か挿入だと判断してください。前のノードを覚えておく必要があるからです。

なぜ2本要るのかというと、連結リストは後ろへは進めても前へは戻れないからです。ここが配列との決定的な違いになります。

配列の添字なら、1つ引けば前に戻れます。その感覚のまま読むと必ずつまずくので、切り替えておきましょう。

配列の側の数え方が不安な人は、こちらの記事が対応しています。

【関連記事】擬似言語の配列と添字がわからない人へ｜要素数・二次元配列の読み方を解説

段2：まず目を付けるのは3か所¶

参照の本数が分かったら、次に読む場所を固定します。連結リストの問題で見るところは3つだけです。

順番を決めておけば、長いコードでも迷いません。

3つめが答えそのものになる問題が多いので、代入行は指を置いて読んでください。

継続条件が「次が未定義でない」なら末尾を探している¶

curr が 未定義 でない で回るコードは、最後まで全部たどります。

いっぽう curr.next が 未定義 でない で回るコードは、末尾の1つ手前で止まります。末尾に何かを足したいときの書き方です。

この1文字違いで止まる位置が変わります。どちらなのかを、必ず最初に確かめてください。

代入行は、左辺と右辺を声に出して読む¶

prev.next ← curr.next を目で追うと、似た記号が並んでいて混乱します。

そこで、前のノードの次を、今のノードの次に向ける、と言葉にしてみてください。言葉に直した瞬間、curr がリストから外れると分かります。

初めて見る形の処理に当たったときの読み方は、こちらでも扱っています。

【関連記事】科目Bの初見問題が解けない人へ｜知らないアルゴリズムが出たときの読み方

段3：図を描いてから表で追う¶

ここが本番です。連結リストだけは、表を書く前に図を描いてください。

図といっても、値を書いて矢印を引くだけです。紙の上でこうなります。

head → [10] → [20] → [30] → 未定義

矢印1本が next 1つぶんです。これだけで、見えなかったつながりが目に見えるようになります。

削除するノードの前後だけを書き出す¶

リストが5要素あっても、書くのは3つで足ります。消すノードと、その前と、その後ろです。

20 を削除する場面を追ってみましょう。prev が 10 を、curr が 20 を指している状態から始めます。

代入は1行だけです。それでも 10 の next が 30 に変わり、20 はどこからも指されなくなりました。

図に戻すと、こうなっています。

head → [10] ────→ [30] → 未定義
          [20]（どこからも指されていない）

curr の値は 20 のままです。ここが引っかけどころで、curr を見ても消えたかどうかは分かりません。見るのは常に prev.next のほうです。

表の書き方そのものを固めたい人は、専用の記事があります。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

挿入は、新しいノードの next を先に決める¶

挿入の問題では、代入が2行出てきます。そして順番を逆にすると、リストが壊れます。

新しいノードの next を先に決めてから、前のノードの next を向け替える。これが正しい順番です。

先に前のノードを向け替えてしまうと、その先の並びをどこも覚えていない状態になります。表の3列目が未定義になった時点で気づけるので、ここも書きながら確かめてください。

末尾に足す問題は、止まる位置を先に決める¶

末尾への追加は、挿入の中でも別枠で考えたほうが速いです。つなぎ替えの前に、末尾まで進む処理が入るからです。

進み終わったとき curr がどこを指しているか。ここを図に書いてから、次の代入行を読んでください。

curr.next が 未定義 でない で回るコードなら、curr は最後のノードを指した状態で止まります。その next に新しいノードを向ければ完成です。

いっぽう curr が 未定義 でない で回してしまうと、curr は未定義まで進んでしまいます。この状態で next に代入しようとするのが、典型的な誤答の1つです。

段4：まぎらわしい選択肢の見分け方¶

連結リストの選択肢は、正解の代入文を1か所だけひねって作られます。作り方が決まっているので、知っておくと迷ったときに戻れます。

よくある外し方を表にまとめました。

いちばん下が、本番で差がつくところです。先頭を消すときだけは head ← head.next のように head そのものを動かします。

このとき prev を使おうとすると、指すべきノードが存在しません。先頭だけ処理を分けている理由が、ここにあります。

判断に迷ったら、自分の図に戻ってください。矢印をたどって全部の値に届かないなら、その選択肢は切れます。

空欄補充なら、選択肢を図に当てはめる¶

つなぎ替えの1行が空欄になっている問題では、考え込むより手を動かすほうが速いです。選択肢を1つずつ図に当てはめて、矢印を引き直してみてください。

間違った選択肢を入れると、矢印が自分自身を指すか、途中で切れます。その崩れ方が見えた時点で消せます。

似た形のデータ構造として、スタックとキューの問題も同じ追い方が使えます。合わせて確認しておくと得です。

【関連記事】擬似言語のスタックとキューの違いとは？科目Bで出る出し入れの順番を解説

段5：シミュレーターで動かして答え合わせをする¶

最後の段は、自分の図と表が正しかったかを確かめる作業です。ここを省くと、ずれた追い方が癖になります。

Giji Academy の擬似言語シミュレーターでは、いま見たようなコードを1行ずつ実行して、変数の中身が変わる様子を画面で追えます。無料で使えるので、紙に描いた図と見比べてみてください。

擬似言語シミュレーターでコードを動かしてみる

自分の表と画面の値がずれた行が、そのまま弱点です。そこだけ直せば、次の問題から精度が上がります。

ずれたら、代入行の1行前から読み直す¶

全部やり直す必要はありません。原因はほぼ、代入の順番か、左辺と右辺の取り違えです。

見つけたら、同じ型の問題をもう1問だけ追ってみてください。連結リストは型が少ないので、それで定着します。

まとめ¶

科目Bの連結リスト問題は、覚えることが少ない分野です。差がつくのは、つながりを目に見える形にできているかどうかだけです。

今日の流れを、もう一度振り返っておきましょう。

この5段は、二分木や木構造の問題にもそのまま使えます。変わるのは矢印の本数だけです。

最初は図を描くのが面倒に感じるかもしれません。それでも2問か3問も解けば、描く線の数が自然に減っていきます。

矢印が見えるようになれば、連結リストは落ち着いて取れる分野に変わります。今日のうちに1問、紙に図を描きながら追ってみてください。

一度その感覚をつかめば、初めて見るつなぎ替えでも順番から確かめられるようになります。焦らず、1行ずつでいきましょう。