基本情報技術者試験（B試験）Classを使った単方向リストをPythonで解く

基本情報のB試験（午後試験）が受からず難儀しています。

大滝みや子さん著書の「アルゴリズム×疑似言語　トレーニングブック」を読みつつClassで引っ掛かり、さらに単方向リストに引っ掛かり途方に暮れました。

色々試行錯誤した結果、chatGPTに問い詰める形となり、結果おおよそ理解できました。

そのやり取りをこちらに記載します。

コード：単方向リストに「ロンドン、ローマ、パリ、ニューヨーク」を入れる。

ノード（Node）とは、データ構造における基本的な要素の1つで、データとそのデータが参照する次の要素（または要素群）へのポインタやリンクを持っています。

# Listという名前のクラスを定義します。
class List:
		#コンストラクタ！！！！
    # クラスの初期化関数を定義します。
		#この関数はListの新しいインスタンスを作成する際に自動的に実行されます。
    def __init__(self, val):
        self.value = val       
				# インスタンスのvalue属性にvalの値（引数で渡される値）を設定します。
        self.next = None       
				# インスタンスのnext属性にNoneを設定します。この属性は次のノードを指し示すためのものです。

# 単方向リストの内容を表示する関数を定義します。
def print_list(lst):
    current = lst             
		# lstからスタートしてリストを辿るための変数currentを初期化します。
    while current:            
		# currentがNoneになるまで（リストの最後まで）ループを続けます。
        print(current.value)  
				# 現在のノードのvalue属性（都市名）を表示します。
        current = current.next 
				# currentを次のノードに更新します。

# リストの作成を開始します。

# "ロンドン"という値でListの新しいインスタンスを作成し、newに代入します。
new = List("ロンドン")
# firstにnew（現時点では"ロンドン"のノード）を代入します。
#firstは常にリストの最初の要素を指し示します。（最後までロンドンが入る）
first = new

# followにfirstの値（"ロンドン"のノード）を代入します。
#followはリストの現在の末尾を指し示すための変数として使われます。
follow = first
# "ローマ"という値で新しいノードを作成し、newに代入します。
new = List("ローマ")
# followが指すノード（"ロンドン"）のnext属性にnew（"ローマ"のノード）を設定します。
follow.next = new
# followを新しい末尾（"ローマ"のノード）に更新します。
follow = follow.next

# 上記の2ステップを"パリ"と"ニューヨーク"にも繰り返します。
new = List("パリ")
follow.next = new
follow = follow.next

new = List("ニューヨーク")
follow.next = new
follow = follow.next

# 単方向リストの内容を表示します。
print_list(first)

メンバ変数は、コンストラクタ内で定義しています。

Javaだとまた違うのでしょうが、深追いはせず理解優先で。

List:first,new,followという記述があるのですが、インスタンス化するのはnewだけでした。わかりづらくてしょうがない。

問題となるのは、new,first,followの中身の動きです。

GPTさんに解説をしてもらいました。

ノードの動き

new = List("ロンドン")     # newのvalue属性に"ロンドン"が代入される
first = new               # first変数にnew（"ロンドン"ノードへの参照）が代入される
follow = first            # follow変数にfirst（"ロンドン"ノードへの参照）が代入される
new = List("ローマ")      # newのvalue属性に"ローマ"が代入される
follow.next = new         # followのnext属性にnew（"ローマ"ノードへの参照）が代入される
new = List("パリ")        # newのvalue属性に"パリ"が代入される
follow.next = new         # followのnext属性にnew（"パリ"ノードへの参照）が代入される
new = List("ニューヨーク") # newのvalue属性に"ニューヨーク"が代入される
follow.next = new         # followのnext属性にnew（"ニューヨーク"ノードへの参照）が代入される

newの動き

変数 new は、新しく作成される都市（地域名）の「箱」を一時的に持つためのものです。各都市を追加するたびに、new はその都市の新しい「箱」を指すように更新されます。

以下が具体的なステップです：

new = List("ロンドン")

ここでは、List("ロンドン") で「ロンドン」という名前の新しい箱（オブジェクト）を作成しています。そして、new という変数にこの新しい箱を代入しています。この操作後、new は「ロンドン」の箱を指します。

new = List("ローマ")

次に、List("ローマ") で「ローマ」という名前の新しい箱を作成しています。そして、再び new という変数にこの新しい箱を代入しています。この操作を行った後、new は「ロンドン」の箱ではなく、「ローマ」の箱を指すようになります。

これ以降も、新しい都市の名前の箱を作るたびに、その新しい箱を new に代入することで、new は常に最新の箱を指すようになります。

この new の特性（常に新しい箱を指すこと）を利用して、リストに都市を追加する際に、follow.next = new のようにして、現在のリストの末尾（**follow**が指す部分）の次に新しい都市の箱を接続しています。

要するに、new は常に最新の都市の箱を指す変数として機能しており、新しい都市を追加するたびに、それを指すように更新されます。

以上の動作の結果として、プログラムの最後で**new**の中身は「ニューヨーク」の箱だけになります。

firstの動き

first の中身は最初に設定された「ロンドン」の箱を指すままであり、プログラムの実行を通じてその指し示す内容は変わりません。

first は、単方向リストの最初の要素、すなわち「ロンドン」を常に指し示しています。これにより、リストの先頭にアクセスする際の参照点となります。

