応用情報技術者試験 令和４年春期 問５
リストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要素を連続して格納することによってリストを構成し，ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。
ア：リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。
イ：リストの中間要素を参照するには，リストの先頭から順番に要素をたどっていくことから，要素数に比例した時間が必要となる。
ウ：リストの要素を格納する領域の他に，次の要素を指し示すための領域が別途必要となる。
エ：リストへの挿入位置が分かる場合には，リストにある実際の要素数にかかわらず，要素の挿入を一定時間で行うことができる。
出典 IPA公開[過去問題]：https://www.ipa.go.jp/shiken/mondai-kaiotu/gmcbt80000009sgk-att/2022r04h_ap_am_qs.pdf
配列内にあるデータにアクセスする場合は、配列の何番目にアクセスするのかを番号で指定します。この番号を「要素番号」と言います。配列を使用する際は配列の要素数を指定することがあります。
要素数を指定して配列を用意した場合、要素数は最初からわかっているので「要素数÷２」をすることで中間位置の要素番号を求めることができるので先頭から順番に辿る必要はありません。しかし、要素数を指定しても全ての要素にデータを入れるとは限りません。この場合は実施には使用されない領域が発生します。
正解は、「ア：リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。」です。
ポインタの場合は各要素に次の要素の場所を示した情報も保存して先頭要素から順番に辿っていきます。配列と違って要素番号でアクセスするわけではないので、配列の様に中間位置に直接アクセスすることができず、先頭から順にリストのデータ個数の半分の回数分辿ります。
結果、配列よりも時間がかかります。