Danh sách: danh sách liên kết đơn và liên kết đôi

5.1 Định nghĩa danh sách và các loại

Danh sách — là một cấu trúc dữ liệu động, gồm nhiều phần tử (nút), mỗi nút chứa dữ liệu và liên kết tới các nút khác. Không giống như mảng, danh sách có thể thay đổi kích thước trong quá trình thực thi chương trình.

Quan trọng! Trong trường hợp này không liên quan đến class list trong Python, mà nói về cấu trúc dữ liệu từ lý thuyết thuật toán.

Các loại danh sách:

• Danh sách liên kết đơn (Singly Linked List): Mỗi nút chứa dữ liệu và liên kết tới nút tiếp theo.
• Danh sách liên kết đôi (Doubly Linked List): Mỗi nút chứa dữ liệu, liên kết tới nút tiếp theo và liên kết tới nút trước đó.

5.2 Nguyên tắc hoạt động của danh sách liên kết đơn

Cấu trúc của danh sách liên kết đơn:

• Nút (Node): Gồm hai phần: dữ liệu và liên kết tới nút tiếp theo.
• Đầu (Head): Con trỏ trỏ tới nút đầu tiên của danh sách.

Nguyên tắc hoạt động:

• Thêm nút: Được thực hiện bằng cách tạo một nút mới và cập nhật liên kết của nút cuối cùng tới nút mới.
• Xóa nút: Cần cập nhật liên kết của nút trước đó tới nút tiếp theo của nút bị xóa.

Ví dụ thực hiện:

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Ví dụ sử dụng:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Kết quả: 1 -> 2 -> 3 -> None

5.3 Nguyên tắc hoạt động của danh sách liên kết đôi

Cấu trúc của danh sách liên kết đôi:

• Nút (Node): Gồm ba phần: dữ liệu, liên kết tới nút tiếp theo và liên kết tới nút trước đó.
• Đầu (Head): Con trỏ trỏ tới nút đầu tiên của danh sách.
• Đuôi (Tail): Con trỏ trỏ tới nút cuối cùng của danh sách (không bắt buộc, nhưng thường được sử dụng).

Nguyên tắc hoạt động:

• Thêm nút: Được thực hiện bằng cách tạo một nút mới và cập nhật liên kết của nút cuối cùng và nút mới.
• Xóa nút: Cần cập nhật liên kết của các nút lân cận tới nút bị xóa.

Ví dụ thực hiện:

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Ví dụ sử dụng:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Kết quả: 1 <-> 2 <-> 3 <-> None

5.4 Các thao tác chính

Các thao tác chính: thêm, xóa, tìm kiếm

Thêm:

• Danh sách liên kết đơn: Thêm một nút mới vào cuối danh sách yêu cầu đi qua tất cả các nút cho đến nút cuối cùng và cập nhật liên kết của nút cuối cùng.
• Danh sách liên kết đôi: Thêm một nút mới vào cuối danh sách tương tự như danh sách liên kết đơn, nhưng cũng cần cập nhật liên kết prev của nút mới tới nút trước đó.

Xóa:

• Danh sách liên kết đơn: Xóa nút yêu cầu đi qua danh sách đến nút cần xóa và cập nhật liên kết của nút trước đó tới nút tiếp theo của nút cần xóa.
• Danh sách liên kết đôi: Xóa nút yêu cầu cập nhật liên kết next và prev của các nút lân cận nút bị xóa.

Tìm kiếm: Duyệt qua danh sách từ đầu đến đuôi và so sánh dữ liệu của mỗi nút với giá trị cần tìm. Độ phức tạp thời gian — O(n).

5.5 Ví dụ sử dụng danh sách

Hãy cùng tạo một stack dựa trên danh sách liên kết đơn nhé.

Stack có thể dễ dàng được thực hiện bằng danh sách liên kết đơn, sử dụng các phương thức thêm push và xóa pop các phần tử. Nó cần có 2 phương thức:

• push — thêm một phần tử mới vào cuối danh sách
• pop — lấy phần tử cuối cùng ra khỏi danh sách

Ví dụ thực hiện:

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Ví dụ sử dụng:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Kết quả: 3 -> 2 -> 1 -> None
print(stack.pop())  # Kết quả: 3
stack.display()  # Kết quả: 2 -> 1 -> None