単方向連結リスト（singly linked list）

単方向連結リスト（singly linked list）#

ここでは単方向連結リスト（singly linked list）を実装したプログラムを解説します．単方向連結リストは以下のようなデータ構造です．

連結リスト（れんけつリスト、（英語: Linked list）は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。

一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる（場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する）。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。

引用：連結リスト - Wikipedia

Pythonではポインターを直接扱うことはないので，これを実装するならばC言語のようなポインターを直接扱えるプログラミング言語の方が適切かもしれません．（しかし）ここでは簡単のためにPythonのクラスを使って実装していきます．
リストの構成要素をNodeクラス，リスト自体をSinglyLinkedListクラスで実装します．

# 型ヒントのためのimport
from typing import Any, Self

ノードの定義#

まずはノードを定義しておきます．

このノードは値self.dataと次のノードへのポインターself.nextを持っています．

class Node():
    def __init__(self, data:Any, next: Self|None=None)->None:
        self.data = data
        self.next = next
    
    def __str__(self):
        #return f"Node(data={self.data}, next={self.next})"
        return self.data.__str__()

__str__メソッド

__str__はprint関数にこのインスタンスを渡した時に表示される文字列を変更するための特殊なメソッドです．

__str__がない場合はクラスの名前とメモリ番地が表示されます．

node = Node(1)
print(node)
# <__main__.Node object at 0x111c89850>

これに対して__str__を上のように宣言すると…

node = Node("適当な値")
print(node)
# 適当な値

このように表示させることが可能です．

初期化（コンストラクタ）#

次に単方向連結リストを定義します．まずは先頭ノードを格納するインスタンス変数を用意します．

class SinglyLinkedList():
    def __init__(self) -> None:
        self.head = None 

    @property
    def tail(self):
        if self.head is None:
            return None

headとtailプロパティ

self.headはリストが空の場合はNoneを持ちます．また，self.head is Noneならば末尾も同様にNoneなので，末尾要素を返すtailプロパティも追加しておきます．ここでtailをインスタンス変数ではなくプロパティとして宣言したのは，この方がこの次のappendメソッドの実装時に都合が良いからです．

要素の追加（append）#

リストの末尾に新しいノードを追加するappendメソッドを実装します．

appendメソッド

【appendメソッド】

もしもself.head is None（先頭要素が空）ならば，先頭要素に直接新しいノードを登録します．
先頭が空でなければ末尾要素に新しいノードを登録します．

【tailプロパティの修正】
先ほど末尾要素を参照するプロパティtailを設定しましたが，これをappendで使うために，先頭が空でない場合の処理を追加します．

先頭要素から順々に，ノードのnext属性をチェックします．
next属性がNoneであるノードが末尾ノードです．

class SinglyLinkedList():
    ...
    
    @property
    def tail(self):
        if self.head is None:
            return None
        current:Node = self.head
        while current.next:
            current = current.next
        return current
    
    def append(self, data:Any) -> Self:
        new = Node(data)

        # initialize
        if self.head is None:
            self.head = new 
            return self
        
        last_node = self.tail
        last_node.next = new
        return self

要素の削除（remove）#

任意の値を持ったノードをリストから削除するremoveメソッドを実装します．

removeメソッド

ここでは評価対象ノードcurrentと，今の評価対象ノードの一つ前のノードpreviousを，リストの先頭から一つづつずらしながら，「currentが削除対象か」をチェックしていきます．

「currentが削除対象」ならば前ノードのポインターprevious.nextを評価対象の次のノードに指定します．
ただし，「先頭要素が削除対象」ならばpreviousは空なので，self.headを直接「評価対象の次のノード」で上書きします．

class SinglyLinkedList():
    ...
    
    def remove(self, data:Any) -> Self:
        # 先頭ノードを評価対象ノードに指定
        current = self.head
        previous = None
        # リストを先頭なら舐める
        while current:
            # もしも評価対象ノードが削除対象ならば
            if current.data  == data:
                if previous:
                    previous.next = current.next
                # 先頭が削除対象ならば
                else:
                    self.head = current.next
                del current
                break
            # 評価対象が削除対象でないならば
            previous = current
            current = current.next

        # リスト内に削除対象が存在しなかった場合
        else:
            raise ValueError("LinkedList.remove(data): data not in LinkedList")
        return self

SinglyLinkedListの全プログラム#

以上でSinglyLinkedListクラスの実装が完了しました．プログラム全体とこれの動作チェックを以下に示します．

class SinglyLinkedList():
    def __init__(self) -> None:
        self.head = None 

    @property
    def tail(self):
        if self.head is None:
            return None
        current:Node = self.head
        while current.next:
            current = current.next
        return current
    
    def append(self, data:Any) -> Self:
        new = Node(data)

        # initialize
        if self.head is None:
            self.head = new 
            return self
        
        last_node = self.tail
        last_node.next = new
        return self
    
    def remove(self, data:Any) -> Self:
        # 先頭ノードを評価対象ノードに指定
        current = self.head
        previous = None
        # リストを先頭なら舐める
        while current:
            # もしも評価対象ノードが削除対象ならば
            if current.data  == data:
                if previous:
                    previous.next = current.next
                # 先頭が削除対象ならば
                else:
                    self.head = current.next
                del current
                break
            # 評価対象が削除対象でないならば
            previous = current
            current = current.next

        # リスト内に削除対象が存在しなかった場合
        else:
            raise ValueError("LinkedList.remove(data): data not in LinkedList")
        return self
    
    def __str__(self):
        if self.head is None:
            return "..."
        display_text = ""
        current:Node = self.head
        display_text+=f"{current}"
        while current.next:
            current = current.next
            display_text+=f", {current}"
        return display_text

    

動作チェックです．値の追加や削除を試してみましょう．

# 動作チェック
linkedlist = SinglyLinkedList()
print(linkedlist)

for i in range(10):
    linkedlist.append(i)
print(linkedlist)

linkedlist.remove(3)
print(linkedlist)

linkedlist.remove(0)
print(linkedlist)

linkedlist.remove(9)
print(linkedlist)

linkedlist.append(9)
print(linkedlist)

...
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 1, 2, 4, 5, 6, 7, 8, 9
1, 2, 4, 5, 6, 7, 8, 9
1, 2, 4, 5, 6, 7, 8
1, 2, 4, 5, 6, 7, 8, 9

リストに存在しない要素を削除しようとすると，エラーが発生するはずです．

linkedlist = SinglyLinkedList()
print(linkedlist)
linkedlist.remove(1)

...

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[5], line 3
      1 linkedlist = SinglyLinkedList()
      2 print(linkedlist)
----> 3 linkedlist.remove(1)

Cell In[3], line 47, in SinglyLinkedList.remove(self, data)
     43     current = current.next
     45 # リスト内に削除対象が存在しなかった場合
     46 else:
---> 47     raise ValueError("LinkedList.remove(data): data not in LinkedList")
     48 return self

ValueError: LinkedList.remove(data): data not in LinkedList