https://www.fe-siken.com/kakomon/sample20220425/b3.html

先日も単方向リスト(削除)の説明をしていただいたのですが
単方向リスト(追加)の問題にて質問がありますので
お付き合いいただけると幸いです。
まだまだ理解しきれていない部分があるようです・・
質問は★の部分です。

まず、この問題をざっくりと読み解くと
〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
①  ListElementクラスで「prev」と「curr」というインスタンスを作成している
    ※そのため「prev」と「curr」はメンバ変数にvalとnextを持つ
②  コンストラクタにて変数valを初期化したものをcurrに格納している
    ※currで持てるのは参照アドレスのみ(問題文より)
③  listHeadは未定義の値で初期化されているが2パターン存在し
    Ⅰ.本当に何も格納されておらずリストがからの状態      ・・※1
    Ⅱ.要素が何個か格納されていてその中に未定義が存在する    ※2
④  Ⅰの場合はif文の条件(listHeadが未定義＝a)を満たすことになるため
    追加したい要素の参照アドレスをもつcurrをlistHeadに代入している。
    ※そうすることによってlistHeadには最初に参照するアドレスが格納される。
⑤  Ⅱの場合(elseの処理)はlistHeadに最初の参照アドレスが格納されているので
    それをprevに代入して一番末尾の未定義にぶつかるまで繰り返し処理を実行する。
    未定義にぶつかったら追加したい要素の参照アドレスをもっているcurrを格納する。
〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓

という風になると思います。

ちなみに先の質問で使用した例を借りてイメージするのなら以下のようになる認識です。

※1(リストが空の状態)
｜アドレス｜要素の値｜次の参照アドレス
｜120     ｜東京    ｜未定義
プログラムの前半部分でcurrに「120」が格納されるので
それをlistHeadに格納してあげることでlistHeadが「120」
となり最初の要素が参照できるようになる。

※2(リストにすでに要素が存在している状態)
｜アドレス｜要素の値｜次の参照アドレス
｜100     ｜京都    ｜130
｜110     ｜広島    ｜未定義
｜120     ｜東京    ｜150
｜130     ｜新大阪  ｜110
｜150     ｜名古屋  ｜100
ここに
｜180     ｜博多    ｜未定義
という要素を追加したいため
繰り返し処理で博多の未定義にぶつかるまで回して
※この段階でprevには広島の未定義が格納されている状態
広島の未定義を180(currの値)に書き換えてあげる。


ここからが質問なのですが
それぞれの選択肢を見たときに
bでは「curr」「curr.next」「listHead」の３つが用意されています。
上記で整理したように
「curr」は正解なのはおいておいて
「curr.next」がダメな理由は
★そもそもcurr.nextは存在しない？←ここ自信ないです(だから迷ったのですが)
  ※2の博多の例で言うと「180」の次の要素を指定しているということになりますよね？
  そんな要素は存在しないため指定ができないと理解しましたが
  問題ないでしょうか？
「listHead」がダメな理由は
★繰り返し処理で未定義にぶつかるまで回すときに
  更新されているのはprevの値でlistHeadは最初の参照値から
  変動していないため最初の参照値を格納してしまうことになるため不適

あとは
★この問題は追加の問題だったので末尾までたどったが
  挿入という処理もプログラムを変えれば実現可能という認識でよいでしょうか？
  ※リスト構造の問題としては「追加」「削除」「挿入」
    の3つに慣れておけば問題ないですかね？

★最初にこのプログラムを読んだときに
  listHead ← 未定義の値
  で初期化しているのならif内の処理が実行されるのは分かるんだけど
  elseの処理にいかなくない？
  prev ← listHeadをしたところで未定義がprevに格納されるだけじゃん
  って思って解いてて解説読んで未定義の意味合いが2パターンあることに
  気づいたんですがこういう書き方に騙されない(言い方変かもですが)
  ためにはどうすればいいでしょうか？
  ※実は※1と※2は解いている時に思いついた例ではなく解説をみて
    書き起こしました・・

