Pythonで循環リンクリストの中央に新しいノードを挿入する方法

循環リンクリスト（Circular Linked List）の中央に新しいノードを挿入するには、まず「Node」クラスを作成する必要があります。このクラスには2つの属性が定義されます。1つ目はノードが保持するデータ、2つ目はリンクされた次のノードへの参照です。

循環リンクリストの特徴

循環リンクリストでは、先頭（head）と末尾（tail）が互いに隣接しており、リスト全体が環状につながっています。そのため、末尾のノードには「NULL」が存在せず、最後のノードのnextが再び先頭を指し示す構造になっています。

続いて、初期化関数を持つ別のクラスを作成します。このクラスでは、リストの先頭が「None」で初期化されます。さらに、リストの中間へノードを追加するメソッドや、ノードの値を出力するメソッドなど、複数の操作用メソッドを定義していきます。

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

サンプルコード

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

class list_creation:
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.next = self.head
        self.size = 0

    def add_data(self, my_data):
        new_node = Node(my_data)
        if self.head.data is None:
            self.head = new_node
            self.tail = new_node
            new_node.next = self.head
        else:
            self.tail.next = new_node
            self.tail = new_node
            self.tail.next = self.head
        self.size = self.size + 1

    def add_in_between(self, my_data):
        new_node = Node(my_data)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
            new_node.next = self.head
        else:
            count = (self.size // 2) if (self.size % 2 == 0) else ((self.size + 1) // 2)
            temp = self.head
            for i in range(0, count):
                curr = temp
                temp = temp.next
            curr.next = new_node
            new_node.next = temp
        self.size = self.size + 1

    def print_it(self):
        curr = self.head
        if self.head is None:
            print("リストは空です")
            return
        else:
            print(curr.data)
            while curr.next != self.head:
                curr = curr.next
                print(curr.data)
            print()

class circular_linked_list:
    my_cl = list_creation()
    print("ノードをリストに追加していきます")
    my_cl.add_data(21)
    my_cl.add_data(54)
    my_cl.add_data(78)
    my_cl.add_data(99)
    print("現在のリスト:")
    my_cl.print_it()
    my_cl.add_in_between(33)
    print("更新後のリスト:")
    my_cl.print_it()
    my_cl.add_in_between(56)
    print("更新後のリスト:")
    my_cl.print_it()
    my_cl.add_in_between(0)
    print("更新後のリスト:")
    my_cl.print_it()

実行結果

ノードをリストに追加していきます
現在のリスト:
21
54
78
99

更新後のリスト:
21
54
33
78
99

更新後のリスト:
21
54
33
56
78
99

更新後のリスト:
21
54
33
0
56
78
99

コードの解説

• まず、ノードのデータと次ノードへの参照という2つの属性を持つ「Node」クラスを作成します。
• 必要な属性を備えた別のクラス「list_creation」を定義します。
• 循環リンクリストの中央（最も中間に近い位置）にデータを挿入するための「add_in_between」メソッドを定義します。
• 循環リンクリストの各ノードを表示するための「print_it」メソッドを定義します。
• 「__init__」メソッドでは、循環リンクリストの先頭と末尾のノードをNoneで初期化します。
• 「list_creation」クラスのオブジェクトを生成し、そのメソッドを呼び出してデータを順番に追加します。
• 「add_in_between」メソッドが呼び出されると、リストを走査して中央のインデックスを算出し、その位置に新しい要素を挿入します。
• 挿入後のリストの状態は「print_it」メソッドによってコンソールに出力されます。

計算量について

中央への挿入では、挿入位置までリストを走査する必要があるため、時間計算量はO(n)となります。一方、実際のノード挿入処理（ポインタの付け替え）自体はO(1)で完了します。この点を理解しておくと、データ構造の選択時に適切な判断ができるようになります。