分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：データ構造

2つの連結構造(単方向リスト・双方向リスト)において、

• 新要素の末尾への追加 f(n)
• 末尾の要素の削除 g(n)

に要する時間の関係を考える問題です。
※一回のポインタ参照→次のセルへのアクセスに要する時間は一定であるとし、処理に要する時間は、このセル移動に回数に比例するものとします。

まず〔実装方法1〕について考えます。
"新要素(n+1)の末尾への追加"は、 ポインタfrontからリスト構造を末尾のデータ(n)まで順にたどり、末尾のデータのポインタ部を新しい要素へのポインタにします。したがって、セル移動の回数はn回です。　
"末尾の要素の削除"は、ポインタfrontから末尾の要素の一つ前の手前の要素(n-1)までたどり、末尾の要素へのポインタを削除します。したがって、セル移動の回数はn-1回です。

nは非常に大きいという条件があるので、〔実装方法1〕のは、(n-1)／nでほぼ1となります。

次に〔実装方法2〕について考えます。
"新要素(n+1)の末尾への追加"は、 ポインタrearを参照することで1回で末尾のセルへアクセスし、末尾のデータのポインタ部を新しい要素へのポインタにします。したがって、セル移動の回数は1回です。　
"末尾の要素の削除"は、〔実装方法1〕と同様に、ポインタfrontから末尾の要素の一つ前の手前の要素(n-1)までたどり、末尾の要素へのポインタを削除します。この場合では、ポインタrearから末尾のセルへ移動することはできても、「末尾のセルからその一つ手前のセルへはポインタがないため戻ることができない」という点が理解できているかがポイントになります。したがって、セル移動の回数はn-1回です。

〔実装方法2〕の、は、(n-1)／1でほぼnに比例となります。

以上より〔実装方法1〕＝"ほぼ1となる"、〔実装方法2〕＝"ほぼ n に比例する"の組合せで「イ」が正解となります。