単方向リストの読み方｜next をたどって、未定義で止まる【基本情報技術者試験 科目B】

現行FE シラバス Ver9.2 準拠擬似言語の記述形式は2022年から変更なし最終更新 2026-10-11

単方向リストは、要素の1つ1つが「値」と「次の要素の場所」を持つ並びです。配列を前から順に読むのとはちがい、読む順は置いてある順ではありません。先頭の要素から「次の要素の場所」を順にたどって読みます。

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円2,600円中身を見る ›

単方向リスト ── 値と「次の場所」の組

科目Bでは、単方向リストを2本の配列で表すことがあります。1本に値を入れ、もう1本に、次の要素の場所として要素番号を入れます。

文字型の配列: val ← {"A", "C", "D", "B"}
整数型の配列: next ← {4, 3, 未定義の値, 2}

next に入っているのは値ではなく、次に読む要素の番号です。値が A・C・D・B とばらばらの順で入っていても、next のとおりに読めば順番は決まります。ばらばらに置けるおかげで、あとから要素を足したり抜いたりするときに、ほかの要素を動かさずに済みます（足し方と抜き方は A10-2）。

たどり方 ── next の番号へ移り、未定義で止まる

読み始めるのは先頭の要素です。どの要素が先頭かは、問題ごとに決めてあります。この例では、1番の要素を先頭とします（令和8年度 問4 も、問題文で1番を先頭と決めています）。

4番の要素に着いたら、そこでも同じ2つをします。next が未定義の要素に着くまで続けると、こうなります。

4つ目に読んだ3番の要素は、next が未定義です。次の要素が無いので、ここが末尾です。末尾は、配列のいちばんうしろにあるとは限りません。next が未定義の要素が末尾です。

たどるプログラム ── p ← next[p] をくり返す

いま手でたどったことを、プログラムにします。p は、いまいる要素の番号を入れておく変数です。

文字型の配列: val ← {"A", "C", "D", "B"}
整数型の配列: next ← {4, 3, 未定義の値, 2}
整数型: p ← 1
while (true)
  val[p] を出力する
  if (next[p] が 未定義)
    繰返し処理を終了する
  endif
  p ← next[p]
endwhile

当サイトで作った例です。

実行すると、A、B、C、D の順に出力されます。

p ← next[p] は、いまいる要素の next を読んで、その番号を新しい p にする行です。リストをたどるプログラムでは、この行が「次の要素へ進む行」にあたります。

クラスで書かれたリスト ── next[p] が p.next になる

同じリストが、クラスを使って書かれることもあります。要素1つをクラス ListElement で表し、メンバ変数に val（値）と next（次の要素）を持たせる書き方です。

こちらには番号が出てきません。next に入っているのは、次の要素そのものを指す参照です（参照＝どの要素かを指すもの）。p も番号ではなく、要素を指す変数になります。

listHead は、先頭の要素を指している変数です。たどるときは、ここから始めます。配列2本のときと並べると、こうなります。

プログラムにすると、こうなります。listHead には、上の図のリストの先頭（A の要素）がすでに入っているものとします。

大域: ListElement: listHead

ListElement: p
p ← listHead
while (true)
  p.val を出力する
  if (p.next が 未定義)
    繰返し処理を終了する
  endif
  p ← p.next
endwhile

当サイトで作った例です。

1行目の 大域: は、どの手続からも使える変数に付く印です。ListElement: p で、要素を指す変数 p を用意しています。

上の図のリストで動かすと、p ははじめ A の要素を指します。このとき p.next は B の要素なので、p ← p.next のあと p は B の要素を指します。これを D の要素までくり返すので、出力は配列2本のときと同じ A、B、C、D です。

      prev ← prev.next

書き方が変わっても、読むところは同じです ── どこから始めるか、どの行で次へ進むか、何が未定義なら止まるか。

次に読む