データ構造のキューを実現する方法において、片方向リンクに比べた場合の双方向リンクの特徴として、適切なものはどれか。
ア | 片方向リンクよりオーバヘッドが小さい。 |
イ | 追加は、最後尾だけに対して行える。 |
ウ | 途中への挿入・取外しが容易に行える。 |
エ | 取外しは、先頭だけに対して行える。 |
答え ウ
【解説】
ア | 双方向リストは、データの追加、挿入、取外しを行うとき、片方向リストと比べリンク(ポインタ)の操作が多いのでオーバヘッドが大きい。 |
イ | 片方向リスト、双方向リストともに追加はどこにでも行うことができる。 (ただし、キューであれば、追加を行うのは最後尾だけです。) |
ウ | あるデータの前に追加を行うという処理を考えた場合、双方向リンクではポインタの操作のみで可能ですが、片方向リンクではあるデータの現在の前のデータを先頭から探す必要があり、処理が複雑になります。 |
エ | 片方向リスト、双方向リストともに取外しはどこからでも行うことができる。 (ただし、キューであれば、取外しを行うのは先頭だけです。) |
【キーワード】
・キュー
・リンク