連結リストの構造とポインタ操作：単方向・双方向リストのノード挿入・削除完全攻略
リストへノードを挿入するとき、どちらのnextを先に書き換えるのでしょうか？
後続への参照を保存してから、前のノードをつなぎ替えます。参照が変わる順序を追い、先頭・末尾の操作や双方向リストも確認します。
配列（Array）vs 連結リスト（Linked List）の確認
データを一列に並べるデータ構造として、配列と連結リストは対極の特徴を持ちます。
比較項目 | 配列 (Array) | 連結リスト (Linked List) |
|---|---|---|
メモリ上の配置 | 連続した単一のメモリ領域に並んで配置される。 | メモリ上の離れた場所（ヒープ領域等）に飛び飛びで存在。 |
要素の構成 | データ値のみが連続して格納される。 | 各要素（ノード）が「データ値」と「次ノードへのポインタ（参照）」を保持。 |
ランダムアクセス (i番目の参照) | O(1) で即時アクセス可能！（先頭アドレス ＋ i × 要素サイズ で計算） | O(n) の時間がかかる（先頭からポインタを i 回たどる必要がある）。 |
中間への挿入・削除 | O(n)（後続の全要素を前後にシフト・前詰めするコスト大） | 位置と必要な前ノードが既知なら、参照のつなぎ替えはO(1)。位置を探す時間は別に必要。 |
要素数の動的伸縮 | 静的配列ではサイズ変更不可（再確保と全コピーが必要）。 | ノードを都度生成・解放できるため、メモリが許す限り柔軟に伸縮可能。 |
リストのバリエーション（単方向・双方向・循環リスト）
連結リストには、ポインタの張り方に応じて3つの主要なバリエーションが存在します。
種類 | ノードの保持するポインタ | 特徴と用途 | 注意点 |
|---|---|---|---|
単方向リスト (Singly Linked List) | 次ノードへのポインタ (next) のみ | 一方向（先頭から末尾）へしか巡回できない。メモリ消費が最小限で済む。 | あるノードの直前ノードを取得するには先頭から再探索が必要。 |
双方向リスト (Doubly Linked List) | 前ノードポインタ (prev) と次ノードポインタ (next) の両方 | 前後どちらの向きにも自由に走査可能。削除処理を直前探索なしで実行できる。 | nextとprevの両方の整合性を保つ必要がある。境界や実装によって更新する数は異なる。 |
循環リスト (Circular Linked List) | 末尾ノードの next が先頭ノードを指す | 先頭と末尾が環状に繋がっている。ラウンドロビンスケジューリング等の巡回処理に最適。 | 開始ノードへ戻ったかなどで終了を判断する。空リストや1ノードの扱いも確認する。 |
ノード挿入・削除のポインタ繋ぎ替え手順（最重要）
試験で最も狙われるのが、ノード挿入時の「ポインタ書き換え順序の鉄則」です。
ノードP の直後に 新ノード NewNode を挿入する場合
// Pは既存ノード、NewNodeは別の新規ノード
NewNode.next ← P.next
P.next ← NewNode
// 後続を別の変数へ保存してから更新する方法もある後続を別に保存していない場合、先にP.nextを新ノードへ変えると、元の後続をたどれなくなります。次にNewNode.next←P.nextを行うと、NewNode自身を指す自己ループになります。
ノードP の直後にある ノードQ を削除する場合
// Q=P.next、Q≠nilの前提で削除
P.next ← Q.next
// 他の参照もなくなったノードは、言語のメモリ管理方式に応じて解放する擬似言語による連結リスト走査と番兵（Sentinel）の役割
先頭ノードを指すポインタを「head」と呼びます。リストの全ノードを末尾まで巡回する基本コードは以下の形を取ります。
// 連結リストの全要素を末尾まで走査する基本形
current ← head
while (current ≠ nil)
出力(current.data)
current ← current.next
endwhileまた、先頭や末尾への挿入・削除において「headがnilかどうかの条件分岐」を省くため、実データを持たないダミーノードを先頭に常駐させる手法を「番兵（Sentinel / ダミーノード）」と呼びます。
実戦演習問題とステップ別解説
問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) で優れており、エは連続領域を必要とする配列の特徴です。正解は イ です。
先頭・末尾と双方向リストの更新
単方向リストの先頭へ挿入するなら、新ノード.next←head、head←新ノードです。先頭を削除するなら、head≠nilを確認してhead←head.nextにします。番兵があれば先頭も「番兵の直後」として扱えます。
// 双方向リスト：Pの直後へNを挿入
Q ← P.next
N.prev ← P
N.next ← Q
P.next ← N
if (Q ≠ nil)
Q.prev ← N
else
tail ← N
endif単方向リストで指定ノードを削除するには、通常その前ノードも必要です。探索から始めるならO(n)になることがあります。つなぎ替えのO(1)と、操作全体の時間を分けます。
出典と仕様を確認する
IPA：FEシラバス Ver.9.2
IPA：試験で使用する用語・プログラム言語 Ver.5.1
Open Data Structures：連結リスト
次におすすめの学習
編集・検証について
編集・検証：IT資格ラボ編集部
IPAが公開する試験要綱・シラバス・過去問題と、各技術の公式資料を優先して内容を確認しています。制度変更や誤りを確認した場合は、記事を見直して更新します。
編集方針・情報源・訂正方針を見る