長くなりましたがよろしくお願いします。

こんにちは。

> ★そもそもcurr.nextは存在しない？←ここ自信ないです(だから迷ったのですが)

まず、currが何なのかから整理してみましょう。
>curr←ListElement(qval)
とあります。
ListElement(qval)の正体はクラスListElementのコンストラクタでvalをqvalで初期化したインスタンスが作成されるようです。では、nextはどうなるのかというとクラスListElementのメンバ変数の説明に書いてある通りにnextは未定義で初期化されるようです。
整理すると、
ListElement(qval)でメモリのどこかにクラスListElementのvalがqval、nextが未定義のインスタンスが作成され、そのアドレスがcurrに入っています。
となると、curr.nextは初期化された後なにも代入されていないので、curr.nextは未定義になります。

> ★繰り返し処理で未定義にぶつかるまで回すときに
  更新されているのはprevの値でlistHeadは最初の参照値から
>変動していないため最初の参照値を格納してしまうことになるため不適

多分合ってると思います。

>★この問題は追加の問題だったので末尾までたどったが
  >挿入という処理もプログラムを変えれば実現可能という認識でよいでしょうか？
>  ※リスト構造の問題としては「追加」「削除」「挿入」
    >の3つに慣れておけば問題ないですかね？

「追加」と「挿入」の区別がつけづらいので、
以降では
「追加」を末尾への挿入
「挿入」を任意の場所への挿入
と表現しますね。

結論から言うと、任意の場所への挿入も可能です。しかし、リスト構造が得意としているのは、末尾への挿入です。特別な理由がない限り、末尾への挿入を利用することが多いと思います。

そのため、勉強の優先度としては、
「末尾への挿入」  > 「削除」 > 「任意の場所への挿入」となるのかなと思います。また、削除も末尾から消すパターンや先頭から消すパターンもあると思います。

> prev ← listHeadをしたところで未定義がprevに格納されるだけじゃん

else句はlistHeadが未定義でない時に入るので、prevには未定義は入りません。

未定義の意味あいが２つあるの意味が私には分からなかったです…申し訳ない。

listHeadは大域変数です。このプログラムが主記憶にロードされ、初めて実行された時点で
はただ一度実行されて未定義の値に初期化されます。

単方向リストの末尾に次々と要素を追加するために、主記憶にロードされた append()関数を何度も呼び出す際には、
の代入は実行されません。

> ③  listHeadは未定義の値で初期化されているが2パターン存在し
>     Ⅰ.本当に何も格納されておらずリストがからの状態      ・・※1
>     Ⅱ.要素が何個か格納されていてその中に未定義が存在する    ※2

という文が、分かっているようにも分かっていないようにも読めるので補足しておきます。

③Ⅰ.は、このプログラムが主記憶にロードされ初めて実行された状態です。
listHead
＋ーー＋
｜NULL｜
＋ーー＋

その後、append("東京")が実行されると、③Ⅱ.の状態になります。
listHead
＋ーー＋
｜ 120｜
＋ーー＋
     val     next 
    ＋ーーー＋ーー＋
 120｜東京  ｜NULL｜
    ＋ーーー＋ーー＋

コメントできそうな所だけコメントします。

>★そもそもcurr.nextは存在しない？←ここ自信ないです(だから迷ったのですが)
>  ※2の博多の例で言うと「180」の次の要素を指定しているということになりますよね？
>  そんな要素は存在しないため指定ができないと理解しましたが
>  問題ないでしょうか？
指定できないという事はありません。

これはオブジェクトを扱う上で覚えておいてほしい考えで
１．対象オブジェクト自体が未定義の場合、そのオブジェクトのメンバへのアクセスはエラーとなる。
ListElement list1  ←  未定義
ListElement list2  ←  list1.next // この操作でエラーとなる

