Python - Tìm kiếm phần tử trong Doubly Linked List

Doubly Linked List (Danh sách liên kết đôi) là cấu trúc dữ liệu mỗi nút (node) có 3 thành phần: dữ liệu, con trỏ next (tiếp theo), con trỏ prev (trước đó). Cho phép duyệt 2 chiều.

Triển khai

class Node:
    """Nút trong Doubly Linked List."""
    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):
        """Thêm node vào cuối list."""
        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 search(self, value):
        """
        Tìm kiếm giá trị trong list.
        
        Returns:
            tuple: (found: bool, position: int, node: Node)
                   position là 1-based index
        """
        current = self.head
        position = 1
        
        while current:
            if current.data == value:
                return True, position, current
            current = current.next
            position += 1
        
        return False, -1, None
    
    def display(self):
        """Hiển thị list từ head đến tail."""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" <-> ".join(elements) if elements else "Empty")
    
    def display_reverse(self):
        """Hiển thị list từ tail về head."""
        elements = []
        current = self.tail
        while current:
            elements.append(str(current.data))
            current = current.prev
        print(" <-> ".join(elements) if elements else "Empty")

# Demo
dll = DoublyLinkedList()
print("Thêm các phần tử: 10, 24, 54, 77, 24, 0")
for val in [10, 24, 54, 77, 24, 0]:
    dll.append(val)

print("\nDanh sách (head -> tail):")
dll.display()

print("\nDanh sách (tail -> head):")
dll.display_reverse()

# Tìm kiếm
print("\n--- Tìm kiếm ---")
for target in [77, 7, 24, 100]:
    found, pos, node = dll.search(target)
    if found:
        print(f"Tìm thấy {target} tại vị trí {pos}")
        # Có thể truy cập node.prev, node.next
        if node.prev:
            print(f"  Node trước: {node.prev.data}")
        if node.next:
            print(f"  Node sau: {node.next.data}")
    else:
        print(f"Không tìm thấy {target}")

Kết quả

Thêm các phần tử: 10, 24, 54, 77, 24, 0

Danh sách (head -> tail):
10 <-> 24 <-> 54 <-> 77 <-> 24 <-> 0

Danh sách (tail -> head):
0 <-> 24 <-> 77 <-> 54 <-> 24 <-> 10

--- Tìm kiếm ---
Tìm thấy 77 tại vị trí 4
  Node trước: 54
  Node sau: 24
Không tìm thấy 7
Tìm thấy 24 tại vị trí 2 (lần đầu)
  Node trước: 10
  Node sau: 54
Không tìm thấy 100

Giải thích

• Class Node lưu data, prev, next.
• Class DoublyLinkedList quản lý head, tail.
• append(): O(1) nhờ có tail pointer.
• search(): duyệt từ head, O(n) worst case. Trả về vị trí 1-based.
• Có thể duyệt ngược từ tail nhờ con trỏ prev.

Tìm kiếm tất cả vị trí (duplicate values)

def search_all(self, value):
    """Trả về list tất cả vị trí tìm thấy."""
    positions = []
    current = self.head
    pos = 1
    while current:
        if current.data == value:
            positions.append(pos)
        current = current.next
        pos += 1
    return positions

print(dll.search_all(24))  # [2, 5]

Độ phức tạp

• Tìm kiếm: O(n) - phải duyệt tuần tự.
• Thêm cuối: O(1).
• Thêm đầu: O(1).
• Xóa: O(1) nếu đã có node, O(n) nếu phải tìm.
• Không gian: O(n).

So sánh với Singly Linked List