【基本情報技術者試験】リスト構造

今回のテーマはリスト構造です。

リストはわかりますが、過去問はむずかしい・・・

基本情報技術者試験や応用情報技術者試験で出題されるリスト構造の問題、過去問をみると難しく感じる問題ですが、リスト構造の動きを理解していればそこまで難しい問題ではありません。

本記事では、リスト構造について分かりやすく解説していきます。

リスト構造

リストはデータ構造（※配列のように複数のデータを格納できる入れ物）のひとつです。リストのデータには「ポインタ」と呼ばれる、次のデータがメモリ上のどの位置にあるかを示す情報が付与されています。

以下はリスト構造のイメージ図です。

リストのデータには「ポインタ」が付与されており、この「ポインタ」をたどることで、リスト内の各データにアクセスすることができます。

リストの特徴はデータの追加・挿入・削除が容易にできることです。なぜなら「ポインタ」さえ書き替えれば、いくらでもデータを繋ぎ変えることができるからです。

スポンサーリンク

リストにデータを挿入する

リストにデータを挿入する場合は、次の図のように「データ2」のポインタを「30 → 50」に書き替え、挿入する「データ5」のポインタに「30」を設定します。

このようにポインタを書き替えるだけで、簡単にデータを挿入することができます。

リストのデータを削除する

リストからデータを削除する場合は、次の図のように「データ2」のポインタを「30 → 20」に書き替えます。

リストの種類

リストには次の種類があります。

単方向リスト

単方向リストとは、リスト構造の基本的な形であり次のデータへのポインタを持つリストのことです。

次のデータへのポインタしか持っていないため、一方通行となり先頭から順番にデータをたどっていきます。

双方向リスト

双方向リストとは、次のデータへのポインタと、前のデータへのポインタを持つリストのことです。

次データと前データのポインタを持っているので、前後のどちらにもたどっていくことができます。

循環リスト

循環リストとは、単方向リストと同じで次のデータへのポインタを持つリストのことです。単方向リストとの違いは最後尾のデータが先頭データへのポインタを持っているところです。

基本情報技術者試験 過去問の解説

スポンサーリンク

基本情報技術者平成30年春期 午前問6

設問は二つの1次元配列を使いbox[i] に要素の値、next[i] に次の要素の番号を格納してリストを表現しています。

next[i]がポインタということですね。

以下はbox[i]とnext[i]をリスト構造にしたイメージ例です。

※「next[0] がリストの先頭(1番目)の要素を指し」と書かれているので位置「1」値「A」が1番目

この問題は「リストの3番目と4番目との間に値が H である要素を挿入したときの next[8] の値はどれか」ときいているので、問題文のとおりに3番目と4番目の間に値がHである要素を挿入します。

リストにデータを挿入した場合、ポインタの値を書きかえる必要があります。3番目と4番目の間にデータを挿入したので、以下の図のように next[3]の値を「7 → 8」に書き替え、挿入した next[8]の値を「7」にします。

next[8]の値は「7」になったので「ウ」が正解です。

基本情報技術者平成24年春期 午前問7

単方向リストとは、リスト構造の基本的な形であり次のデータへのポインタを持つリストのことです。次のデータへのポインタしか持っていないので、先頭から順にたどっていく必要があります。

解答のア～エの操作のうち、ポインタを参照する回数が最も多いものはどれか、ひとつずつ確認します。

今回は次の単方向リストを例に説明していきます。

ア：リストの先頭にデータを挿入する

先頭に挿入するデータのポインタに「先頭ポインタ」を参照して取得した値「10」を設定します。データ挿入後は「先頭ポインタ」の値を「10 → 50」に書き替えます。

ポインタの参照は1回（先頭ポインタ → 先頭のデータ「アドレス：10」）

イ：リストの先頭のデータを削除する

「先頭ポインタ」を参照して「先頭のデータ」を特定、「先頭ポインタ」の値を「先頭のデータ」が持つポインタの値「10 → 40」に書き替えます。

ポインタの参照は1回（先頭ポインタ → 先頭のデータ「アドレス：10」）

ウ：リストの末尾にデータを挿入する

「末尾ポインタ」を参照して「末尾のデータ」を特定、「末尾のデータ」のポインタを追加するデータのアドレス「50」に書き替えます。そして、データ挿入後は「末尾ポインタ」の値を「20→ 50」に書き替えます。

ポインタの参照は1回（末尾ポインタ → 末尾のデータ「アドレス：20」）

リストの末尾のデータを削除する

末尾のデータを削除するには、末尾のひとつ前のデータのポインタを空にします。

単方向リストなので末尾のデータからひとつ前のデータへの逆方向の参照はできず、先頭から末尾のひとつ前まで順番にポインタをたどっていく必要があります。

「先頭ポインタ」を参照して「先頭のデータ」を特定、「先頭のデータ」のポインタを参照して「次のデータ」を特定と、先頭から末尾のひとつ前まで順番にポインタをたどっていきます。

そして、末尾のひとつ前のデータにたどりついたらポインタの値を削除し「末尾ポインタ」の値を「20 → 30」に書き替えます。

ポインタの参照は3回

1. 先頭ポインタ → 先頭のデータ「アドレス：10」
2. 先頭のデータ「アドレス10」→ 次のデータ「アドレス40」
3. 次のデータ「アドレス40」→ 更に次データ「アドレス30」

上記の結果より、ポインタを参照する回数が最も多いのは「エ」の「リストの末尾のデータを削除する」です。