基本情報技術者

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

2021年10月29日

今回のテーマはリスト構造です。
リストはわかりますが、過去問はむずかしい・・・

問題

リストを二つの1次元配列で実現する。配列要素 box[i] と next[i] の対がリストの一つの要素に対応し,box[i] に要素の値が入リ,next[i] に次の要素の番号が入る。配列が図の状態の場合,リストの3番目と4番目との間に値が H である要素を挿入したときの next[8] の値はどれか。ここで,next[0] がリストの先頭(1番目)の要素を指し,next[i] の値が0である要素はリストの最後を示し,next[i] の値が空白である要素はリストに連結されていない。

問題の配列

ア:3 イ:5 ウ:7 エ:8

基本情報技術者平成30年春期 午前問6 ※図は過去問を参考に作成したものです。

問題

多数のデータが単方向リスト構造で格納されている。このリスト構造には,先頭ポインタとは別に,末尾のデータを指し示す末尾ポインタがある。次の操作のうち,ポインタを参照する回数が最も多いものはどれか。

  • ア:リストの先頭にデータを挿入する。
  • イ:リストの先頭のデータを削除する。
  • ウ:リストの末尾にデータを挿入する。
  • エ:リストの末尾のデータを削除する。

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

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

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

本記事で学べること

  • リスト構造について理解する
  • 単方向リスト双方向リスト循環リストの動きについて理解する
  • 基本情報技術者試験の過去問の解き方を学ぶ

リスト構造

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

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

リスト構造のイメージ例

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

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

スポンサーリンク

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

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

リストデータ挿入後

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

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

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

データ削除後

リストの種類

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

単方向リスト

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

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

単方向リストのイメージ例

双方向リスト

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

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

双方向リストのイメージ例

循環リスト

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

循環リストのイメージ例

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

スポンサーリンク

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

問題

リストを二つの1次元配列で実現する。配列要素 box[i] と next[i] の対がリストの一つの要素に対応し,box[i] に要素の値が入リ,next[i] に次の要素の番号が入る。配列が図の状態の場合,リストの3番目と4番目との間に値が H である要素を挿入したときの next[8] の値はどれか。ここで,next[0] がリストの先頭(1番目)の要素を指し,next[i] の値が0である要素はリストの最後を示し,next[i] の値が空白である要素はリストに連結されていない。

問題の配列

ア:3 イ:5 ウ:7 エ:8

基本情報技術者平成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番目にデータを挿入

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

ポインタを設定

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

基本情報技術者平成24年春期 午前問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」

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

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

helpful