線形リスト

【平成22年・秋】

Q.

先頭ポインタと末尾ポインタをもち、多くのデータがポインタでつながった単方向の線形リストの処理のうち、先頭ポインタ、末尾ポインタまたは各データのポインタをたどる階数が最も多いのはどれか。ここで、単方向のリストは先頭ポインタからつながっているものとし、追加するデータはポインタをたどらなくても参照できるものとする。

ア・・・先頭にデータを追加する処理
イ・・・先頭のデータを削除する処理
ウ・・・末尾にデータを追加する処理
エ・・・末尾のデータを削除する処理

A.

 

上記の図を例に説明すると以下となります。

ア・・・

 1.先頭ポインタからアドレス１０を参照

 2.先頭ポインタを追加するデータのアドレスに更新
 3.追加するデータのアドレス部を"アドレス10"に更新

 １回

イ・・・

 1.先頭ポインタからアドレス10を参照

 2.アドレス１０からアドレス１１を参照

 3.先頭ポインタのアドレスを"11"に更新

2回

ウ・・・（アドレス１４のデータを追加するとして）
 1.末尾ポインタからアドレス１３を参照
 2.アドレス１３のアドレスを"14"に更新
 3.末尾ポインタのアドレスを"14"に更新

1回

エ・・・

 1.末尾ポインタからアドレス13を参照 (アドレス13を取得)

 2.先頭ポインタからアドレス10を参照

 3.アドレス10からアドレス11を参照

 4.アドレス11からアドレス12を参照

 5.アドレス12のアドレス部を削除

 6.末尾ポインタをアドレス12に変更

データの数＋１（上記の場合、5回)

補足）
細かく書くと上記のような説明になるが、要は、
単方向の線形リストで先頭ポインタ、末尾ポインタがある場合、 一番参照回数が増えるのは２番目の末尾データです。データが増えるほど、たどる回数は増えていきます。
それがわかっていれば、わざわざカウントしなくても解ける問題です。