n 個の要素x1, x2, …, xn から成る連結リストに対して、新たな要素xn +1の末尾への追加に要する時間をf (n )とし、末尾の要素xn の削除に要する時間をg (n )とする。
n が非常に大きいとき、実装方法1と実装方法2における
の挙動として、適切なものはどれか。
[実装方法1]
先頭のセルを指すポインタ型の変数frontだけをもつ。
[実装方法2]
先頭のセルを指すポインタ型の変数frontと、末尾のセルを指すポイント型の変数rearを併せもつ。
| 実装方法1 | 実装方法2 | |
| ア | ほぼ1になる。 | ほぼ1になる。 |
| イ | ほぼ1になる。 | ほぼn に比例する。 |
| ウ | ほぼn に比例する。 | ほぼ1になる。 |
| エ | ほぼn に比例する。 | ほぼn に比例する。 |
答え イ
【解説】
連結リストの要素の追加・削除処理では要素の数n が大きくなると、リストをたどる時間が大きくなり、処理時間はリストをたどる時間で決まることになる。
実装方法1では新たな要素を末尾に追加するときも、末尾の要素を削除するときも、変数frontから末尾までリストを順にたどって処理する必要があるため、f (n )とg (n )の時間に大きな差は発生しない。
実装方法2では新たな要素を末尾に追加するときは変数rearを利用するとリストの最後をすぐに知ることができるが、末尾の要素を削除するときは変数rearが指しているxn からxn -1をたどる手段はなく、実装方法1と同様に変数frontから末尾までリストを順にたどる必要があるので、末尾の要素を削除する処理時間g (n )は末尾に要素を追加するf (n )のn 倍の時間がかかる事になる。
【キーワード】
・連結リスト
- 連結リスト
データ構造の一種で、データのリストの中に次のリストを示すリンク(ポインタ)を持っている。
片方向リスト
双方向リスト
もっと、「連結リスト」について調べてみよう。
戻る
一覧へ
次へ