基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

線形リストの問題に関する質問です。

[基本：平成27年秋期  午前  問5] 
ポインタを用いた線形リストの特徴のうち，適切なものはどれか。
１．先頭の要素を根としたn分木で，先頭以外の要素は全て先頭の要素の子である。
２．配列を用いた場合と比較して，2分探索を効率的に行うことが可能である。
３．ポインタから次の要素を求めるためにハッシュ関数を用いる。
４．ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。
答：４

ところが、別の問題では、

[応用：令和元年秋期 午前問6] 
先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで，単方向のリストは先頭ポインタからつながっているものとし，追加するデータはポインタをたどらなくても参照できるものとする。
1. 先頭にデータを追加する処理
2. 先頭のデータを削除する処理
3. 末尾にデータを追加する処理
4. 末尾のデータを削除する処理
答：4

この２つの問題は、矛盾してるように思えるのです。
上の問題では、「新たな要素を追加する計算量は，要素の個数や位置によらず  ”一定である”」が正解であるのに、下の問題では、「ポインタをたどる回数が最も多いもの」を訊いているのです。上の問題では、"一定である"  が正解なのに、下の問題では、一定でないことを前提にして”回数が最も多いもの”を聞いているのです。これは一体どういうことなのでしょうか。

おわかりになる方、教えていただけると大変助かります。宜しくお願いします。

結論から言うと矛盾していないです。

上の問題は、

“ポインタによって指定されている要素”の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である

とあるので、ポインタによって指定されていない要素の後ろに追加する計算量は一定であるかは書かれていません。また、削除に関しては全く述べられていません。

ですので、下の問題で「ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。」という性質について述べられているのは

1. 先頭にデータを追加する処理

だけですね。先頭ポインタが与えられ、先頭ポインタが追加するデータを指すようにするだけですので。2,3,4については上記の性質の前提条件を満たしていません。

早速ご回答くださりありがとうございます。大変助かりました。
「ポインタによって指定されている」＝「たどった後」という発想をすることができずに延々と悩み、この２問によってリストの仕組みが全くわからないようになり半日が過ぎ、ここで質問させていただきました。
こんなことがわからないのは自分だけで誰の役にも立たないかも知れませんが、もしかすると同じことを疑問に思う方もいらっしゃるかもしれないので追記させていただきますと、この２問を理解するのに「ポインタによって指定されている要素の削除自体は一定の計算量で行える」ということも併せて知る必要がありましたのでこのコメントに残しておきます。

みなさんの厳密な問題読み込みにびっくりしています・・・

線形リストに要素を追加する操作は以下になると思います。
１．先頭要素から対象の箇所まで探し続ける。
２．対象箇所で何かを行う。
３．対象箇所の変更による前要素の処理。
※２と３は場合によっては無いかもしれませんが

前者は、１の処理を考えてないで（ポインタによって指定されている要素の後ろに、と既に１は処理済みの上で）２と３について言っていて
後者は、１・２・３すべてに対しての参照回数で最大になるのは？と聞いているところの違いだと思ってます。

ITパスポートの試験でもそうでしたが、最初は用語の概略を知っているレベルの問題も、後発の問題ではより多角的な視点で問われることがあると思ってますのでその違いかなと思います。

> 「ポインタによって指定されている要素の削除自体は一定の計算量で行える」
>（スレ主さんによる回答No.3）

いいえ、間違っています。
応用情報ドットコムの解説でも、そうは書かれていないです。

ポインタによって指定されている要素の後ろに新たな要素を追加する、のであれば、即座に可能です。
ポインタが指す要素Xの後ろに新要素を追加する処理は「要素X内の次ポインタ」の書き換えで実現できるので。

（ →[大崎]→[品川]→[田町]→ という線形リストにおいて、ポインタが[品川]を指している場合、
[品川]～[田町]間に [高輪GW] を追加する処理は、[品川]内の次ポインタを[高輪GW]行きに書き換えるだけで即座に（一定回数で）実現できます）

それに対して。

ポインタによって指定されている要素の削除は、即座にはできません。
ポインタが指す要素Xを削除する処理は「【要素Xを指す要素】内の次ポインタ」の書き換えなので。

（ →[大崎]→[品川]→[田町]→ という線形リストにおいて、ポインタが[品川]を指している場合、
[品川]を削除するためには[品川]を変更するのでなく、[大崎]内の次ポインタを[田町]行きに書き換えねばなりません。しかし [大崎]→[品川] は単方向の線形リストなので、[品川]を指しているポインタは[大崎]にさかのぼることができません。結局、線形リストの先頭から順に[大崎]まで進むことでようやく[品川]の削除が可能になります。つまり即座に（一定回数で）は実現できません）

jjon-comさん、間違いを指摘して下さりありがとうございます。
[大崎]内の次ポインタを[田町]行きに書き換える時の司令は、以下のような感じという理解で合ってますか？
1.品川を削除せよ
2.「単方向なんで次ポイントしか持ってないよ。後ろが誰だかわからないんだ」by品川
3.了解。1から辿っておまえ(品川)の後ろを特定する
4.品川の後ろが特定できたぞ。大崎だ。品川、次ポイント(田町)を大崎に渡せ。

電タックさん、分かりやすくまとめて下さりありがとうございます。少しずつイメージできるようになってきました。

No.6の文の「後ろ」をすべて「前」に置き換えるのなら正しいです。

ただこれは、「前」「後ろ」をどうイメージしているかの違いかもしれません。

→[大崎]→[品川]→[田町]→ において現在位置が[品川]であるとき、

私は、
[大崎]を [品川]の「前」と呼ぶ方がしっくりきますし、
[田町]を [品川]の「後ろ」と呼ぶ方がしっくりきます。

それに対してSato39さんは、
[田町]を [品川]の「前」と呼ぶイメージ、
[大崎]を [品川]の「後ろ」と呼ぶイメージなのかもしれません。