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

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

要点まとめ

• 結論：実装方法1は末尾削除が$O(n)$、末尾追加が$O(n)$で比率はほぼ1、実装方法2は末尾削除が$O(n)$、追加が$O(1)$で比率は$n$に比例します。
• 根拠：実装方法1は末尾ポインタがなく末尾探索が必要、実装方法2は末尾ポインタがあり追加は定数時間、削除は先頭から探索が必要です。
• 差がつくポイント：末尾ポインタの有無で追加操作の時間が大きく変わり、削除操作はどちらも末尾探索が必要なため$O(n)$です。

正解の理由

よくある誤解

解法ステップ

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