← デモ一覧へ戻る

単方向リストの挿入・削除

head を入口にして、挿入 と 削除 で矢印がどうつなぎ替わるかを、図で確認できます。

基本説明必要なときだけ開く
なぜ配列ではなくリスト？

配列は番号で素早く読めますが、要素数を先に決める必要があります。単方向リストは、あとから増減しやすいのが強みです。

  • 配列は番号で直接アクセスできる
  • リストは先頭から順番にたどる
  • リストは挿入・削除で形を変えやすい
head は入口

リスト全体は head から始まります。各ノードは data と next を持ち、最後は NULL で終わります。

  • head は最初のノードを指す
  • next は次のノードを指す
  • NULL は「もう次がない」印
挿入の鉄則

途中に新しいノードを差し込むときは、先に newNode の行き先を決めてから、前のノードの next を変えます。

  • 先に newNode.next をつなぐ
  • あとで prev.next を newNode に変える
削除の鉄則

削除では、消すノードそのものよりも、前のノード が次にどこを指すかが重要です。飛び越すイメージで考えます。

  • まず target = prev.next を確認する
  • 次に prev.next = target.next で飛び越す
このページの見方
  1. 参照中のポインタ で、いま注目しているノードを確認する
  2. ポインタ付け替え で、どの参照が何から何へ変わったかを見る
  3. リスト本体 が最後まで HEAD → ... → NULL でつながっているか確かめる

可視化

head prev target newNode このステップで更新した next
リスト本体
作業中のノード
参照中のポインタ