Pythonで循環リンクリストから重複要素を削除する方法【コード例付き】

循環リンクリストから重複要素を削除したい場合は、まず「Node」クラスを作成する必要があります。このクラスには、ノードが保持するデータと、リンクリストにおける次のノードへの参照という2つの属性を持たせます。

循環リンクリストでは、先頭（head）と末尾（tail）が互いに隣接しています。両者が連結されることで円形構造が形成され、最後のノードに「NULL」は存在しません。

次に、初期化関数を持つ別のクラスを作成し、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_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

    def remove_duplicate_vals(self):
        curr = self.head
        if(self.head == None):
            print("The list is empty")
        else:
            while(True):
                temp = curr
                index_val = curr.next
                while(index_val != self.head):
                    if(curr.data == index_val.data):
                        temp.next = index_val.next
                    else:
                        temp = index_val
                    index_val = index_val.next
                curr = curr.next
                if(curr.next == self.head):
                    break

    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("Nodes are being added to the list")
    my_cl.add_data(21)
    my_cl.add_data(54)
    my_cl.add_data(78)
    my_cl.add_data(99)
    my_cl.add_data(21)
    print("The list is :")
    my_cl.print_it()
    my_cl.remove_duplicate_vals()
    print("The updated list is :")
    my_cl.print_it()

実行結果

Nodes are being added to the list
The list is :
21
54
78
99
21

The updated list is :
21
54
78
99

処理の解説

• まず「Node」クラスを作成します。
• 続いて、必要な属性を持つ別のクラス（list_creation）を作成します。
• リンクリスト内の重複要素を取り除くための「remove_duplicate_vals」メソッドを定義します。
• 循環リンクリストのノードを画面に表示する「print_it」メソッドも定義します。
• 「list_creation」クラスのインスタンスを生成し、データを追加するメソッドを呼び出します。
• 「__init__」メソッドでは、循環リンクリストの先頭ノードと末尾ノードをNoneで初期化します。
• その後、「remove_duplicate_vals」メソッドを呼び出します。
• このメソッドはリスト全体を走査しながら、値が重複している要素が存在するかどうかを確認します。
• 重複が見つかった場合、該当する要素はリンクから切り離される形で削除されます。
• 最後に、「print_it」メソッドを使用して更新後のリストの内容がコンソールに出力されます。