問題3
n 個の要素x 1，x 2，…，x n から成る連結リストに対して、新たな要素x n +1の末尾への追加に要する時間をf (n )とし、末尾の要素x n の削除に要する時間をg (n )とする。n が非常に大きいとき、実装方法1と実装方法2における
の挙動として、適切なものはどれか。
| [実装方法1] | |
| 先頭のセルを指すポインタ型の変数frontだけをもつ。 | |
 |
| [実装方法2] | |
| 先頭のセルを指すポインタ型の変数frontと、末尾のセルを指すポインタ型の変数rearを併せもつ。 | |
 |
解答・解説を見る
解答：イ
- [実装方法1]
- 新たな要素を追加する際には先頭から順に最後まで辿らなくてはならず、処理時間f(n) はn が増えるほど増加するのでn に比例することになる。同じように削除処理時間g(n)もｎが増えれば同様にn に比例するのでg(n)/f(n)はほぼ1になる。
- [実装方法2]
- 追加の場合はポインタrearのアドレス指定に従い1つ追加するだけなので処理時間はほぼ1になる。削除する場合はrearからは1つ前のアドレスがわからないためfrontから順に辿らなくてはならず、作業時間g(n)はn に比例します。よってg(n)/f(n)はnに比例する。