[記事公開日]2015/01/31
[最終更新日]2016/11/29

基本情報技術者試験 2-3(リスト構造)

 

 

今回は「リスト構造」についてです。

 

前回は「配列」について学びました。

 

基本情報技術者試験では、「配列構造」と「リスト構造」をよく理解しましょう。

簡単な問題から、午後のアルゴリズムの問題にまで登場してきますので、どんな構造かくらいは覚えておきましょう。

 

「配列」と「リスト構造」とはどんなのか覚えるだけです。

 

めちゃくちゃ簡単です。(笑)

 

●配列

・順番通り

・削除、挿入が手間

・順番にデータを参照するのに楽

 

でしたね。

 

では、リストは?

 

●リスト

・データの前後に、「受取」と「送信」の情報持っています。

・リストがたくさん連携されて「リスト構造」といいます。

※単体では「リスト」ですが、リスト単体というのが現実的に意味ないことなので、「リスト構造」と呼んでよろしいかと思います。

 

●付加された前後の部分を「ポインタ」と呼びます。データ部分とは別に「ポインタ」を持っています。

リスト構造

 

●次のデータへのポインタのみもつリスト

⇒単方向リスト

リスト構造(2)

 

●前後のポインタをもつリスト

⇒双方向リスト(真ん中のやつ)

双方向

 

●(そもそもの話・・)・データが環状に連結されているリスト構造

⇒環状リスト(リスト構造は環状リストだよねーというだけの話し)

環状リスト

 

 

 

なんとなく理解できましたか・・?

 

では、どのような問題が出題されるのでしょうか。

 

リスト問題

 

上の様なリスト構造があります。

駅名でしょう。

 

よく見ると「ポインタ」の順番がバラバラです。

 

「アドレス」というのは、その名の通り「住所」という意味です。居場所を差します。

 

東京の次は新横浜となり、続いて熱海がきます。

ポインタがアドレスを指定しているだけの話しです。

 

では、新しく「静岡」をどこかに挿入したいとなると、どのようなリスト構造にすればよいでしょうか。

 

●解答の手順

※熱海と浜松に「静岡」を挿入する場合で考えると・・

 

まずは、アドレスを適当に作ってあげます。もちろん、どこかのデータアドレスと重複しないようにです。

今回はアドレス「150」で静岡を作りました。

次に、ポインタを変更してあげます。

前の駅である「熱海」から、引き継がなければいけないので、熱海のポインタを「150」にしておきます。

次に、次の駅である「浜松」のアドレスを指定します。「70」です。

 

<変更前>

リスト問題(3)

<変更後>

リスト問題(4)

 

 

どうでしょうか。

 

ズルズルと変更してしまいましたが、変更したのは赤字で示した、たったの2箇所です。

 

ポインタ値を2箇所変えてあげただけです。

 

「リスト構造に挿入~」ときて、選択肢の既存データの「アドレス」が変わっていたら、すぐにその選択肢は消去できる!

 

①変更後の値(数字)を選択肢で問われる場合もあれば、

 

②変更が必要な箇所を問われる場合もあります。

 

このリスト構造の構成と「アドレス」「ポインタ」の語句を理解していれば、心配ご無用です。

 

ーー基本情報技術者試験 2-3(リスト構造)ーー

☆リスト構造は、アドレスがあってポインタが次のアドレスを指定してあげる

☆リスト構造は「環状リスト」ともいえる。配列みたいに一方通行じゃないから。

☆挿入があると、アドレスは変わる必要がなくって、ポインタだけを変えればよい。

 

 

以上です

 

 

yamatunes