Danh Sách Liên Kết Đôi (Doubly Linked List) trong Python

Danh sách liên kết đôi (Doubly Linked List) là một cấu trúc dữ liệu cổ điển trong lập trình, có khả năng lưu trữ dữ liệu tương tự như danh sách liên kết đơn (Singly Linked List), nhưng với một điểm khác biệt quan trọng: mỗi node (đơn vị lưu trữ) trong danh sách liên kết đôi không chỉ có con trỏ next trỏ đến node tiếp theo mà còn có con trỏ prev trỏ về node trước đó. Điều này giúp cho việc thao tác và duyệt qua danh sách trở nên linh hoạt và tiện lợi hơn.

Cấu Trúc của Node trong Danh Sách Liên Kết Đôi

Mỗi node trong danh sách liên kết đôi thường chứa ba thành phần chính:

Data: Chứa dữ liệu mà node đó lưu trữ.
Next: Con trỏ này trỏ đến node tiếp theo trong danh sách.
Prev: Con trỏ này trỏ về node trước đó trong danh sách.

Cài Đặt Danh Sách Liên Kết Đôi

Dưới đây là cách định nghĩa node và danh sách liên kết đôi bằng Python:

python Copy

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

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

Phương Thức Thêm Node: Append và Prepend

Phương Thức Append

Phương thức này cho phép bạn thêm một node mới vào cuối danh sách:

python Copy

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

Phương Thức Prepend

Giúp thêm một node mới ở đầu danh sách:

python Copy

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

Thêm Node Trước và Sau Node Cụ Thể

Thêm Node Trước Một Node Cụ Thể

python Copy

def add_before(self, target_data, data):
        temp = self.head
        while temp:
            if temp.data == target_data:
                new_node = Node(data)
                new_node.next = temp
                new_node.prev = temp.prev
                if temp.prev:
                    temp.prev.next = new_node
                else:
                    self.head = new_node
                temp.prev = new_node
                return
            temp = temp.next
        print(f"Node {target_data} không tồn tại trong danh sách")

Thêm Node Sau Một Node Cụ Thể

python Copy

def add_after(self, target_data, data):
        temp = self.head
        while temp:
            if temp.data == target_data:
                new_node = Node(data)
                new_node.next = temp.next
                if temp.next:
                    temp.next.prev = new_node
                temp.next = new_node
                new_node.prev = temp
                return
            temp = temp.next
        print(f"Node {target_data} không tồn tại trong danh sách")

Xóa Node

Bạn có thể xóa một node dựa trên dữ liệu của nó:

python Copy

def delete(self, target_data):
        temp = self.head

        if not temp:
            print("Danh sách rỗng")
            return

        if temp.next is None and temp.data == target_data:
            self.head = None
            return

        if temp.data == target_data:
            self.head = temp.next
            self.head.prev = None
            return

        while temp:
            if temp.data == target_data:
                if temp.next:
                    temp.prev.next = temp.next
                    temp.next.prev = temp.prev
                else:
                    temp.prev.next = None
                return
            temp = temp.next
        print(f"Node {target_data} không tồn tại trong danh sách")

Đảo Ngược Danh Sách

Bạn có thể đảo ngược danh sách liên kết đôi:

python Copy

def reverse(self):
        temp = self.head
        if not temp:
            return

        while temp:
            temp.prev, temp.next = temp.next, temp.prev
            if not temp.prev:
                self.head = temp
            temp = temp.prev

Ví Dụ Sử Dụng

Dưới đây là một ví dụ minh họa cho việc sử dụng danh sách liên kết đôi:

python Copy

# Khởi tạo danh sách liên kết đôi
radll = DoublyLinkedList()

# Thêm các phần tử vào danh sách
radll.append(10)
radll.append(20)
radll.append(30)
radll.prepend(0)
m
# In danh sách
print("Danh sách liên kết đôi ban đầu:")
radll.print_list()

# Thêm node sau node với giá trị 20
radll.add_after(20, 25)
print("\nSau khi thêm 25 sau 20:")
radll.print_list()

# Thêm node trước node có giá trị 10
radll.add_before(10, 5)
print("\nSau khi thêm 5 trước 10:")
radll.print_list()

# Xóa node đầu tiên
radll.delete(0)
print("\nSau khi xóa node đầu (0):")
radll.print_list()

# Xóa node cuối cùng
radll.delete(30)
print("\nSau khi xóa node cuối (30):")
radll.print_list()

# Đảo ngược danh sách
radll.reverse()
print("\nSau khi đảo ngược danh sách:")
radll.print_list()

Ưu và Nhược Điểm của Các Loại Danh Sách Liên Kết

Danh Sách Liên Kết Đơn (Singly Linked List)

Ưu điểm: Cấu trúc đơn giản, tiêu tốn ít bộ nhớ.
Nhược điểm: Không thể duyệt ngược và việc chèn, xóa node trong danh sách thường chậm hơn.

Danh Sách Liên Kết Vòng (Circular Linked List)

Ưu điểm: Cho phép duyệt vòng vô tận và thích hợp cho các ứng dụng yêu cầu tính tuần hoàn.
Nhược điểm: Khó xác định điểm kết thúc danh sách và không thể duyệt ngược trong danh sách liên kết đơn.