基本情報技術者試験の午後問題が変わりました．
以前よりもプログラムを読み取る力が求められるようになりましたね．
科目B問題を解けるようになるにはプログラムを元に自分でコードを書いてみるのが1番良いでしょう．
今回は問3「単方向リストに追加するプログラム」の解説とそのコードを紹介します．
Pythonで書いてみたので是非手元で実行してみてください．
科目Bサンプル問題 問3 単方向リストに追加するプログラム
問題文はこちらです．
データ構造に関する問題です．
難しそうな問題ですね．
問1, 2は関数に関する問題でした．
そのため処理内容を追えば解けたことでしょう．
この問題にはクラスとデータ構造の理解が必要です．
求められる知識の幅が広がりました．
初めに単方向リストの意味について抑えましょう．
単方向リストとは
単方向リスト（Singly Linked List）はデータ構造の1つです．
この特徴は要素が1方向に参照され，線形に並べられている点です．
リストの最初の要素をヘッド（Head）と言います．
次の要素へのリンクがない要素はリストの終端を意味します．
リスト内の各要素は2つの属性を持ちます．
- データ（val）：データそのもの
- 参照（next）：次の要素へのリンク情報
ヘッドは1つ目の要素を参照していて，1つ目の要素は2つ目の要素を参照している. ..（要素分だけ続く）というように隣り合う要素は関連していると分かります．
プログラムをPythonで書き直す
問3に掲載されているプログラムを元にPythonで書き直しました．
リストの中身を表示するメソッドは問題文にありませんが，リスト状況を確認できたほうが分かりやすいので追加しました．
細かい処理内容はコメントで補足しています．
# 単方向リストの1つの要素を表すクラス
class ListElement:
def __init__(self, qVal: str):
self.val = qVal # val=データ
self.next = None # next=次の要素への参照
# 単方向リスト全体を表すクラス
class SinglyLinkedList:
def __init__(self):
self.listHead = None # リストの先頭
# 引数で与えられた文字を単方向リストに追加する
# 新しい要素はリストの末尾に追加される
def append(self, qVal: str):
curr = ListElement(qVal) # 要素を1つ作成する
if (self.listHead == None): # a もしリストの先頭が何も参照していない場合
self.listHead = curr # さきほど作成した要素をリストの1つ目とする
else: # すでに先頭がある要素を参照していた場合，追加する要素の1つ前の参照を付け替える
prev = self.listHead # リストの先頭を取得する
while (prev.next != None): # 要素が別の要素を参照していたとき以下の処理を繰り返す
prev = prev.next # 次の要素を取得する
prev.next = curr # b 要素が何も参照していなければ新しい要素を追加する
# 単方向リストの中身を表示する
def display(self):
current = self.listHead
while current:
print(current.val, end=" -> ")
current = current.next
print("None")
# 単方向リストのインスタンスを作成する
my_list = SinglyLinkedList()
# 単方向リストに要素を追加する
my_list.append(1)
my_list.append(2)
my_list.append(3)
# リストの中身を表示する
my_list.display()
プログラム結果を見ると追加した順に並べられていることが分かります．
コード内容は問題なさそうですね．
この問題では a に未定義，bに curr が入りました．
よって答えは「ア」となります．
続いてこの選択肢が入る理由について紹介します．
a）if (listHead が未定義）になる理由
空欄aの前後の処理を抜き出しました．
# 単方向リスト全体を表すクラス
class SinglyLinkedList:
def __init__(self):
self.listHead = None # リストの先頭
# 引数で与えられた文字を単方向リストに追加する
# 新しい要素はリストの末尾に追加される
def append(self, qVal: str):
curr = ListElement(qVal) # 要素を1つ作成する
if (self.listHead == None): # a もしリストの先頭が何も参照していない場合
self.listHead = curr # さきほど作成した要素をリストの1つ目とする変数の意味を整理します．
- listHead：単方向リストのヘッド（先頭部分）
- curr：今回追加する要素
listHeadは単方向リストのヘッドを表しています．
このヘッドは参照先の要素情報を持ちます．
初期値を見ると listHead は None が入っていることが分かりますね．
これは参照先の要素がないことを意味します．
参照先の要素がない＝ listHead が未定義であれば要素を入れてあげれば良さそうですね．
そのため真の処理のときに self.listHead = curr という処理が実行されます．
b）prev.next = currになる理由
空欄bの前後の処理を抜き出しました．
if (self.listHead == None): # a もしリストの先頭が何も参照していない場合
self.listHead = curr # さきほど作成した要素をリストの1つ目とする
else: # すでに先頭がある要素を参照していた場合，追加する要素の1つ前の参照を付け替える
prev = self.listHead # リストの先頭を取得する
while (prev.next != None): # 要素が別の要素を参照していたとき以下の処理を繰り返す
prev = prev.next # 次の要素を取得する
prev.next = curr # b 要素が何も参照していなければ新しい要素を追加するヘッドが未定義であれば要素を追加すると分かりました．
else 以降はヘッドがすでに要素を参照している場合の処理です．
prev = self.listHead # リストの先頭を取得する
while (prev.next != None): # 要素が別の要素を参照していたとき以下の処理を繰り返す
prev = prev.next # 次の要素を取得する
prev.next = curr # b 要素が何も参照していなければ新しい要素を追加するprev には各要素が入ります．
各要素は次の要素の参照情報（next）を持っていましたね．
前から順に要素が参照情報を持っているか確認します．
もし次の要素の参照情報がなければ新しい要素を参照情報として追加してあげます．
まとめ
今回は科目Bサンプル問3「単方向リストに追加するプログラム」について紹介しました．
この問題は所見で解くのはちょっと厳しいですね．
クラスに加えてデータ構造も知っておく必要がありました．
どちらかの知識が身についていれば解くのも可能かもしれません．
掲載したコードを参考に自分で書いてコードを動かしてみましょう．
より理解が深まること間違いありません．