後続の都市（「ローマ」、「パリ」、「ニューヨーク」）は first の next プロパティ、およびその次の next プロパティをたどることでアクセスできますが、first 自体が指す都市は「ロンドン」のままです。

単方向リストを作成する上で、first のような変数は非常に重要です。その理由は以下の通りです：

1. アクセスポイント: first はリストの先頭を指し示すためのアクセスポイントとして機能します。リストに含まれる要素にアクセスしたり、リスト全体を通過したりする際には、最初の要素から開始するのが一般的です。そのため、リストの先頭要素への参照を保持しておく変数が必要となります。
2. リストの状態の保持: first なしでリストを作成した場合、リストの先頭要素への参照を失うと、そのリストの他の要素へのアクセスも不可能になります。これは、単方向リストの性質上、各要素が次の要素のみを指示しているためです。
3. 操作の簡素化: first を使用することで、リストへの要素の追加や削除などの操作を簡素化できます。特に、リストの先頭に新しい要素を追加する際など、first を使うことで操作が簡単になります。

要するに、単方向リストを効率的に操作・管理するためには、リストの先頭を示す変数（この場合 first）が非常に有用です。

followの動き

1. 最初に new = List("ロンドン") が実行されたとき、new は「ロンドン」の箱を指します。その後、follow = first が実行されることで、follow も「ロンドン」の箱を指すようになります。
2. 次に new = List("ローマ") が実行されると、new は「ロンドン」から「ローマ」の箱を指すように変わります。この時点で、follow.next = new により、「ロンドン」の箱の次に「ローマ」の箱が続くようにリンクが設定されます。その後、follow = follow.next が実行されることで、follow は「ローマ」の箱を指すようになります。
3. new = List("パリ") が実行されると、new は「ローマ」から「パリ」の箱を指すようになります。follow.next = new により、「ローマ」の箱の次に「パリ」の箱が続くようにリンクが設定されます。その後、follow = follow.next が実行されることで、follow は「パリ」の箱を指すようになります。
4. 最後に new = List("ニューヨーク") が実行されると、new は「パリ」から「ニューヨーク」の箱を指すようになります。follow.next = new により、「パリ」の箱の次に「ニューヨーク」の箱が続くようにリンクが設定されます。その後、follow = follow.next が実行されることで、follow は「ニューヨーク」の箱を指すようになります。

結果として、new は「ニューヨーク」の箱を、follow も「ニューヨーク」の箱を指すようになります。

この説明を通じて、new は常に新しく作成された箱を指し、follow はリストの現在の末尾の箱を指すという動きを理解できると思います。

follow.nextの動き

まず、基本的な概念から確認します。follow は単方向リスト内の特定の要素（ノード）を指す変数であり、.next はそのノードが次に指しているノードへの参照を示します。したがって、follow.next に何かを代入するということは、follow が指しているノードが次に指すノードを設定または更新するということです。

以下に、各ステップでの follow.next の動きを説明します：

1. 最初に follow = first が実行されると、follow はリストの先頭要素「ロンドン」を指します。この時点では follow.next は None です。
2. new = List("ローマ") が実行されると、new は「ローマ」のノードを指します。follow.next = new が実行されると、follow が指す「ロンドン」のノードの次のノードとして「ローマ」が設定されます。これにより、リストは「ロンドン」→「ローマ」となります。
3. 次に new = List("パリ") が実行されると、new は「パリ」のノードを指します。follow は「ローマ」を指していますので、follow.next = new により、「ローマ」の次に「パリ」が来るようにリンクが設定されます。リストは「ロンドン」→「ローマ」→「パリ」となります。
4. 最後に new = List("ニューヨーク") が実行され、new は「ニューヨーク」のノードを指します。follow は「パリ」を指しているので、follow.next = new により、「パリ」の次に「ニューヨーク」が来るようにリンクが設定されます。リストは最終的に「ロンドン」→「ローマ」→「パリ」→「ニューヨーク」となります。

この流れを通じて、follow.next に代入することでリストの連鎖を形成し、新しい要素をリストの末尾に追加していることがわかります。

結論：

1. new=List()でインスタンス化し、都市名の箱を作る。
2. 一つ目の箱にはロンドンが入る。
3. follow.nextには必ず次の箱へのノードが入る。ロンドンでの中身はNone
4. new=List(”ローマ”)によって、２つ目の箱ローマがインスタンス化される。
5. follow.next=new の処理によって、ロンドンからローマへつながるノードができる。
6. 繰り返し

最終的には箱は４個になるようです。

最終的には4つの独立した箱が存在しています。

それぞれの箱は次のように構造化されています:

1. "ロンドン"を持つ箱（この箱の**next**は"ローマ"の箱を指す）
2. "ローマ"を持つ箱（この箱の**next**は"パリ"の箱を指す）
3. "パリ"を持つ箱（この箱の**next**は"ニューヨーク"の箱を指す）
4. "ニューヨーク"を持つ箱（この箱の**nextはNone**）

したがって、このリストには合計4つの箱（ノード）があります。

といことでした。

Classを突っつけば突っつくほど、C言語のポインタが脳裏をよぎります。

ノードとはポインタのようなもののようです。

奥が深すぎる・・・・