【Python】双方向連結リストの末尾からノードを削除する方法を解説

双方向連結リスト（Doubly Linked List）の末尾からノードを削除するには、まず「Node」クラスを作成する必要があります。このクラスには、ノードが保持するデータ、次のノードへの参照、前のノードへの参照という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.previous = None
            self.tail.next = None
        else:
            self.tail.next = new_node
            new_node.previous = 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_end(self):
        if(self.head == None):
            return
        else:
            if(self.head != self.tail):
                self.tail = self.tail.previous
                self.tail.next = 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_end()
    print("末尾から要素を削除した後のリスト：")
    my_instance.print_it()

実行結果

要素を双方向連結リストに追加しています
双方向連結リスト内のノード：
10
24
54
77
92
末尾から要素を削除した後のリスト：
双方向連結リスト内のノード：
10
24
54
77
末尾から要素を削除した後のリスト：
双方向連結リスト内のノード：
10
24
54
末尾から要素を削除した後のリスト：
双方向連結リスト内のノード：
10
24
末尾から要素を削除した後のリスト：
双方向連結リスト内のノード：
10
末尾から要素を削除した後のリスト：
リストは空です

コードの解説

• まず「Node」クラスを作成します。各ノードはデータ本体と、前後のノードへの参照を持ちます。
• 次に、必要な属性を持つ「double_list」クラスを作成します。
• 「add_data」メソッドは、双方向連結リストの末尾に新しいデータを追加するためのメソッドです。リストが空の場合は新ノードが先頭かつ末尾になり、そうでなければ既存の末尾ノードの後に接続されます。
• 「print_it」メソッドは、リスト内のすべてのノードの値を順番に表示します。リストが空の場合はその旨を出力します。
• 「delete_from_end」メソッドは、リストの末尾（tail）ノードを削除し、その直前のノードを新しい末尾として設定します。ノードが1つしかない場合は、head と tail の両方を None にしてリストを空にします。
• 「double_list」クラスのインスタンスを作成し、各メソッドを呼び出して末尾からのノード削除を実行します。
• 「__init__」メソッドでは、head と tail を初期状態として None に設定しています。
• while ループによってリストが空になるまで繰り返し末尾のノードを削除していきます。
• 各段階のリストの状態は「print_it」メソッドを使ってコンソールに出力され、削除の進行状況を確認できます。

このように、tail ポインタを利用することで、双方向連結リストの末尾への追加・削除はどちらも O(1) の計算量で効率的に行えます。単方向連結リストと異なり、前のノードへの参照があるため、末尾ノードを削除してもその前のノードを簡単に特定できるのが大きな利点です。