単方向リストの解釈

　多数のデータが単方向リスト構造で格納されている。このリスト構造には、先頭ポインタとは別に、末尾のデータを指し示す末尾ポインタがある。次の操作のうち、ポインタを参照する回数が最も多いものはどれか。

ア　リストの先頭にデータを挿入する。
イ　リストの先頭のデータを削除する。
ウ　リストの末尾にデータを挿入する。
エ　リストの末尾のデータを削除する。　　　　　（平成24年度春期　問７）

各選択肢の参照ポインタ数はいくつになるのでしょうか。
解説書によって必要なポインタ参照数が異なっていて、理解できずにいます。

とある解説書では、
ア　２回のポインタの参照が必要
イ　１回のポインタの参照が必要
ウ　２回のポインタの参照が必要

と記述してあり、またある解説書では

ア　０回のポインタの参照が必要
イ　２回のポインタの参照が必要
ウ　１回のポインタの参照が必要
エ　３回のポインタの参照が必要

と記述されていました。

先頭から末尾の一つ手前のデータまで順にたどって参照する必要のあるエが一番ポインタを参照する回数が多そうだな、と想像はできるのですが、実際の参照回数までは理解の外です。。

ご教授お願いします。

No.1 回答者： bin-chan 回答日時： 2013/03/18 20:18

> 実際の参照回数までは理解の外です。

。
要素数を定義しないと難しいかも。

この回答へのお礼

＞ある解説書では、
ア　２回のポインタの参照が必要
イ　１回のポインタの参照が必要
ウ　２回のポインタの参照が必要

この解説では要素数の定義はされていませんでした。
なので、要素数を定義しなくてもこの参照回数になるのではないかと考えています。

お礼日時：2013/03/18 20:51

No.2 回答者： hue2011 回答日時： 2013/03/18 23:06

２つの解説書とも、説明が違います。

答えがエであることはおわかりですね。

順に解説します。簡単です。

単方向リストですから、ずらりとデータが並んでいます。
アの場合は、先頭にあるポインタを２番目にして新しく確保したポインタを先頭にするだけですから2回です。
イは、先頭のポインタの参照を殺して２番目のポインタにすればいいので、１回です。先頭を見る必要はありません。
ウは、最後のポインタを更新することになりますから、１回です。
エは、最後のポインタを最後から２番目のポインタにしなければいけません。
イの場合は最初＋１が２番目のポインタになりますけど、エは最後ー１のポインタを確保しなければならないのです。

だったら、エ、は最初からずっと最後になるまで全部を調べてはじめて、最後ー１がわかります。
仮にリストが２個しかなくても２回は必要です。n個あったらn回参照です。

No.3 回答者： jjon-com 回答日時： 2013/03/19 00:57

ア）を実現するためには次の２つの処理を実行すればよい。

・挿入要素の次ポインタ部←先頭ポインタの中身
・先頭ポインタの中身←挿入要素のアドレス

--------
イ）を実現するためには次の処理を実行すればよい。
・先頭ポインタの中身←先頭ポインタが指す要素の次ポインタ部の中身

【補足】
回答No.2では次のように解説されていますけれど，
> イは、先頭のポインタの参照を殺して２番目のポインタに
> すればいいので、１回です。先頭を見る必要はありません。
先頭ポインタを起点にリストを一歩進まないと２番目の要素のアドレスは得られません。

私なら，上記の イ）の処理は，実質的に次の２つの処理だと見なします。
・変数Ｘ←先頭ポインタの中身
・先頭ポインタの中身←変数Ｘが指す要素の次ポインタ部の中身

--------
ウ）を実現するためには次の処理を実行すればよい。
・末尾ポインタが指す要素の次ポインタ部の中身←挿入要素のアドレス
・末尾ポインタの中身←挿入要素のアドレス

前述と同様，私はこれを実質的に次の３つの処理だと見なします。
・変数Ｘ←先頭ポインタの中身
・変数Ｘが指す要素の次ポインタ部の中身←挿入要素のアドレス
・末尾ポインタの中身←挿入要素のアドレス

--------
そして最後の エ）ですが。

単方向リストにおける要素の削除とは，
削除対象要素を書き換えることではなく，
「削除対象要素の１つ前の要素の次ポインタ部」を書き換えることです。

末尾要素に達するだけなら，末尾ポインタから一発で到着することができますが，
そこから「末尾要素の１つ前の要素」に移動しようとしても，単方向リストなので末尾要素から１つ前に遡ることは不可能です。
したがって，回答No.2で解説されているとおり，
先頭ポインタから単方向リストを一歩一歩 順にたどることによってでしか「末尾要素の１つ前の要素」に達することはできません。

そこに達した後は次の処理を実行します。
・末尾要素の１つ前の要素の次ポインタ部の中身←リスト終端を表す特別な値
・末尾ポインタの中身←末尾要素の１つ前の要素のアドレス

No.4 回答者： root139 回答日時： 2013/04/13 14:36

「ポインタの参照」をどう捉えるかで、数が変わってきますね。

例えば、新規の要素を確保してそのポインタをどこかに設定する場合、既存のポインタは見ていないので参照回数に加えないのか、新規確保したポインタも数に入れて+1とするかは解釈が分かれるかと。
まあ、答えがエで有ることは変わらないですが。（要素が多数で、末尾の要素を指しているもの以外の全てのポインタを参照する必要が有る為）

個人的には「ポインタの参照」を「既存のポインタの値を取得すること」と捉えるのが妥当だと思いますので、下記のページの解説が分かりやすくて良いと思います。
http://itpro.nikkeibp.co.jp/article/COLUMN/20120 …

だたし、このページも間違っている箇所は有ります。
エの場合、末尾のデータを指しているポインタは（書き換える必要は有っても）参照する必要は無いので図の最後の青矢印は不要です。（解説の文章の方は間違っていませんが）