２．対象オブジェクト自体が未定義でなければ、そのオブジェクトのメンバが未定義でも何ら問題ない。
ListElement list1  ←  ListElement(qVal)
ListElement list2  ←  list1.next // 「list1」が未定義ではないのでこの操作は何ら問題なく、未定義のlist2となる
ListElement list3  ←  list1.next.next // 「list1.next」が未定義のため、１．の考えでエラーとなる

>★繰り返し処理で未定義にぶつかるまで回すときに
>  更新されているのはprevの値でlistHeadは最初の参照値から
>  変動していないため最初の参照値を格納してしまうことになるため不適
今回のプログラムであれば不適（正解ではない）で正しいですが、リストの要素が回っている（末尾の次が先頭を指す様なもの）循環リストというものが一応存在しているという事を周辺知識で覚えておいても良いと思います（使うことはほぼ無いと思いますが）

ちょっと補足します。

リスト構造には以下の前提があります。
・リストの末尾要素のnextは未定義である。

この前提をもとにすると、問題のプログラムは以下のように解釈できると思います。

まず、リストが空（listHeadが未定義）のときとそうでないときで場合わけしています。
======================================
追加したいクラスListElementのインスタンスを作成し、変数currにそのアドレスを格納する。

・リストが空のとき
listHeadがcurrが参照しているアドレスを参照すればよい。
・そうでないとき
先頭の要素の参照をprevに代入し、メンバ変数nextを頼りに次の要素へと順々に移って行きます。whileループはprev.nextが未定義になったら終了です。すなわち、先ほどの前提をもとにすると、リストの末尾の参照が、変数prevに入ったら終了です。whileループが終了した時点で、prevにはリストの末尾の要素の参照が入っているので、末尾にcurrを追加したい場合は、prev.nextにcurrが参照しているアドレスを代入すればOK。
======================================

No.1の次の★の箇所は、
誤×  博多の未定義にぶつかるまで回して
正○  広島の未定義にぶつかるまで回して
です。

の実行によって新たな要素が生み出されます。
この時点では単方向リストに連結されていない独立した要素ですから、
単方向リストをlistHeadから順にたどっていっても"博多"にはぶつかりません。
単方向リストは要素"博多"が存在することすら知らず、
を実行して初めて、要素"博多"の存在を知ることになります。

皆さまご解説ありがとうございます。

今皆様からのコメントに目を通させていただきました。
取り急ぎお礼申し上げます。

今から個別の返信をさせていただきますので
お待ちください。

まーぼ  様

引き続きご回答いただきありがとうございます。

> 整理すると、
> ListElement(qval)でメモリのどこかにクラスListElementのvalがqval、nextが未定義のインスタンスが作成され、そのアドレスがcurrに入っています。
> となると、curr.nextは初期化された後なにも代入されていないので、curr.nextは未定義になります。
    ⇒ここの理解がやはり少し足りていなかったようです。
      存在しないわけではなくて”未定義”として存在しているわけですね。
      問題としては未定義をprev.nextに入れてしまうことになるので不適ということですね。


> 結論から言うと、任意の場所への挿入も可能です。しかし、リスト構造が得意としているのは、末尾への挿入です。
> 特別な理由がない限り、末尾への挿入を利用することが多いと思います。
> そのため、勉強の優先度としては、
> 「末尾への挿入」  > 「削除」 > 「任意の場所への挿入」となるのかなと思います。
> また、削除も末尾から消すパターンや先頭から消すパターンもあると思います。
    ⇒なるほど、リスト構造が得意としているのが末尾の挿入ということであれば
      わざわざ任意の場所への挿入を実装するのであれば
      他の方法を使った方がよいという話ですね。
      不可能ではないとのことで意地悪問題として
      出題される可能性がある以上は勉強しておこうと思います。
      削除も末尾から消すパターンや先頭から消すパターンがあるのは確かにその通りですね。
      基本的な考え方は理解できたような気がするので
      後は問題をこなして感覚を磨いていきたいと思います。


