平成21年度秋期 システムアーキテクト 午前Ⅰ 問3

末尾操作で辿るノード数を見積もる

連結リストの計算量は、操作で書き換えるべきノードへ手元のポインタから何回たどれば届くかで決まります。各構成について、末尾側の操作で必要になるノードとそこへの到達手段を一つずつ確かめる姿勢で検討しましょう。

この問題で問われていること

着目点は一つ、「操作で参照・更新が必要なノードに、構成が用意しているポインタから定数回の移動で到達できるか」です。操作の種類ごとに、必要なノードを書き出してから到達経路を確認してください。

視点

計算量は、リストの長さnに比例する手順が含まれるかどうかで判断します。どのノードへ到達できるかは、外部から直接指しているノードと、各ノードが持つリンクの向きの組合せで決まります。ノードと矢印を簡単な図に描き、実際にたどって確かめると整理しやすくなります。

確認ポイント

• 操作の前後で、どのノードのリンクを書き換える必要があるかを書き出したか
• そのノードへ、構成が持つポインタから直接届くか、先頭などから順にたどる必要があるかを確認したか
• たどる回数がリストの長さに依存するかどうかで計算量を判断したか

正解

イ

解説

実装方法1では追加も削除も先頭から辿るので、比はほぼ1になる。実装方法2ではrearにより追加は一定時間だが、削除は直前のセルを探す必要があるので、比はほぼnに比例する。正答はイ。

実装方法1

frontしかないので、追加では末尾のxₙまで辿ってからxₙ₊₁をつなぐ。削除ではxₙの直前のxₙ₋₁まで辿り、そのポインタを空にする。どちらもnに比例する回数だけセルを辿るので、f(n)≒a·n、g(n)≒b·n（a、bは定数）と表せる。比はg(n)/f(n)≒b/aとなりnが消えるので、ほぼ一定（選択肢の表現では「ほぼ1」）になる。

実装方法2

追加は、rearが指すxₙの後ろにxₙ₊₁をつなぎ、rearを更新するだけで済むので、f(n)はnによらない一定時間になる。一方、削除ではxₙ₋₁のポインタを空にし、rearをxₙ₋₁に移す必要がある。xₙから前のセルに戻るポインタはないので、frontから辿るしかなく、g(n)はnに比例する。よってg(n)/f(n)はほぼnに比例する。

比較

rearは末尾のセルを直接指すので、末尾の後ろに何かをつなぐ処理は速くなる。しかし末尾の削除で必要なのはその1つ前のセルなので、rearがあっても速くならない。この非対称性により、実装方法1の比はほぼ1、実装方法2の比はnに比例するという違いが生じる。

選択肢ア

これは不正解だよ。実装方法1の比がほぼ1になる点は合っている。しかし実装方法2では、rearを使えば追加は一定時間で済む一方、削除にはxₙの直前のxₙ₋₁が必要になる。単方向リストでは先頭から辿るしかないので、g(n)だけがnに比例し、比はほぼ1にならないよ。

選択肢イ（正解）

これは正解だよ。実装方法1では、追加は末尾のxₙまで、削除は直前のxₙ₋₁まで先頭から辿る必要がある。f(n)もg(n)もnに比例するので、比はほぼ1になる。実装方法2では、追加はrearが指すxₙにつなぐだけなので一定時間だが、削除はxₙ₋₁を先頭から探す必要がある。そのため比はほぼnに比例するよ。

選択肢ウ

これは不正解だよ。実装方法1ではf(n)もg(n)も先頭からの走査でnに比例するので、比はnに比例せず、ほぼ1になる。実装方法2では、rearがあっても削除には直前のxₙ₋₁を探す必要があり、g(n)はnに比例したまま、f(n)だけが一定時間になる。そのため比はnに比例する。前半・後半とも逆だよ。

選択肢エ

これは不正解だよ。実装方法2の比がほぼnに比例する点は合っている。しかし実装方法1では、追加（末尾のxₙまで走査）も削除（直前のxₙ₋₁まで走査）もnに比例する時間がかかる。比をとるとnの影響が打ち消されてほぼ1になるので、実装方法1の比はnに比例しないよ。

学習のポイント

単方向連結リストで末尾を削除するには直前のセルが必要で、末尾ポインタがあっても探す手間は省けない点を押さえる。