基本情報技術者 2009年 春期 午前（科目A） 問06

連結リストの挿入と操作特性【午前解説】

正解の理由

解法ステップ

1. 各選択肢が説明している操作（更新・削除・参照・挿入）を明確にする。
2. 連結リストの基本特性を思い出す：ノードはポインタで連結、物理的な要素移動は不要。
3. 操作を「位置が既知か否か」で分ける：位置既知なら挿入・削除は $O(1)$、位置特定が必要なら探索に $O(n)$。
4. 配列との比較：配列はランダムアクセス $O(1)$、挿入・削除はシフトが必要で最悪 $O(n)$。
5. 各選択肢と上記性質を照らし合わせて正誤を判断する。

選択肢別の誤答解説

• ア: 要素を更新する場合、ポインタを順番にたどるだけなので、処理時間は短い。
  → 誤り。要素の更新（値の代入）自体は $O(1)$ だが、更新対象のノードを見つけるために先頭から辿る必要があるなら探索に $O(n)$ かかる。選択肢は「順番にたどるだけ」と書いているが、これが必要であれば短いとは言えない点を混同している。
• イ: 要素を削除する場合、削除した要素から後ろにあるすべての要素を前に移動するので、処理時間は長い。
  → 誤り。これは配列の挙動であり、連結リストでは要素を物理移動しない。前後のポインタを書き換えるだけで済むため、削除自体は位置が既知なら $O(1)$。ただし前ノードを探す必要があれば探索で $O(n)$。
• ウ: 要素を参照する場合、ランダムにアクセスできるので、処理時間は短い。
  → 誤り。連結リストはランダムアクセスができず、任意の位置の参照には先頭から辿る必要があり $O(n)$。配列のみがインデックスで即時参照 $O(1)$ を提供する。
• エ: 要素を挿入する場合、数個のポインタを書き換えるだけなので、処理時間は短い。
  → 正しい。挿入位置が分かっていれば数個のポインタ更新で済み、操作自体は $O(1)$。

よくある誤解

• 「更新（代入）は常に連結リストが速い」：ノードの値を書き換える操作自体は $O(1)$ だが、対象ノードを見つけるための探索が必要なら全体で $O(n)$ になる点を見落としやすい。
• 「削除は配列と同じで要素を移動する」：連結リストでは物理的に要素を前に移動する必要はなくポインタを書き換えるだけで済むため、削除自体は $O(1)$（位置が分かっている場合）である。
• 「連結リストはランダムアクセスができる」：インデックスで即座にアクセスできるのは配列のみで、連結リストは先頭から順に辿る必要がありランダムアクセスはできない。

補足コラム

• 単方向連結リストと双方向（ダブル）連結リスト：単方向は前ノードが分からないと前方参照のみなので削除で前ノード探索が必要、双方向は前後両方向のポインタを持ち削除・逆走行が容易だがポインタ数とメモリオーバーヘッドが増える。
• メモリ局所性：配列は連続メモリに格納されキャッシュヒット率が高く高速に動作する場面が多い。一方連結リストは散在するメモリを参照するためキャッシュ効率が悪い。
• 実用的選択基準：頻繁にランダムアクセスが必要なら配列（または配列ライクな構造）、頻繁に途中挿入・削除が必要で挿入位置が既知なら連結リストが有利。

FAQ