pythonでLinked List実装(参照フィールド)のおさらい

最近アルゴリズムの勉強をしようとGoogle Tech Dev Guideを進めているんですが、Linked Listを実装しようというコーナーがあって全然できなくて苦労しました。

概要図でやろうとすることは理解できるのですが、全然実装方法が思いつかず、Youtubeや色んなサイトの記事をみながら本日やっとコードのテストに合格できました。(Singly Linked Listでこのざま)
正確には実装はインデックスの取得や挿入、削除といった機能の方が苦労したのですが、そもそもLinked Listはどうデータを入れてるのかと言うのが気になったのでちょっとメモしておきます。

環境

ubuntuのターミナルで実行します。

masashi@PC-ubuntu:~$ python3 --version
Python 3.8.10

Singly Linked Listの基本的な形

Linked Listは各ノードが参照フィールドを持っていて、次のノードの情報が格納されているというのが特徴です。
いろんな動画や記事を見てもLinked Listの実装はほとんど以下の形です。

class Node:
    def __init__(self, data):
      self.data = data
      self.next = None # 参照フィールド

class MyLinkedList:
    def __init__(self):
        self.head = None

これをインスタンス化して各ノードをつなげます。
インスタンスに別のクラスを当てるというアイデアが出てこなかったです。

ll = MyLinkedList()

ll.head = Node('a')
second = Node('b')
third = Node('c')

ll.head.next = second
second.next = third

nextに次ノードの値を入れて、それを繋げていくことでリストになります。

リストとしてを出力するには以下。
Nodeオブジェクトはイテレーションできないのでwhileを使います。

>>> nodes = ll.head
>>> while nodes:
...   print(nodes.data, end=' ')
...   nodes = nodes.next # 次のノードへ
... 
a b c >>>

ちゃんと順番に出力されました。

どう繋がっているのか

各Nodeクラスのnextに次のオブジェクトが入るのはわかりましたが実際はどうなっているのでしょうか。
中を見てみます。

>> dir(ll.head)
['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', 'data', 'next']

headオブジェクトにdataとnextの属性が格納されてます。
Nodeクラスのインスタンスにはそれぞれdataとnextが作成されるということですね。
nextが繋がらなくなったらNoneでLink終了と。

nextが繋がっているのが確認できます。

>>> ll
<__main__.MyLinkedList object at 0x7fc5cf3c1a00>
>>> ll.head # a
<__main__.Node object at 0x7fc5cf360250>
>>> ll.head.next # b
<__main__.Node object at 0x7fc5cf360730>
>>> ll.head.next.next # c
<__main__.Node object at 0x7fc5cf3607f0>
>>> ll.head.next.next.next # 値なし

各ノードオブジェクトが別のメモリアドレスに割り当てられてます。
こうみたらnextがどんどん足されているんですね。
次はdataを呼び出してみます。

>>> ll.head.data
'a'
>>> ll.head.next.data
'b'
>>> ll.head.next.next.data
'c'
>>> ll.head.next.next.next.data
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'NoneType' object has no attribute 'data'

格納したデータどおりの順に出力されました。
cの次は何も入ってないので値がとれませんね。

本当に繋がっているのかメモリアドレスも出してみます。
現在ノードのアドレス、データ、次ノードのアドレスを出力してみます。

>>> while nodes:
...   print(nodes, nodes.data, nodes.next)
...   nodes = nodes.next
... 
<__main__.Node object at 0x7f81b16d76a0> a <__main__.Node object at 0x7f81b16d7730>
<__main__.Node object at 0x7f81b16d7730> b <__main__.Node object at 0x7f81b16d77f0>
<__main__.Node object at 0x7f81b16d77f0> c None