応用情報技術者試験 応用情報技術者試験 令和4年度春期 午前 問5: リストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要

問題本文

リストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要素を連続して格納することによってリストを構成し，ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。

選択肢

• ア.リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。
• イ.リストの中間要素を参照するには，リストの先頭から順番に要素をたどっていくことから，要素数に比例した時間が必要となる。
• ウ.リストの要素を格納する領域の他に，次の要素を指し示すための領域が別途必要となる。
• エ.リストへの挿入位置が分かる場合には，リストにある実際の要素数にかかわらず，要素の挿入を一定時間で行うことができる。

正解

ア. リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。

解説

配列によるリストとポインタ(連結リスト)によるリストの特徴を対比させる問題です。配列はあらかじめ連続した記憶領域をまとめて確保する必要があるため、入れられる最大個数ぶんの領域を先に予約し、実際の要素数がそれより少ないと使われない領域が無駄になります。これが配列で実現したリストの特徴であり、正解はアです。一方、添字計算で任意位置に直接アクセスできる(中間要素も先頭からたどらない)、ポインタ用の領域が不要、という点が配列の長所で、イ・ウ・エはいずれも連結リスト側の説明です。

選択肢ごとの解説

• ア.配列は連続領域を最大要素数ぶん先に確保するため、実際の要素数が少ないと未使用領域が生じる。これは配列で実現したリストの特徴で正解。
• イ.先頭から順にたどるので要素数に比例した時間がかかるのは連結リストの特徴。配列は添字計算で中間要素にも一定時間で直接アクセスできるため誤り。
• ウ.次の要素を指すポインタ用の領域が別途必要なのは連結リストの特徴。配列は要素を連続配置するためポインタ領域は不要で誤り。
• エ.挿入位置が分かればポインタの付け替えだけで一定時間に挿入できるのは連結リストの特徴。配列は挿入位置以降の要素をずらす必要があり要素数に依存するため誤り。