問題
リストを二つの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] に次の要素の番号を格納してリストを表現しています。
以下は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」にします。
基本情報技術者平成24年春期 午前問7
問題
多数のデータが単方向リスト構造で格納されている。このリスト構造には，先頭ポインタとは別に，末尾のデータを指し示す末尾ポインタがある。次の操作のうち，ポインタを参照する回数が最も多いものはどれか。
- ア：リストの先頭にデータを挿入する。
- イ：リストの先頭のデータを削除する。
- ウ：リストの末尾にデータを挿入する。
- エ：リストの末尾のデータを削除する。
基本情報技術者平成24年春期 午前問7
単方向リストとは、リスト構造の基本的な形であり次のデータへのポインタを持つリストのことです。次のデータへのポインタしか持っていないので、先頭から順にたどっていく必要があります。
解答のア～エの操作のうち、ポインタを参照する回数が最も多いものはどれか、ひとつずつ確認します。
ア：リストの先頭にデータを挿入する
先頭に挿入するデータのポインタに「先頭ポインタ」を参照して取得した値「10」を設定します。データ挿入後は「先頭ポインタ」の値を「10 → 50」に書き替えます。
ポインタの参照は1回（先頭ポインタ → 先頭のデータ「アドレス：10」）
イ：リストの先頭のデータを削除する
「先頭ポインタ」を参照して「先頭のデータ」を特定、「先頭ポインタ」の値を「先頭のデータ」が持つポインタの値「10 → 40」に書き替えます。
ポインタの参照は1回（先頭ポインタ → 先頭のデータ「アドレス：10」）
ウ：リストの末尾にデータを挿入する
「末尾ポインタ」を参照して「末尾のデータ」を特定、「末尾のデータ」のポインタを追加するデータのアドレス「50」に書き替えます。そして、データ挿入後は「末尾ポインタ」の値を「20→ 50」に書き替えます。
ポインタの参照は1回（末尾ポインタ → 末尾のデータ「アドレス：20」）
リストの末尾のデータを削除する
末尾のデータを削除するには、末尾のひとつ前のデータのポインタを空にします。
単方向リストなので末尾のデータからひとつ前のデータへの逆方向の参照はできず、先頭から末尾のひとつ前まで順番にポインタをたどっていく必要があります。
「先頭ポインタ」を参照して「先頭のデータ」を特定、「先頭のデータ」のポインタを参照して「次のデータ」を特定と、先頭から末尾のひとつ前まで順番にポインタをたどっていきます。
そして、末尾のひとつ前のデータにたどりついたらポインタの値を削除し「末尾ポインタ」の値を「20 → 30」に書き替えます。
ポインタの参照は3回
- 先頭ポインタ → 先頭のデータ「アドレス：10」
- 先頭のデータ「アドレス10」→ 次のデータ「アドレス40」
- 次のデータ「アドレス40」→ 更に次データ「アドレス30」
基本情報技術者試験おすすめの参考書・問題集
| いちばんやさしい 基本情報技術者 | 『基本情報技術者試験』試験に、短期間で一発合格するための試験対策本。ITの知識がまったくない、未経験者やでもスラスラと学習を進められるよう、丁寧に解説。 |
| かやのき先生の基本情報技術者教室 | 基本情報技術者をめざす方のためのやさしいオールインワンタイプの参考書＆問題集。イラストや豊富な図解・例え話を駆使して理解しやすく・記憶に残りやすいように説明。 |
| 基本情報技術者 パーフェクトラーニング過去問題集 | 科目A・Bともに万全の対策ができる、定番の過去問題集！科目A・科目Bの両方について万全の対策ができる。 |
| キタミ式イラストIT塾 基本情報技術者 | すべての解説をイラストベースで行っているため，とてもわかりやすい解説本。いちばん最初に読む基本情報技術者試験関連の書籍を探している人におすすめ！ |
| 出るとこだけ！基本情報技術者［科目B］ | 基本情報技術者【科目Ｂ】対策の定番書！前提知識＋解き方＋試験問題を掲載。効率よく学習できる。 |
| 基本情報技術者 合格教本 | 出題範囲を体系的にきちんと理解しながら学習したい人におすすめ！基本情報技術者試験の定番テキストの改訂版。 |
| 基本情報技術者 超効率の教科書＋よく出る問題集 | 動画でスムーズに学習スタート、テキストでしっかり理解度を深める！よく出る問題を反復学習することで、合格に直結するチカラが身に付く！ |