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

リストの問題になると、矢印の先を見失って手が止まる。

ノードや参照という言葉が出てきた瞬間、頭が真っ白になっていませんか？

配列なら添字を数えれば追えたのに、リストは次の要素がどこにあるのか一目では分かりません。その戸惑いは、科目Bを学ぶ多くの人が同じ場所で感じているものです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でリストを自分で組み立てる機会はそれほど多くありませんが、つなぎ替えの順番を一つ間違えたせいで、データの一部がどこからもたどれなくなる不具合には何度か立ち会っています。

裏を返せば、順番さえ押さえればリストは怖くありません。この記事では、ノードの形から、たどる処理、挿入と削除までを一つずつ整理していきます。

リストは、次の場所を持って並ぶデータ構造¶

はじめに、リストがどういうものなのかを言葉で押さえておきましょう。リストは、値と次の要素の居場所をセットで持った箱を、数珠つなぎにしたデータ構造です。

この箱のことをノードと呼びます。ノードが自分の次を指し示しているので、先頭から順に手繰っていけば全部の要素にたどり着けます。

配列のように場所が連続して並んでいるわけではありません。バラバラの場所にあるノードが、指し示す関係だけでつながっています。

イメージが湧きにくいときは、宝探しのメモを思い浮かべてください。一枚目のメモに次の隠し場所が書いてあり、そこに行くとまた次の場所が書いてある、という形です。

ここまでの説明を、配列と比べる形でもう少しはっきりさせておきます。

配列とリストは何が違うのか¶

両者の違いは、要素へのたどり着き方と、途中を変えるときの手間に出ます。次の表で並べてみます。

表を見ると、得意なことがきれいに分かれているのが分かります。狙った要素をすぐ取り出したいなら配列、途中の出し入れが多いならリストです。

科目Bでリストが出るのは、この参照をつなぎ替えるという操作が、コードを読む力をよく測れるからだと考えています。

配列側の読み方が怪しいと感じる場合は、先にそちらを固めておくと理解が早く進みます。

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

ノードは値と次への参照でできている¶

では、ノードの中身を具体的に見ていきましょう。ノードが持つのは、多くの場合ふたつだけです。

ひとつは、その要素が持っている値そのもの。もうひとつが、次のノードの場所を示す参照です。

擬似言語の問題では、この形が問題文の冒頭で定義されます。たとえば次のような書き方です。

/* リストの要素（ノード）の定義 */
/* val  … その要素が持つ値      */
/* next … 次の要素への参照      */

/* 変数 head は、リストの先頭要素への参照を持つ */

大事なのは、next が値そのものではなく、場所を指しているという点です。next をたどった先に、また val と next を持ったノードがあります。

そしてリストの最後尾では、next が指す先がありません。ここには未定義の値が入っていて、問題文では null と書かれることもあります。

この末尾の目印が、後で出てくる繰返しの終了条件になります。今の段階では、最後だけ next が空だと覚えておけば十分です。

先頭からたどる処理を読めるようにする¶

ノードの形が分かったら、次はリストを端から端まで見て回る処理です。ここが読めれば、リスト問題の半分は越えたと言えます。

たどる処理の骨格は、驚くほど短いコードで書けます。まずは実物を見てください。

○リストの全要素を表示する
 curr ← head            /* 先頭から始める */
 while (curr が 未定義 でない)
   curr.val を表示する
   curr ← curr.next     /* 次の要素へ進む */
 endwhile

注目してほしいのは、最後の行です。curr ← curr.next という一行が、次のノードへ足を進める役割を全部担っています。

この一行を書き忘れると、curr がずっと先頭のままになり、同じ値を表示し続けます。処理が終わらない無限ループになる、よくある失敗です。

繰返しの条件も見ておきましょう。curr が未定義でない間だけ回るので、末尾のノードを処理し終えると自然に止まります。

言葉で追うより、実際に値を書き出したほうが早く納得できます。値が 10、20、30 の三つのノードが並んだリストで動かしてみます。

三つのノードに対して、繰返しは三回だけ回っています。四回目に入ろうとしたところで条件が偽になり、処理が終わる流れです。

こうやって一行ずつ表に書き出す方法は、リスト以外の問題でも効きます。手順そのものを身につけたい人は、次の記事もあわせて読んでみてください。

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

現在位置を表す変数の名前に慣れる¶

たどる処理では、今どこを見ているかを覚えておく変数が必ず登場します。この記事では curr という名前を使いましたが、問題によって呼び名は変わります。

p や ptr、cur、node といった名前もよく見かけます。名前が違うだけで、役目はどれも同じです。

さらに、ひとつ前のノードを覚えておく変数が一緒に出てくることもあります。prev や before といった名前で、削除の場面で活躍します。

問題を読み始めたら、まずどの変数が現在位置でどれが前の位置かに印を付けましょう。この整理だけで、コードの見通しがぐっと良くなります。

特定の値を探しながらたどる¶

たどる処理は、表示するだけでなく探す目的でもよく使われます。目的の値が見つかったところで繰返しを抜ける形です。

書き方を見ておきましょう。条件がひとつ増えるだけで、骨格は先ほどと変わりません。

○リストから値 target を探す
 curr ← head
 while (curr が 未定義 でない)
   if (curr.val が target と等しい)
     curr を返す        /* 見つかった */
   endif
   curr ← curr.next
 endwhile
 未定義 を返す           /* 最後まで無かった */

見つからなかったときに未定義を返す行が、繰返しの外側に置かれている点に注目してください。中に入れてしまうと、一つ目の要素で違っただけで探索が終わります。

この形は、配列に対する線形探索とほとんど同じ考え方です。違うのは、添字を増やす代わりに参照をたどっている点だけになります。

