配列によるリスト構造とポインタによるリスト構造の特徴

配列によるリスト構造では、連続したメモリ領域に要素を格納するため、あらかじめ想定される最大要素数分の静的領域を確保しておく必要があります。そのため、実際の要素数が少ない場合には使用されない無駄な領域(空き領域)が発生します。 先頭から順にたどる必要があるのはポインタによるリスト構造の特徴です。配列によるリストでは添字(インデックス)を指定して $O(1)$ の一定時間で任意の位置の要素を参照できます。 次の要素を指し示すポインタ領域が必要となるのはポインタによるリスト構造の特徴です。配列によるリストでは要素そのもののみを連続して格納します。 挿入位置が分かっていればポインタの付け替えのみで $O(1)$ で挿入できるのはポインタによるリスト構造の特徴です。配列によるリストでは挿入位置以降の全要素を後ろへずらす(シフトする)必要があるため、要素数に比例した時間($O(n)$)がかかります。

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

出典令和4年度 春期 応用情報技術者試験 午前 問5
ア
リストにある実際の要素数にかかわらず,リストに入れられる要素の最大個数に対応した領域を確保し,実際には使用されない領域が発生する可能性がある。
イ
リストの中間要素を参照するには,リストの先頭から順番に要素をたどっていくことから,要素数に比例した時間が必要となる。
ウ
リストの要素を格納する領域の他に,次の要素を指し示すための領域が別途必要となる。
エ
リストへの挿入位置が分かる場合には,リストにある実際の要素数にかかわらず,要素の挿入を一定時間で行うことができる。