Chương trình Python chèn nút mới vào giữa danh sách liên kết đôi

Khi cần chèn nút mới vào giữa danh sách liên kết đôi (doubly linked list), ta định nghĩa lớp Node với ba thuộc tính: dữ liệu, con trỏ next và prev. Lớp quản lý danh sách có head, tail và size.

Ví dụ

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
        self.size = 0

    def add_data(self, my_data):
        new_node = Node(my_data)
        if self.head is 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
        self.size += 1

    def print_it(self):
        curr = self.head
        if self.head is None:
            print("Danh sách rỗng")
            return
        print("Các nút trong danh sách liên kết đôi:")
        while curr is not None:
            print(curr.data)
            curr = curr.next

    def add_data_in_middle(self, my_data):
        new_node = Node(my_data)
        if self.head is None:
            self.head = self.tail = new_node
            self.head.previous = None
            self.tail.next = None
        else:
            curr = self.head
            mid = (self.size // 2) if (self.size % 2 == 0) else ((self.size + 1) // 2)
            for i in range(1, mid):
                curr = curr.next
            temp = curr.next
            temp.previous = curr
            curr.next = new_node
            new_node.previous = curr
            new_node.next = temp
            temp.previous = new_node
        self.size += 1

my_instance = double_list()
print("Đang thêm phần tử vào danh sách liên kết đôi")
my_instance.add_data(10)
my_instance.add_data(24)
my_instance.add_data(54)
print("Thêm phần tử vào giữa danh sách")
my_instance.add_data_in_middle(77)
my_instance.print_it()
my_instance.add_data_in_middle(92)
my_instance.print_it()

Kết quả

Đang thêm phần tử vào danh sách liên kết đôi
Thêm phần tử vào giữa danh sách
Các nút trong danh sách liên kết đôi:
10
24
77
54
Các nút trong danh sách liên kết đôi:
10
24
92
77
54

Giải thích

• Lớp Node đại diện cho nút.
• Lớp double_list quản lý head, tail, size.
• Phương thức add_data thêm vào cuối.
• Phương thức add_data_in_middle tính chỉ số giữa, chèn nút mới giữa curr và temp.
• Phương thức print_it duyệt từ head in ra dữ liệu.
• Tạo instance, thêm dữ liệu, chèn giữa, in kết quả.