■

　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 に比例する。 │
└──┴──────────┴──────────┘