連結リストの構造とポインタ操作：単方向・双方向リストのノード挿入・削除完全攻略

プログラミングとアルゴリズム分野において、配列と並ぶ最重要の基本データ構造が「連結リスト（リンクリスト：Linked List）」です。

特に「配列と連結リストの計算量・メモリ配置の違い」「単方向リストと双方向リストの構造」「ノードの挿入・削除におけるポインタ繋ぎ替えの厳密な順序」は、擬似言語読解問題で頻出する定番論点です。

ポインタの更新順序を1行でも誤ると、後続ノードのアドレスを見失ってデータ全体が消失する致命的バグ（参照消失）につながります。本記事では、ポインタ操作のメカニズムを図解付きで完璧に整理します。

1. 配列（Array）vs 連結リスト（Linked List）の完全対比

データを一列に並べるデータ構造として、配列と連結リストは対極の特徴を持ちます。

2. リストのバリエーション（単方向・双方向・循環リスト）

連結リストには、ポインタの張り方に応じて3つの主要なバリエーションが存在します。

3. ノード挿入・削除のポインタ繋ぎ替え手順（最重要）

試験で最も狙われるのが、ノード挿入時の「ポインタ書き換え順序の鉄則」です。

【ノードP の直後に 新ノード NewNode を挿入する場合】

// 正しい手順（この順序でなければならない！）
NewNode.next ← P.next;   // ステップ1: まず新ノードの先を、Pの次のノード（後続）に繋ぐ
P.next ← NewNode;        // ステップ2: その後で、Pの先を新ノードへ繋ぎ替える

【超重要：逆順に書くと大惨事になる理由】もし先に「P.next ← NewNode」を実行してしまうと、Pがもともと指していた後続ノードへの唯一の参照アドレスが上書きされて消滅してしまいます。その結果、NewNode.next に後続ノードを繋ぐことが不可能になり、後続のリスト全体がメモリの海へ孤立・消失（参照喪失）してしまいます。

【ノードP の直後にある ノードQ を削除する場合】

// 削除の手順（Pの先を、Qの次のノードへ直接スキップさせる）
P.next ← Q.next;         // ノードPがノードQを飛び越えて次のノードを直接指す
// （Qはリストから外れるため、ガベージコレクション等でメモリ解放される）

4. 擬似言語による連結リスト走査と番兵（Sentinel）の役割

先頭ノードを指すポインタを「head」と呼びます。リストの全ノードを末尾まで巡回する基本コードは以下の形を取ります。

// 連結リストの全要素を末尾まで走査する基本形
current ← head
while (current ≠ nil)
    出力(current.data)
    current ← current.next
endwhile

また、先頭や末尾への挿入・削除において「headがnilかどうかの条件分岐」を省くため、実データを持たないダミーノードを先頭に常駐させる手法を「番兵（Sentinel / ダミーノード）」と呼びます。

5. 実戦演習問題とステップ別解説

【問1：単方向連結リストへのノード挿入のコード穴埋め】

ポインタ p が指すノードの直後に、新たに生成したノード new_node を挿入したい。適切な処理手順はどれか。

• ア：p.next ← new_node ; new_node.next ← p.next

• イ：new_node.next ← p.next ; p.next ← new_node

• ウ：new_node.next ← p ; p.next ← new_node.next

• エ：p.next ← new_node.next ; new_node.next ← p

【正解】イ

【解説】ノード挿入では「後続ノードを見失わないように、まず新ノードの next に後続アドレス（p.next）を代入する」のが大原則です。したがって最初に「new_node.next ← p.next」を行い、その後に「p.next ← new_node」で先行ノードの向き先を新ノードへ更新します。アの順序で行うと、new_node.next に new_node 自身が代入されて自己ループになってしまいます。正解は イ です。

【問2：配列と連結リストの計算量比較】

要素数 n のデータ構造に対する操作のうち、配列と比べて連結リストが計算量的に優れている（所要時間が短い）操作はどれか。

• ア：先頭から k 番目（1 < k < n）の要素の値を読み出す操作

• イ：ポインタで指定された特定ノードの直後に新たな要素を1個挿入する操作

• ウ：二分探索法を用いて目的のデータ値を高速に検索する操作

• エ：全要素のメモリ領域を単一の連続アドレスとして確保する操作

【正解】イ

【解説】特定の位置（ポインタ）がすでに判明している場合、連結リストへの挿入は前後のポインタを繋ぎ替えるだけなので O(1) で完了します。配列の場合は後続の要素を1つずつ後ろへずらすシフト処理が発生するため O(n) の時間がかかります。アとウはランダムアクセスが得意な配列が O(1), O(log n) で優れており、エは連続領域を必要とする配列の特徴です。正解は イ です。