この記事で解決できる内容
※タップすると該当箇所までジャンプできます。
コンピュータが読み書きしたり、表現するデータの構造には様々な種類があります。その中でも「リスト構造」と「配列構造」は似て非なるものとして違いが分かりづらいです。
そこで今回は、リスト構造と配列構造の違いを分かりやすくまとめていきます。
最後には基本情報技術者試験で実際に出題された過去問にも挑戦してもらうことで理解を深めていきましょう。
ITスキルを磨くならUdemy
- 最大95％OFFで有料コンテンツが購入可能！
- ITスキルを本よりもわかりやすく体系的に学べる！
- スキマ時間で学習が可能！
>> 基本情報技術者試験への一発合格を目指している人におすすめの学習方法はこちら
【基本情報】リスト構造と配列構造の違いをわかりやすく解説！
リストを二つの1次元配列で実現する。配列要素 box[i] と next[i] の対がリストの一つの要素に対応し，box[i] に要素の値が入リ，next[i] に次の要素の番号が入る。配列が図の状態の場合，リストの3番目と4番目との間に値が H である要素を挿入したときの next[8] の値はどれか。ここで，next[0] がリストの先頭(1番目)の要素を指し，next[i] の値が0である要素はリストの最後を示し，next[i] の値が空白である要素はリストに連結されていない。
出典：平成30年春期 問6
ア:3 イ:5 ウ:7 エ:8
今回解説していくのは上記のような問題です。
リスト構造と配列構造に関しての知識が無ければ問題文を読んでもちんぷんかんぷんになってしまいますので、「リスト構造」と「配列構造」について詳しく見ていきましょう。
問題を解くのに知っておきたい用語
- リスト構造とは？
- 1次元配列とは？
データ構造には【リスト構造】と【配列構造】がある
まずはデータ構造の種類【配列構造】と【リスト構造】についてまとめていきます。
特徴をざっくりまとめると以下。
- 配列構造：添え字だけ
- リスト構造：添え字とポインタで数珠つなぎになっているデータ
リスト構造とは？
要素のほかに「次はあそこだ！」と場所を指すポインタの組み合わさってデータが数珠つなぎにつながっているデータ構造のことです。
この数珠つなぎのようにつながっていることから【連結リスト】とか【線型リスト】とも呼ばれます。
- 単方向リスト→「前しか見えない」単方向にだけ進む構造
- 双方向リスト→前も後ろも見えるので戻ることができる構造
今回の問題は単方向リストが使われています。
配列構造とは？
配列とはデータの塊のことで、「データの入った複数の箱をひとつにまとめたもの」コインロッカーのようなものを想像するとわかりやすいです。
コインロッカーには中に荷物が入っていて、自分の入れた荷物はどこに入っているかわかるように番号がついています。配列にも同じようにデータひとつひとつ(要素)が何処に入っているか分かるように印(添字)がついています。
【リスト構造】を【配列構造】を用いて表現する
ここで問題に戻ります。
「リストを二つの1次元配列で実現する。」の言いたいことはつまり「リスト構造を１次元の配列構造で表してみたい」ことを意味しています。
そして次の文章でどのように表わすのか説明に入っていきます。
「配列要素 box[i] と next[i] の対がリストの一つの要素に対応し，box[i] に要素の値が入リ，next[i] に次の要素の番号が入る。」
ここもなんだかよくわからないですよね。
リスト構造は【要素】と【ポインタ】が数珠つなぎになっている構造
box[i]の要素とnext[i]の要素ってのがあって、ボックスって名前の要素には値が入ってもう一方のネクスト要素には次の要素の番号が入るって書いてあるので、
- box[i]は要素を表している配列
- next[i]はポインタを表している配列
と書かれているのを読み取ります。
「配列が図の状態の場合，リストの3番目と4番目との間に値が H である要素を挿入したときの next[8] の値はどれか。」
いやいや・・・リストの３番目と４番目の間ってどこやねん。
ってなっているのはわかります。
リスト構造の先頭はポインタスタートで次の要素が1番目
リストはポインタをたどる必要があるのでこのデータ構造の先頭は
ポインタであるnext[0]からたどっていくことになります。
このようにBの要素が入っている添字が2のリストは次のポインタが指す住所が0なのでここでこの配列は終了です。
これの３番目と４番目の間に値がHである要素を挿入するんです！
ここで注意点としてはnext[0]のときbox[0]には値は入っていないので
ちゃんと要素が入っているAが1番目になる点です。
Hをはbox[8]なのでnext[3]は8の値が入ります。
そして次の要素がGなのでnext[8]に入る値は7となります。
よって答えは7のウとなります。
まとめ
今回は基本情報技術者試験の中でも出題頻度の高い、データ構造「配列構造」と「リスト構造」についてとその過去問の解き方についてまとめました。
問題文の意味がわからない時はその問題が基本情報技術者試験の中のどの分野の何を問いたい問題なのかを考えると良いです。
今回の場合はデータ構造の中のリスト構造について「配列構造」との違いがわかっていないと解けない問題を解説しました。
