Pythonで双方向リンクリストから重複要素を削除する方法

双方向リンクリスト（二重連結リスト）から重複する要素を削除するには、まず「Node」クラスを作成する必要があります。このクラスには3つの属性が含まれます。ノードに格納されるデータ、リンクリスト内の次のノードへの参照、そして前のノードへの参照です。

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

サンプルコード

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

class double_list:
    def __init__(self):
        self.head = None
        self.tail = None

    def add_data(self, my_data):
        new_node = Node(my_data)
        if(self.head == None):
            self.head = self.tail = new_node
            self.head.previous = None
            self.tail.next = None
        else:
            self.tail.next = new_node
            new_node.previous = 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

    def remove_duplicates(self):
        if(self.head == None):
            return
        else:
            curr = self.head
            while(curr != None):
                index_val = curr.next
                while(index_val != None):
                    if(curr.data == index_val.data):
                        temp = index_val
                        index_val.previous.next = index_val.next
                        if(index_val.next != None):
                            index_val.next.previous = index_val.previous
                        temp = None
                    index_val = index_val.next
                curr = curr.next

my_instance = double_list()
print("要素を双方向リンクリストに追加しています")
my_instance.add_data(10)
my_instance.add_data(24)
my_instance.add_data(54)
my_instance.add_data(77)
my_instance.add_data(24)
my_instance.print_it()
print("重複を削除した後のリストの要素：")
my_instance.remove_duplicates()
my_instance.print_it()

実行結果

要素を双方向リンクリストに追加しています
双方向リンクリストのノード：
10
24
54
77
24
重複を削除した後のリストの要素：
双方向リンクリストのノード：
10
24
54
77

コードの解説

• まず「Node」クラスを作成します。このクラスは各ノードを表し、データと前後のノードへの参照を保持します。
• 次に、リンクリスト本体を管理するための「double_list」クラスを作成します。
• 「remove_duplicates」メソッドでは、リストの先頭から順に各ノードを基準として、それ以降のノードとデータを比較していきます。
• 同じ値を持つノードが見つかった場合、そのノードをリンク構造から切り離すことで削除します。
• 「print_it」メソッドは、リスト内のすべてのノードの値を先頭から順番に表示します。
• 「double_list」クラスのインスタンスを作成し、「add_data」メソッドを使って要素（10、24、54、77、24）を追加します。
• その後「remove_duplicates」メソッドを呼び出して重複を除去します。
• 最後に「print_it」メソッドで結果をコンソールに出力すると、重複していた「24」が1つだけ残っていることが確認できます。

このアルゴリズムの計算量はO(n²)です。各ノードについて残りのノードを走査して比較するため、要素数が多い場合はパフォーマンスに注意が必要です。より効率化したい場合は、セット（set）を使って既出の値を記録しながら一度の走査で重複を除去する方法（O(n)）も検討できます。