【Python】双方向リンクリストの先頭からノードを削除する方法

双方向リンクリスト(二重連結リスト)の先頭からノードを削除するには、まず「Node」クラスを作成する必要があります。このクラスには、ノードが保持するデータ(data)、リンクリスト内の次のノードへの参照(next)、前のノードへの参照(prev)という3つの属性を定義します。

以下に、具体的な実装例を示します。

サンプルコード

class Node:
    def __init__(self, my_data):
        self.prev = None
        self.data = my_data
        self.next = None

class double_list:
    def __init__(self):
        self.head = None
        self.tail = None

    def add_data(self, my_data):
        new_node = Node(my_data)
        if(self.head == None):
            self.head = self.tail = new_node
            self.head.prev = None
            self.tail.next = None
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
            self.tail.next = None

    def print_it(self):
        curr = self.head
        if (self.head == None):
            print("リストは空です")
            return
        print("双方向リンクリストのノード : ")
        while curr != None:
            print(curr.data)
            curr = curr.next

    def delete_from_beginning(self):
        if(self.head == None):
            return
        else:
            if(self.head != self.tail):
                self.head = self.head.next
                self.head.prev = None
            else:
                self.head = self.tail = None

my_instance = double_list()
print("要素を双方向リンクリストに追加しています")
my_instance.add_data(10)
my_instance.add_data(24)
my_instance.add_data(54)
my_instance.add_data(77)
my_instance.add_data(92)
my_instance.print_it()
while(my_instance.head != None):
    my_instance.delete_from_beginning()
    print("先頭の要素を削除した後のリスト : ")
    my_instance.print_it()

実行結果

要素を双方向リンクリストに追加しています
双方向リンクリストのノード : 
10
24
54
77
92
先頭の要素を削除した後のリスト : 
双方向リンクリストのノード : 
24
54
77
92
先頭の要素を削除した後のリスト : 
双方向リンクリストのノード : 
54
77
92
先頭の要素を削除した後のリスト : 
双方向リンクリストのノード : 
77
92
先頭の要素を削除した後のリスト : 
双方向リンクリストのノード : 
92
先頭の要素を削除した後のリスト : 
リストは空です

コードの解説

• 「Node」クラスを作成し、コンストラクタ内で prev・data・next の3つの属性を初期化します。
• リンクリスト本体を管理するための「double_list」クラスを別途作成します。
• 「add_data」メソッドを定義し、リストが空の場合は新ノードを head かつ tail に設定し、空でない場合は末尾(tail)に接続します。
• 「print_it」メソッドを定義し、head から順にノードをたどりながらすべてのデータを表示します。リストが空の場合はその旨を出力します。
• 「delete_from_beginning」メソッドを定義し、先頭(head)ノードを削除して、次のノードを新しい head として設定します。
• 「__init__」メソッドでは、head と tail を None に初期化します。
• 「double_list」クラスのインスタンスを生成し、add_data メソッドで5つの要素(10, 24, 54, 77, 92)を追加します。
• while ループにより、リストが空になるまで先頭ノードを繰り返し削除し、その都度「print_it」メソッドで現在の状態をコンソールに出力します。

削除処理のポイント

先頭ノードの削除は、head の参照を次のノードに付け替え、新しい head の prev を None にするだけで完了します。要素の移動が不要なため、計算量は O(1) と非常に効率的です。また、ノードが1つしかない場合(head == tail)は、head と tail の両方を None に設定することで、リスト全体を空の状態にできます。