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

ポインタ線形リストの挿入【午前2解説】

正解の理由

解法ステップ

1. 問題がどの操作について問うているかを確認する（今回：ある要素の「後ろに追加する」操作）。
2. 「挿入位置を示すポインタが与えられているか」を考える。与えられているなら探索は不要。
3. ポインタ更新だけで済むか（$O(1)$）を判断する。探索が必要なら $O(n)$。
4. 他の選択肢がデータ構造の性質や利用方法と矛盾しないかを確認する。

選択肢別の誤答解説

• ア: 「先頭の要素を根とした n 分木で、先頭以外の要素は全て先頭の要素の子である」
  → 連結リストは線形構造であり、木構造の記述ではない。先頭の要素がすべての要素の親となるのは誤り。
• イ: 「配列を用いた場合と比較して、2分探索を効率的に行うことが可能である」
  → 二分探索はランダムアクセスが前提（添字で中間要素へ直接アクセスできること）であり、連結リストは中間要素への直接アクセスができないため二分探索は非効率（一般に $O(n)$ のアクセスが必要）。したがって誤り。
• ウ: 「ポインタから次の要素を求めるためにハッシュ関数を用いる」
  → ポインタ（参照）は次ノードのアドレス（参照）を直接保持する。ハッシュ関数は不要であり適切でない。誤り。
• エ: 「ポインタによって指定されている要素の後ろに、新たな要素を追加する計算量は、要素の個数や位置によらず一定である」
  → 挿入位置を示すノードの参照が既にある場合、ポインタ更新のみで済むため一定時間（$O(1)$）。ここが妥当なので正しい。

よくある誤解

1. 「末尾への追加＝常に $O(1)$」と考える誤解
   • 末尾に追加しても、末尾を指すポインタ（tail）が保持されていなければ最後まで探索する必要があり $O(n)$ になる。末尾ポインタを持っていれば末尾追加は $O(1)$ にできる点を区別すること。
2. 「連結リストならどの挿入も $O(1)$」という誤解
   • 任意の位置に挿入するためにその位置を見つける探索が必要なら総コストは探索時間を含む（位置不明なら $O(n)$）。挿入自体は $O(1)$ でも、位置決定が時間を要する点を見落とさないこと。
3. 「二分探索はどんな線形構造でも速い」
   • 二分探索は配列のランダムアクセスを前提とするため、連結リストでは適用できない（アクセスコストが増え、アルゴリズム全体はむしろ遅くなる）。

補足コラム

# node は挿入位置のノードへの参照、new_node は挿入するノード
new_node.next = node.next
node.next = new_node

FAQ