単方向線形リストにおけるポインタ辿り回数の比較

正解は エ です。 単方向線形リストにおいて、末尾のデータを削除するには、末尾ノードの直前のノードを探し出し、その次ポインタを null に更新した上で末尾ポインタをその直前ノードに向ける必要があります。 しかし単方向リストではポインタを逆方向にたどることができないため、先頭ポインタから開始して末尾の直前ノードまでリストの全ノード（要素数を $n$ とすると $n-1$ 回）を順番に走査しなければなりません。したがって、ポインタをたどる回数が最も多くなります（$O(n)$）。 新ノードの次ポインタを現在の先頭ノードに向け、先頭ポインタを新ノードで更新するだけで完了するため、ポインタをたどる回数は 0 回です（$O(1)$）。 先頭ポインタから先頭ノードを参照し、先頭ノードが保持する次ノードアドレスを先頭ポインタに設定するだけなので、ポインタをたどる回数は 1 回で済みます（$O(1)$）。 末尾ポインタから現在の末尾ノードを参照し、その次ポインタを新ノードに向けて末尾ポインタを更新するため、ポインタをたどる回数は 1 回で済みます（$O(1)$）。 処理 必要なポインタのたどり方 回数 ア 先頭に追加 先頭ポインタを書き換えるだけ 0回 イ 先頭を削除 先頭ポインタから1つ先へ 1回 ウ 末尾に追加 末尾ポインタから末尾の要素へ 1回 エ 末尾を削除 末尾の1つ前を先頭から順に探す 約 n 回

先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで，単方向のリストは先頭ポインタからつながっているものとし，追加するデータはポインタをたどらなくても参照できるものとする。

出典令和元年 秋期 応用情報技術者試験 午前 問6
ア
先頭にデータを追加する処理
イ
先頭のデータを削除する処理
ウ
末尾にデータを追加する処理
エ
末尾のデータを削除する処理