Pythonで循環リンクリストの中央からノードを削除する方法

循環リンクリスト（Circular Linked List）の中央からノードを削除するには、まず「Node」クラスを作成する必要があります。このクラスには、ノードが保持するデータと、リンクリスト内の次のノードへの参照という2つの属性を持たせます。

循環リンクリストでは、先頭（head）と末尾（tail）が互いに隣接しています。つまり、最後のノードに「NULL」が存在せず、全体が円形につながった構造になっているのが特徴です。

次に、初期化関数を持つ別のクラスを作成します。このクラスでは、headを「None」で初期化し、サイズを表す変数sizeも0で初期化します。

さらに、ユーザー定義関数として、リンクリストへノードを追加する機能、コンソールに内容を出力する機能、そして中央のインデックスからノードを削除する機能を実装します。

以下に実際のコード例を示します。

サンプルコード

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 = int(self.size)+1

    def delete_from_mid(self):
        if(self.head == None):
            return
        else:
            count = (self.size//2) if (self.size % 2 == 0) else ((self.size+1)//2)
            if( self.head != self.tail ):
                temp = self.head
                curr = None
                for i in range(0, count-1):
                    curr = temp
                    temp = temp.next
                if(curr != None):
                    curr.next = temp.next
                    temp = None
                else:
                    self.head = self.tail = temp.next
                    self.tail.next = self.head
                    temp = None
            else:
                self.head = self.tail = None
        self.size = self.size - 1

    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()
    my_cl.add_data(11)
    my_cl.add_data(52)
    my_cl.add_data(36)
    my_cl.add_data(74)
    print("The original list is :")
    my_cl.print_it()
    while(my_cl.head != None):
        my_cl.delete_from_mid()
        print("The list after updation is :")
        my_cl.print_it()

実行結果

The original list is :
11
52
36
74

The list after updation is :
11
36
74

The list after updation is :
11
74

The list after updation is :
74

The list after updation is :
The list is empty

コードの解説

• まず「Node」クラスを作成し、データと次ノードへの参照を保持できるようにします。
• 必要な属性を持つ「list_creation」クラスを作成します。
• 「add_data」メソッドを定義し、循環リンクリストへデータを追加できるようにします。
• 「delete_from_mid」メソッドを定義し、参照を切り替えることで中央の要素を順番に削除します。
• 「print_it」メソッドを定義し、リンクリストの内容をコンソールに表示します。
• 「list_creation」クラスのオブジェクトを生成し、メソッドを呼び出してデータを追加します。
• 「delete_from_mid」メソッドを呼び出して削除処理を実行します。
• リンクリスト内のノードを走査して中央のインデックスを特定し、そこから要素を削除していきます。
• 削除後の状態は「print_it」メソッドを使ってコンソールに出力されます。