平成25年秋期問6 リストを配列で実現した場合の特徴

基本情報技術者平成25年秋期午前問6

リストは，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。

テクノロジ系 » アルゴリズムとプログラミング » データ構造

ア

正しい。配列で実現するリストの特徴です。配列を用いる場合は最大の要素数を格納できるだけのメモリ領域を確保する必要があります。1000要素分確保しても実際の格納数が10要素程度だとすると、残りの990要素分のメモリ領域が無駄になってしまいます。
配列リストに挿入する場合は挿入位置より後ろの要素を1つずつ後ろの領域へ移動しなくてはなりません。また削除する場合は削除位置より後方の要素を1つずつ前に移動する必要があります。これは要素が後方に存在する数の多い、配列リストの前方への挿入・削除ほど処理に時間がかかることを意味します。
ポインタで実現するリストの特徴です。配列リストでは要素をメモリ上の連続した領域に格納するので、添え字と一要素のデータサイズから参照すべきメモリアドレスをすぐに計算することができます。したがって要素の格納位置に関わらず参照時間は一定になります。
ポインタで実現するリストの特徴です。配列リストは連続したメモリ領域に添え字順に要素を格納するので、次の要素の位置を容易に計算することができます。したがってポインタリストのように次の要素へのポインタを保持しておく必要はありません。