2009年度 秋期 ネットワークスペシャリスト 午前I 問3

実装方法2は、先頭のポインタ front に加えて、末尾のセルを指すポインタ rear を持ちます。このrearポインタを利用することで、末尾への要素追加は直接末尾のセルに新しい要素を連結できるため、定数時間O(1)で完了します。末尾要素の削除も、rearポインタから一つ前の要素をたどることで、これも定数時間O(1)で実現できます。したがって、f(n)はほぼ1に比例し、g(n)もほぼ1に比例します。

アは、実装方法2における末尾要素の削除時間がnに比例すると誤っています。実装方法2ではrearポインタがあるため、末尾削除は定数時間で可能です。

ウは、実装方法1における末尾への要素追加時間が1に比例すると誤っています。実装方法1では末尾への追加はリストの走査が必要なため、nに比例します。

エは、実装方法1における末尾への要素追加時間と、実装方法2における末尾要素の削除時間が共にnに比例すると誤っています。実装方法2ではrearポインタにより末尾操作が効率化されます。