令和4年度 春期 応用情報技術者試験 午前 問5
テクノロジ／アルゴリズムリストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要素を連続して格納することによってリストを構成し，ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。
出典：令和4年度 春期 応用情報技術者試験 午前 問5
- アリストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。
- イリストの中間要素を参照するには，リストの先頭から順番に要素をたどっていくことから，要素数に比例した時間が必要となる。
- ウリストの要素を格納する領域の他に，次の要素を指し示すための領域が別途必要となる。
- エリストへの挿入位置が分かる場合には，リストにある実際の要素数にかかわらず，要素の挿入を一定時間で行うことができる。
正解：ア
解説
配列によるリストは，あらかじめ最大要素数分の連続領域を確保して要素を詰めて格納します。そのため実際の要素数が少ないと未使用領域が生じます。一方，添字で直接アクセスできるため中間要素の参照は一定時間で行えますが，挿入・削除では後続要素の移動が必要です。
選択肢ごとの解説
- ア正しい。配列は最大個数に対応した領域をあらかじめ確保するため，要素数が少ないときは使用されない領域が発生する可能性があります。
- イ誤り。先頭から順にたどる必要があるのはポインタを用いたリストの特徴です。配列では添字によって中間要素に一定時間でアクセスできます。
- ウ誤り。次の要素を指すポインタ領域が別途必要になるのは，ポインタを用いたリストの特徴です。
- エ誤り。配列への挿入は挿入位置以降の要素を後ろへずらす必要があるため，要素数に比例した時間が掛かります。一定時間で挿入できるのはポインタを用いたリストです。