応用情報技術者 2009年 秋期 午前2 問05

連結リストの末尾追加と削除時間の比率【午前2 解説】

正解の理由

解法ステップ

1. 実装方法1の構造を確認し、末尾ポインタがないことを理解する。
2. 末尾追加は末尾まで探索が必要で$O(n)$、末尾削除も同様に$O(n)$。
3. 実装方法2は末尾ポインタrearがあり、追加は$O(1)$で可能。
4. しかし削除は単方向リストのため、末尾の一つ前を探す必要があり$O(n)$。
5. それぞれの$f(n)$と$g(n)$の時間計算量を比較し、比率を求める。

選択肢別の誤答解説

• ア：両方とも比率が1になるとあるが、実装方法2は追加が$O(1)$で削除が$O(n)$なので誤り。
• イ：正解。実装方法1は比率1、実装方法2は比率$n$に比例。
• ウ：実装方法1が比率$n$に比例は誤り。末尾追加も削除も$O(n)$で比率は1。
• エ：両方とも比率$n$に比例は誤り。実装方法1は比率1。

よくある誤解

補足コラム

FAQ