探索そのものの読み方を整理しておきたい人は、こちらもあわせてどうぞ。

【関連記事】擬似言語の線形探索と二分探索の違いとは？科目Bで差がつく探索の読み方

挿入と削除は、つなぎ替えの順番がすべて¶

ここからがリスト問題の本番です。要素を途中に入れる、あるいは取り除く操作を見ていきます。

配列と違って、後ろの要素をずらす作業はありません。その代わり、参照の書き換えを正しい順番で行う必要があります。

順番を逆にすると、後ろのノードがどこからもたどれなくなります。まずは挿入から確認しましょう。

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

あるノードの直後に、新しいノードを差し込む場面を考えます。関係するのは、差し込む位置の前にあるノードと、新しいノード、そして元々後ろに続いていたノードです。

擬似言語で書くと、たった二行です。

/* curr が指すノードの直後に、newNode を挿入する */
newNode.next ← curr.next    /* ① 新しいノードの次を、元の続きに向ける */
curr.next ← newNode         /* ② 前のノードの次を、新しいノードに向ける */

この二行は、順番を入れ替えてはいけません。理由を落ち着いて考えてみましょう。

先に curr.next ← newNode を実行すると、curr が元々指していた続きの情報が上書きされて消えます。その時点で、後ろに続いていたノードへの道が失われます。

つまり、新しいノードの行き先を先に確保しておくのが鉄則です。この考え方は、整列の交換処理で一時変数を使う理由とよく似ています。

選択肢を絞るときも、この順番が判断材料になります。二行の順序が入れ替わっている選択肢は、その時点で外せます。

削除は前のノードの next を書き換える¶

次は削除です。あるノードをリストから取り除くとき、実際に行うのは前のノードの参照の書き換えだけです。

コードにすると、こちらは一行で済みます。

/* prev の直後にある curr を、リストから取り除く */
prev.next ← curr.next

prev の次が、curr を飛び越えて curr の次を指すようになりました。これで curr はどこからも参照されなくなり、リストから外れます。

curr の中身を消す処理は書かれていない点に注意してください。たどれなくなった時点で、リスト上は存在しないのと同じ扱いになります。

ここで必要になるのが、先ほど触れた prev という変数です。削除するノードだけを知っていても、その前のノードが分からないと参照を書き換えられません。

だから、リストをたどる処理の中で prev を一緒に進めるコードがよく出てきます。curr を進める前に prev ← curr を置く形です。

出し入れの順番という観点では、スタックとキューの考え方も一緒に押さえておくと理解が立体的になります。

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

科目Bのリスト問題でつまずきやすい場所¶

ここまでの内容が分かっていても、試験本番で失点する箇所はある程度決まっています。私が学習相談を受けてきた範囲では、次の三つに集中していました。

失点の型を先に知っておくと、同じ落とし穴を避けられます。表で確認しましょう。

どれも、通常の真ん中あたりの要素では起きない問題です。境界の場面だけ挙動が変わるので、そこを狙って出題されます。

問題文に空のリストの場合という但し書きがあったら、それは考えるヒントだと受け取ってください。

未定義の扱いを混同しない¶

もう一歩踏み込んで、未定義について整理しておきます。ここは言葉の意味が曖昧なままだと、条件式の判断がぶれる場所です。

next が未定義であるというのは、次のノードが無いという意味です。値が 0 だとか、空文字だとかいう話ではありません。

同じように、head が未定義なら、そのリストには要素が一つも無いことになります。要素が一つだけあるリストと混同しないようにしましょう。

要素が一つのリストでは、head はノードを指していて、そのノードの next が未定義です。この違いが、選択肢の絞り込みでそのまま効いてきます。

手続の中でリストを渡す形に慣れる¶

リスト操作は、手続や関数の形で出題されることがほとんどです。引数としてリストの先頭を受け取り、処理をして返す流れになります。

このとき、引数で受け取った変数を書き換えても、呼び出し元の変数がどうなるかは問題の定義次第です。問題文の説明を読み飛ばさないでください。

手続と関数の読み分けに不安が残っている場合は、こちらの記事で基礎を確認しておくと安心です。

【関連記事】擬似言語の手続と関数の違いとは？引数・戻り値と変数の有効範囲を解説

手を動かして確かめるのが一番の近道¶

リストの理解は、読むだけではなかなか定着しません。参照が動く様子は、実際に値を追ってはじめて腑に落ちます。

紙に丸と矢印を描いて、つなぎ替えを一手ずつ書き直してみてください。矢印を消して引き直す作業が、そのまま参照の書き換えです。

そのうえで、コードを一行ずつ動かして確かめられると理解が速くなります。Giji Academy の擬似言語シミュレーターなら、変数の変化を見ながら処理を追えます。

使い方から知りたい人は、次の記事に手順をまとめてあります。

【関連記事】擬似言語 シミュレーターとは？試験対策に役立つ使い方と学習法を解説

まとめ¶

最後に、この記事で確認したことを振り返ります。

リストは、値と次への参照を持つノードがつながったデータ構造でした。先頭から順にたどることでしか要素に届かない代わりに、途中の出し入れが得意です。

たどる処理の核は、curr ← curr.next の一行です。この行が現在位置を前へ進め、未定義に行き着いたところで繰返しが終わります。

挿入では、新しいノードの next を先に決めてから前のノードをつなぎ替えます。削除では、前のノードの next を書き換えて対象を飛び越えます。

そして、先頭の削除と空のリストという境界の場面が、試験で狙われやすい場所でした。ここに気を配れるようになれば、正答率は確実に上がります。

矢印を見失うのは、あなたの理解力の問題ではありません。丁寧に一手ずつ描き直せば、リストは必ず読めるようになります。