連結リストとはデーター構造の一種で、イメージしやすくいうとノードという箱のようなものにデータを格納してを他の箱と連結している構造をとっています。
図解するとこのような感じになります。
ノードを実際にコードで書いてみる
class LinledList:
class Node:
def __init__(self, payload):
self.payload = payload
self.next = None
def __init__(self):
self.head = None
def addNode(self, newpayload):
newnode = LinkedList.Node(newpayload)
if self.head == None:
self.head = newnode
return
else: #最後のノードに連結するケース
runner = self.head
while runner.next != None:
runner = runner.next
runner.next = newnode
links = LinkedList()
links.addNode(26)
links.addNode(99)
links.addNode(127)
links.addNode(42)
links.addNode(367)
実際のコードはこんな感じです。
class LinkedListが連結リストの機能をもつ部分で、「links = LinkedList()」以下の部分が実際に連結リストにデータを入れている部分になります。
ここからは部分ごとの解説をして行きたいと思います。
箱の部分
Nodeというクラスを作りました。そのノードは図の箱の部分のコードになります。
Nodeクラスはpayroadとnextの２つのインスタンス変数を持っています。
payloadは図での箱の中の｜より前半の部分で、プログラムとしては連結リストの中のデータはpayloadによって代入され一つのノードの中に記憶されます。
ここのpayloadの値はaddNodeメソッドの下の 「newnode = LinkedList.Node(newpayload)」のnewpayloadにあたります。
nextは図の｜の後半の➡︎のスタートしている部分で、次のノード（箱）の情報がnextに代入されます。
ですが通常新しいノードは一番後ろのノードに接続されて新しいノードより後ろにノードは存在しないためnextはNoneが初めからセットアップされています。
LinkedListの初期化
class LinkedListにはheadというここから連結リストが始まるという目印のようなものを初期化の時点でセットアップされています
図のheadがそれにあたります。
一番最初にNodeで作られたノードがheadの次に来ます。（addNodeの一番最初のif文がその部分にあたります。）
addNodeメソッド
addNodeメソッドは２つに分岐されています。
まだノードが接続されてない状態
まだノードが連結リストに連結されていない状態では、一番最初に作られたノード（このコードではnewnode）がheadになります。
既に連結されたノードがあり、その後ろに連結する場合
連結リストはコードが順番にデータを保存して行くので、普通のリストと違いインデックスがありません。
よってこのような場合、挿入する一つ前のnode（＝一番最後のノード）までrunnerという（名前はなんでもいいんですけど）たすきのようなものをまわす必要があります。
そのたすきを回している部分がwhileループになります。
１、
最初runner(たすき)は連結リストの最初の目印であるheadをもつ一番最初のノードにいます。（ runner = self.head）
２、
そこからrunner(タスキ)は次のノードに別のノードが接続されいないノード（＝連結リストの最後）になるまで移動します。（runner = runner.next）
runner.nextはNodeクラスの.nextにあたります。よってrunner.nextはrunnerというノードの次のノードのことを意味します。
runnerは元々１個目のノードであるself.headでしたが、それが２個目のノードであるself.head.nextに移り、最後には最後のノードにrunnerは移ります。
３、
最後のノードの次（＝runner.next）に新しいノードを代入します。
追記
細かいところですが、実はself.nextに代入されているものは次のノードそのものではなく、次のノードのメモリーの場所です。id()という組み込み関数を使ってそれを確認することができます。
self.head's id = 4470967936
4470967936 26 (next=4470967992)
4470967992 99 (next=4470968048)
4470968048 127 (next=4470968104)
4470968104 42 (next=4470968160)
4470968160 367 (next=None)
具体的にどのようなコードを書いたのかは割愛しますが、next＝の値が次のデータの前に書かれている値と一致することが確認できると思います。
今回はノードを一番後ろに接続する場合のみ紹介しましたが、一番前に連結することや、途中に挿入する方法もあります。
またこのように→が一方向の連結リストは片方向リストといい、一番シンプルなものになります。もし他の種類がきになる方はwikipediaで確認してみてください。
もし技術的に間違った箇所があればご連絡していただけると助かります。
おすすめ記事
もし情報工学科やコンピューターサイエンス学部に進学予定の方へ。もしかしたら他学部でもいいかも...
