Python - Xóa phần tử trùng lặp khỏi Doubly Linked List

Xóa các node trùng lặp trong Doubly Linked List: duyệt qua từng node, kiểm tra các node sau nó có giá trị trùng không, nếu có thì xóa (bypass).

Triển khai

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
    
    def remove_duplicates(self):
        """Xóa node trùng lặp, giữ lần xuất hiện đầu tiên."""
        if self.head is None:
            return
        
        current = self.head
        while current:
            # Kiểm tra các node sau current
            runner = current.next
            while runner:
                next_runner = runner.next  # Lưu trước khi có thể xóa
                if runner.data == current.data:
                    # Xóa runner
                    self._remove_node(runner)
                runner = next_runner
            current = current.next
    
    def _remove_node(self, node):
        """Xóa node khỏi list (helper)."""
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" <-> ".join(elements) if elements else "Empty")

# Demo
dll = DoublyLinkedList()
for val in [10, 24, 54, 77, 24, 10, 54]:
    dll.append(val)

print("Danh sách gốc:")
dll.display()

print("\nĐang xóa trùng lặp...")
dll.remove_duplicates()

print("Danh sách sau khi xóa trùng:")
dll.display()

Kết quả

Danh sách gốc:
10 <-> 24 <-> 54 <-> 77 <-> 24 <-> 10 <-> 54

Đang xóa trùng lặp...
Danh sách sau khi xóa trùng:
10 <-> 24 <-> 54 <-> 77

Giải thích

• Duyệt current từ head đến tail.
• Với mỗi current, dùng runner duyệt các node phía sau.
• Nếu runner.data == current.data -> xóa runner.
• _remove_node() cập nhật con trỏ prev/next của node lân cận, xử lý trường hợp head/tail.
• Lưu next_runner trước khi xóa để tiếp tục duyệt.

Độ phức tạp

• Thời gian: O(n²) - lồng 2 vòng lặp.
• Không gian: O(1) - không dùng cấu trúc phụ.

Tối ưu O(n) với Hash Set

def remove_duplicates_fast(self):
    """O(n) time, O(n) space - dùng set theo dõi đã thấy."""
    if self.head is None:
        return
    
    seen = set()
    current = self.head
    
    while current:
        if current.data in seen:
            # Trùng -> xóa
            next_node = current.next
            self._remove_node(current)
            current = next_node
        else:
            seen.add(current.data)
            current = current.next

# Test
dll2 = DoublyLinkedList()
for v in [10, 24, 54, 77, 24, 10, 54]:
    dll2.append(v)
dll2.remove_duplicates_fast()
dll2.display()  # 10 <-> 24 <-> 54 <-> 77

Xóa trùng lặp cho nested data (so sánh phức tạp)

def remove_duplicates_custom(self, key_func=None):
    """Xóa trùng lặp theo key function."""
    seen = set()
    current = self.head
    while current:
        key = key_func(current.data) if key_func else current.data
        if key in seen:
            next_node = current.next
            self._remove_node(current)
            current = next_node
        else:
            seen.add(key)
            current = current.next

# Ví dụ: xóa trùng theo tên (bỏ qua tuổi)
dll3 = DoublyLinkedList()
for v in [('A', 1), ('B', 2), ('A', 3), ('C', 1)]:
    dll3.append(v)
dll3.remove_duplicates_custom(key_func=lambda x: x[0])
# Giữ ('A',1), ('B',2), ('C',1)