n 個の要素 x1,x2,…,xn から成る連結リストに対して,新たな要素 x[n + 1]
の末尾への追加に要する時間を f(n) とし,末尾の要素 xn の削除に要する時間を
g(n)とする。n が非常に大きいとき,実装方法 1 と実装方法 2 における
g(n) / f(n) の挙動として,適切なものはどれか。
[実装方法 1] 先頭のセルを指すポインタ型の変数 front だけをもつ。 ┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ front |●┼─>|x1|●┼─>|x2|●┼─> … ──>|xn|/| └─┘ └─┴─┘ └─┴─┘ └─┴─┘ [実装方法 2] 先頭のセルを指すポインタ型の変数 front と,末尾のセルを指すポインタ型の 変数 rear を併せもつ。 ┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ front |●┼─>|x1|●┼─>|x2|●┼─> … ──>|xn|/| └─┘ └─┴─┘ └─┴─┘ ┐└─┴─┘ ┌─┐ / rear |●┼──────────────────/ └─┘ ┌──────────┬──────────┐ │ 実装方法 1 │ 実装方法 2 │ ┌──┼──────────┼──────────┤ │ ア │ほぼ 1 になる。 │ほぼ 1 になる。 │ ├──┼──────────┼──────────┤ │ イ │ほぼ 1 になる。 │ほぼ n に比例する。 │ ├──┼──────────┼──────────┤ │ ウ │ほぼ n に比例する。 │ほぼ 1 になる。 │ ├──┼──────────┼──────────┤ │ エ │ほぼ n に比例する。 │ほぼ n に比例する。 │ └──┴──────────┴──────────┘