応用情報技術者試験に頻出する連結リストについてまとめました。
連結リスト
連結リストとは
連結リストとは、ポインタでデータ同士をつないでリスト構造にしたものです。
ポインタとは、アドレス（データの位置情報）を持つデータです。
ポインタについては、C言語等を扱う人は躓くことが多い概念なので、馴染みが深いかもしれませんね。
連結リストと配列の違い
連結リストと似た概念で配列がありますが、配列ではなく連結リストを使うメリットデメリットは以下になります。
メリット
・データの追加・削除が容易
配列だとデータの挿入や削除をする際に、すべてのデータを後ろにずらす必要がありますが、連結リストであればポインタでデータ同士を繋ぎかえるだけで実現できます。
デメリット
・個々のデータにアクセスしにくい
線形リストには、個々のデータの配列番号を表す「添え字」という概念がありませんので、個々のデータに容易にアクセスできません。
線形リスト
・単方向（片方向）リスト
要素が片方向にのみ連結されるものをいいます。後ろにだけポインタがあります。
・双方向リスト
要素が双方向に連結されるものをいいます。前後にポインタがあります。
環状リスト
環状リストは、線形リストと違い最後のデータは最初のデータへのポインタがあります。
演習問題
実際の試験の過去問を解いてみましょう。
応用情報技術者試験 令和元年秋期 午前問６ 問題
| IPA 応用情報技術者試験（AP） 問題より 問6 先頭ポインタと末尾ポインタをもち、多くのデータがポインタでつながった単方向の線形リストの処理のうち、先頭ポインタ、末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで、単方向のリストは先頭ポインタからつながっているものとし、追加するデータはポインタをたどらなくても参照できるものとする。 選択肢 ア 先頭にデータを追加する処理 イ 先頭のデータを削除する処理 ウ 末尾にデータを追加する処理 エ 末尾のデータを削除する処理 |
応用情報技術者試験 令和元年秋期 午前問６ 解答
「追加するデータはポインタをたどらなくても参照できる」ということを念頭に、たどった回数をイラストで確認していきます。
ア 先頭にデータを追加する処理
イ 先頭のデータを削除する処理
ウ 末尾にデータを追加する処理
エ 末尾のデータを削除する処理
以上から、答えは「エ」となります。
連結リストの解説は以上です。
こちらに応用情報技術者試験の問題について、
解説を掲載していますので、良かったらご覧ください。
当ブログ「応用情報技術者解答解説」まとめページはこちら
