Chương trình Python xóa nút khỏi giữa danh sách liên kết đôi

Khi cần xóa nút ở giữa danh sách liên kết đôi, ta tính chỉ số giữa, di chuyển con trỏ đến nút đó, sau đó nối nút trước và nút sau của nó.

Ví dụ

class Node:
    def __init__(self, my_data):
        self.prev = 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 delete_from_middle(self):
        if self.head is None:
            return
        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
            if curr == self.head:
                self.head = curr.next
                self.tail.next = None
            elif curr == self.tail:
                self.tail = self.tail.prev
            else:
                curr.prev.next = curr.next
                curr.next.prev = curr.prev
            self.size -= 1

my_instance = double_list()
print("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)
my_instance.add_data(77)
my_instance.add_data(92)
my_instance.print_it()
while my_instance.head is not None:
    my_instance.delete_from_middle()
    print("Danh sách sau khi xóa nút giữa:")
    my_instance.print_it()

Kết quả

Thêm phần tử vào danh sách liên kết đôi
Các nút trong danh sách liên kết đôi:
10
24
54
77
92
Danh sách sau khi xóa nút giữa:
Các nút trong danh sách liên kết đôi:
24
54
77
92
Danh sách sau khi xóa nút giữa:
Các nút trong danh sách liên kết đôi:
54
77
92
Danh sách sau khi xóa nút giữa:
Các nút trong danh sách liên kết đôi:
77
92
Danh sách sau khi xóa nút giữa:
Các nút trong danh sách liên kết đôi:
92
Danh sách sau khi xóa nút giữa:
Danh sách rỗng

Giải thích

• Lớp Node và double_list có size.
• delete_from_middle tính mid, di chuyển curr đến vị trí mid.
• Xử lý 3 trường hợp: curr là head, curr là tail, curr ở giữa (nối prev.next = next, next.prev = prev).
• Giảm size, lặp xóa cho đến khi rỗng.