令和4年度 春期 午前Ⅰ 問題【共通】 問2

リスト（線形リスト）をメモリ上で実現する方法には、配列を用いる方法とポインタ（連結リスト）を用いる方法があり、それぞれ異なる特徴を持ちます。

配列を用いたリストの特徴

• メモリ上に連続した領域を確保してデータを格納します。
• インデックス（添え字）を指定することで、任意の要素に一定時間で直接アクセスできます。
• 配列のサイズは事前に決めておく必要があり、最大要素数に対応した領域を確保するため、実際の要素数が少ない場合は未使用の領域が発生します。
• データの挿入や削除を行う際、連続性を保つためにそれ以降の要素をすべて移動（シフト）させる必要があるため、要素数に比例した時間がかかります。

ポインタを用いたリスト（連結リスト）の特徴

• データ本体と次の要素へのポインタをペアにして格納し、ポインタで要素同士を繋ぎます。
• 必要なときに必要な分だけメモリを確保するため未使用領域は発生しませんが、ポインタを保持するための追加のメモリ領域が別途必要になります。
• 任意の要素にアクセスするには、先頭から順にポインタをたどる必要があるため、要素数に比例した時間がかかります。
• 挿入や削除の位置がわかっている場合、ポインタの繋ぎ変えだけで済むため、一定時間で処理できます。

各選択肢の解説

• ア: 正解。配列を用いたリストは、事前に最大要素数分の連続した領域を確保するため、実際には使用されない領域が発生する可能性があります。
• イ: 誤り。リストの先頭から順番に要素をたどって要素数に比例した時間が必要となるのは、ポインタを用いたリストの特徴です。配列を用いたリストは、インデックスを用いて中間要素にも一定時間でアクセス可能です。
• ウ: 誤り。要素を格納する領域のほかに次の要素を指し示す領域（ポインタ）が必要となるのは、ポインタを用いたリストの特徴です。
• エ: 誤り。要素の挿入位置が分かる場合に一定時間で挿入できるのは、ポインタを用いたリストの特徴です。配列を用いたリストでは、挿入位置以降の要素をすべて後ろにずらす必要があるため、要素数に比例した時間が必要となります。