> else句はlistHeadが未定義でない時に入るので、prevには未定義は入りません。
> 未定義の意味あいが２つあるの意味が私には分からなかったです…申し訳ない。
    ⇒ここは私の勘違いです。すみません。
      リストが完全に空である時の状態を引きずったまま文章を打ち込んでいました。
      おっしゃる通りlistHeadが未定義でない時しかelseの処理には分岐しませんもんね・・
      意味合いが2つといったのは※1と※2の２つのパターンを考えないといけない。
      ということを言いたかっただけです。
      この２つのパターンがあるということを初見では見抜けなかったので・・


また
> リストの末尾要素のnextは未定義である。
    ⇒問題解いているとそんな感じなんだろうなあと思っていましたが
      リスト構造の前提としてそうなっているのですね。
      これも忘れずに覚えておきます。


====で囲まれた文章については
自分の理解と認識合います。

丁寧に解説していただきありがとうございました。

クラスやメンバ変数、コンストラクタなどの概念を
少しは自分の頭に落とし込めたような気がします。

まだまだ似たような例題をこなしていかないと
誤答してしまう気がしますが
これだけ時間をかけていただいたので本番で似たような問題が
出た際には取りこぼさないようにしたいと思います。

ありがとうございました。

jjon-com  様

引き続きご回答いただきありがとうございます。


> listHeadは大域変数です。このプログラムが主記憶にロードされ、初めて実行された時点で
> ただ一度実行されて未定義の値に初期化されます
    ⇒listHeadに未定義の値は処理中一度しか格納されないということですね。

Ⅰの状態の補足ありがとうございます。
ここは私の理解と認識が合います。
問題を解いている時にここまで理解できればよかったのですが・・


> 誤×  博多の未定義にぶつかるまで回して
> 正○  広島の未定義にぶつかるまで回して
> です。
    ⇒ここすみません・・・
      完全に私の打ち間違いです・・
      結果的に博多が格納されるだけで
      ループの段階では存在しませんもんね。
      ご説明の通り認識合いますので大丈夫です。
      訂正ありがとうございました。


引き続き精進していきます。
丁寧な解説ありがとうございました。

電タック  様

解説いただきありがとうございます。

> これはオブジェクトを扱う上で覚えておいてほしい考えで
> １．対象オブジェクト自体が未定義の場合、そのオブジェクトのメンバへのアクセスはエラーとなる。
> ListElement list1  ←  未定義
> ListElement list2  ←  list1.next // この操作でエラーとなる
> ２．対象オブジェクト自体が未定義でなければ、そのオブジェクトのメンバが未定義でも何ら問題ない。
> ListElement list1  ←  ListElement(qVal)
> ListElement list2  ←  list1.next // 「list1」が未定義ではないのでこの操作は何ら問題なく、未定義のlist2となる
> ListElement list3  ←  list1.next.next // 「list1.next」が未定義のため、１．の考えでエラーとなる
    ⇒詳しい解説ありがとうございます。
      オブジェクト自体が未定義だったら.nextを指定した段階でエラーが返ってくるんですね。
      たしかにこの考え方を理解しているかしていないかで
      他の問題でも絞れる回答が変わってくるかもですね。


> リストの要素が回っている（末尾の次が先頭を指す様なもの）
> 循環リストというものが一応存在しているという事を周辺知識で覚えておいても良いと思います
> （使うことはほぼ無いと思いますが）
    ⇒こちらも補足の説明ありがとうございます。
      参考書を読んでいる時にチラッと目を通した記憶があるようなないような・・
      末尾が先頭を指しているということはその名の通りグルグル循環するってことですよね。
      使うことはほぼ無いとのことで優先度は落として時間があれば調べてみようと思います。


お時間割いて解説していただきありがとうございました。
引き続き精進します。

皆さま改めて優しく解説していただいてありがとうございました。

また詰まったときにはお力添えをいただくこともあるかと思いますが
その際はよろしくお願いします。