Pythonで循環リンクリストの先頭に新しいノードを挿入するプログラムの書き方

循環リンクリストとは

循環リンクリスト（Circular Linked List）は、末尾のノードが再び先頭のノードを指すことで円状につながったデータ構造です。通常のリンクリストと異なり、最後のノードに「NULL」値は存在せず、先頭（head）と末尾（tail）が互いに隣接しています。

循環リンクリストの先頭に新しいノードを挿入するには、まず「Node」クラスを作成する必要があります。このクラスには、ノードに格納されるデータ（data）と、リンクリスト内の次のノードへの参照（next）という2つの属性を持たせます。

続いて、初期化関数を持つ別のクラスを作成し、ノードのheadを「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  

    def add_at_beginning(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:  
            temp = self.head
            new_node.next = temp
            self.head = new_node
            self.tail.next = self.head
            
    def print_it(self):  
        curr = self.head
        if self.head is None:  
            print("The list is empty")
            return
        else:  
            print(curr.data)
            while(curr.next != self.head):  
                curr = curr.next
                print(curr.data)
            print("\n")
            
class circular_linked_list:  
    my_cl = list_creation()
    print("Values are being added to the list")
    my_cl.add_at_beginning(21)
    my_cl.print_it()
    my_cl.add_at_beginning(53)
    my_cl.print_it()
    my_cl.add_at_beginning(76)
    my_cl.print_it()

出力結果

Values are being added to the list
21

53
21

76
53
21

コードの解説

• まず、「Node」クラスを作成します。
• 続いて、必要な属性を持つ別のクラス（list_creation）を作成します。
• 「add_at_beginning」というメソッドを定義します。このメソッドは、循環リンクリストの先頭、すなわち「head」ノードの前にデータを追加するために使用されます。
• 「print_it」というメソッドを定義します。このメソッドは、循環リンクリストの各ノードの値を表示します。
• 「list_creation」クラスのオブジェクトを生成し、そのメソッドを呼び出してデータを追加します。
• 「__init__」（init）メソッドでは、循環リンクリストの最初と最後のノードをNoneに初期化しています。
• 「add_at_beginning」メソッドを呼び出すと、リンクリストのheadを取得し、その前に新しい要素を追加します。そして、そのアドレスをtailポインタおよびnextポインタに参照させます。
• 最後に、「print_it」メソッドを使用して、結果をコンソールに出力します。

まとめ

このように、Pythonでは「Node」クラスとリスト操作用のクラスを組み合わせることで、循環リンクリストへのノード挿入をシンプルに実装できます。先頭への挿入時は、新ノードのnextを元のheadに向けること、そしてtailのnextを新しいheadに更新することがポイントです。この仕組みを理解すれば、末尾への挿入やノードの削除など、他の操作にも応用できます。