基本情報技術者 2015年 秋期 午前（科目A） 問05

ポインタを用いた線形リストの特徴【午前2 解説】

要点まとめ

• 結論：ポインタを使った線形リストでは、指定したノードの直後に新要素を追加する操作は参照の差し替えだけで済み、計算量は $O(1)$ の一定時間です。
• 根拠：各ノードが次ノードへの参照（ポインタ）を持つため、挿入は新ノードのポインタ設定と隣接ノードのポインタ更新のみで完了し、全体走査は不要だからです。
• 差がつくポイント：末尾への追加や任意位置の挿入は、末尾ポインタの有無や単方向／双方向リストの構成によって $O(1)$ か $O(n)$ に変わる点を理解しておくと差が付きます。

正解の理由

よくある誤解

• 「配列と同じく二分探索ができる」と誤解する人がいますが、線形リストはランダムアクセスが $O(n)$ のため二分探索は基本的に非効率です。
• 「ポインタの参照先を求めるのにハッシュ関数を使う」と考える人がいますが、ポインタ（アドレス）による参照は直接アクセスでありハッシュは不要です。
• 「末尾への追加は常に $O(1)$」だと誤解しがちですが、末尾ポインタを保持していない単方向リストでは末尾を探すため $O(n)$ になります。

解法ステップ

1. 各選択肢が線形リスト（連結リスト）の基本性質と一致するかを確認する。
2. 「ポインタによって指定されている要素の後ろに追加」という条件は「挿入位置が既に分かっている」状況を意味する点に注目する。
3. 挿入に必要な操作が参照の書き換え数で決まることから計算量を判断し、対比で配列や木構造、ハッシュを含む選択肢を排除する。

選択肢別の誤答解説

• ア: 「先頭の要素を根とした$n$分木で、先頭以外の要素は全て先頭の要素の子である。」
  → 誤り。線形リストは木構造ではなく各要素が1つ（単方向）または2つ（双方向）の参照を持つ直列構造です。木の“子”の概念は当てはまりません。
• イ: 「配列を用いた場合と比較して、2分探索を効率的に行うことが可能である。」
  → 誤り。二分探索にはランダムアクセスが必要で、線形リストはランダムアクセスが $O(n)$ であるため二分探索は効率的になりません。
• ウ: 「ポインタから次の要素を求めるためにハッシュ関数を用いる。」
  → 誤り。ポインタは直接アドレス参照であり、ハッシュ関数は不要かつ用途が異なります。
• エ: 「ポインタによって指定されている要素の後ろに、新たな要素を追加する計算量は、要素の個数や位置によらず一定である。」
  → 正解。挿入位置が既知ならば参照の書き換えのみで済み、時間計算量は $O(1)$ となります。

補足コラム

• 単方向リスト（singly linked list）では「指定ノードの後に挿入」は $O(1)$、しかし「値で検索して挿入位置を決める」や「インデックスで挿入位置を指定する（先頭から数える）」場合は位置特定に $O(n)$ が必要です。
• 末尾への頻繁な追加がある場合は末尾ポインタ（tail）を保持すると末尾追加を $O(1)$ にできます。双方向リスト（doubly linked list）は前後両方向の操作で利便性が増しますがポインタ分のメモリオーバーヘッドが増えます。
• 配列と比較すると、連結リストは挿入・削除が局所的に速い一方でキャッシュ局所性が悪く、ランダムアクセスやメモリ効率で不利です。

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

def insert_after(node, value):
    # node が挿入位置（直前のノード）を指すポインタ
    new_node = Node(value)
    new_node.next = node.next  # 新ノードの next を指定ノードの次に向ける
    node.next = new_node       # 指定ノードの next を新ノードに向ける
    # 以上は定数個の操作で完了する（O(1)）

FAQ