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_at_end(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

my_instance = double_list()
print("双方向リンクリストの末尾に要素を追加します")
my_instance.add_data_at_end(10)
my_instance.print_it()
my_instance.add_data_at_end(24)
my_instance.print_it()
my_instance.add_data_at_end(54)
my_instance.print_it()
my_instance.add_data_at_end(77)
my_instance.print_it()
my_instance.add_data_at_end(92)
my_instance.print_it()

実行結果

双方向リンクリストの末尾に要素を追加します
双方向リンクリストのノードは次のとおりです：
10
双方向リンクリストのノードは次のとおりです：
10
24
双方向リンクリストのノードは次のとおりです：
10
24
54
双方向リンクリストのノードは次のとおりです：
10
24
54
77
双方向リンクリストのノードは次のとおりです：
10
24
54
77
92

解説

• まず、データ・前ノードへの参照（prev）・次ノードへの参照（next）の3つの属性を持つ「Node」クラスを作成します。
• 続いて、head（先頭）とtail（末尾）への参照を必要な属性として持つ「double_list」クラスを作成します。
• 「add_data_at_end」というメソッドを定義し、これを使って双方向リンクリストの末尾にデータを追加できるようにします。リストが空の場合は新ノードがheadとtailの両方になり、そうでなければtailの後ろに新ノードを連結してtailを更新します。
• もう一つのメソッド「print_it」を定義し、リンクリスト内のすべてのノードを順番に表示できるようにします。
• 「double_list」クラスのオブジェクト（インスタンス）を生成し、そのメソッドを呼び出して双方向リンクリストの末尾へデータを追加していきます。
• 「__init__」メソッドでは、headとtailの各ノードをNoneで初期化しています。
• 要素を1つ追加するたびにリスト全体が走査され、末尾に新しい要素が連結されます。
• 追加のたびに「print_it」メソッドを使い、現在のリストの状態をコンソールに出力して確認できます。