
単方向リストの挿入で参照を書き換える順番
解き方
単方向リストは、データと次の要素への参照を持つ要素をつないだ構造です。途中に挿入するときは、後続の要素へ到達できる状態を保ちながら参照を書き換えます。
手順を追う例
A→B→CというリストのAの直後にXを挿入します。まずX.nextにA.nextを代入し、次にA.nextへXを代入します。最初の代入でX→Bができ、次の代入でA→X→B→Cになります。ここでnextは「次の要素への参照」であり、要素に格納するデータとは別のものです。
確認問題【オリジナル】
次の2行を逆順に実行するとどうなりますか。初期状態はA→B→Cで、Xはまだリストに接続されていません。
X.next ← A.next
A.next ← X
答えと解説
逆順だと、先にA.nextがXになります。続くX.next ← A.nextではX自身が代入され、A→X→X…という自己参照になります。元のBへの参照は、この2行からたどる限り失われます。元の後続をX.nextへ先に保存することが必要です。別の変数がBを参照しているかどうかは、この問題では指定していません。