線形リストの特徴
出典: 令和2年度 10月 応用情報技術者試験 午前 問5 (IPA)
ポインタを用いた線形リストの特徴のうち，適切なものはどれか。
- ア 先頭の要素を根とした n 分木で，先頭以外の要素は全て先頭の要素の子である。
- イ 配列を用いた場合と比較して，2 分探索を効率的に行うことが可能である。
- ウ ポインタから次の要素を求めるためにハッシュ関数を用いる。
- エ ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。
正解と解説を見る
正解: エ
- ア: 先頭以外の全要素が先頭の子になる木構造は、線形リストではありません。
- イ: 線形リストは途中の要素に直接アクセスできないので、2 分探索は配列の方が効率的です。
- ウ: 次の要素はポインタで直接示されているので、ハッシュ関数は使いません。
- エ: 指定された要素の後ろに追加するときは、ポインタを付け替えるだけなので、要素数や位置によらず一定の手間でできます。正しい記述です。
ポイント
- 線形リスト: 各要素が、次の要素の場所を示す ポインタ を持ち、数珠つなぎになったデータ構造です。
- 要素を追加・削除するときは、前後のポインタを付け替えるだけなので、要素数や位置によらず一定の手間 (O(1)) でできます (追加する位置が分かっている場合)。
- 一方で、途中の要素を探すには先頭から順にたどる必要があるので、2 分探索には向きません。