Xóa phần tử khỏi Doubly Linked List (Danh sách liên kết kép) bằng JavaScript

Xóa node trong Doubly Linked List dễ dàng hơn Singly List nhờ có con trỏ prev. Có 3 trường hợp chính:

3 Trường hợp xóa

1. Xóa Head (Đầu): head = head.next; head.prev = null;
2. Xóa Tail (Cuối): tail = tail.prev; tail.next = null;
3. Xóa giữa (Middle): prevNode.next = node.next; node.next.prev = prevNode;

Minh họa trực quan

Triển khai phương thức remove() chuẩn

class DoublyLinkedList {
    // ... constructor, Node, insert, head, tail, length ...

    remove(position = 0) { // Mặc định xóa đầu (position 0)
        if (this.length === 0) {
            console.log("List is already empty");
            return null;
        }
        
        this.length--;
        let current = this.head;
        
        // 1. Xóa đầu (position <= 0)
        if (position <= 0) {
            this.head = this.head.next;
            if (this.head) this.head.prev = null;
            else this.tail = null; // List rỗng
        }
        // 2. Xóa cuối (position >= length - 1) - SAU KHI length--
        else if (position >= this.length) { // length đã --
            this.tail = this.tail.prev;
            if (this.tail) this.tail.next = null;
            else this.head = null;
        }
        // 3. Xóa giữa
        else {
            let index = 0;
            while (index < position) {
                current = current.next;
                index++;
            }
            // current là node cần xóa
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }
        
        // Dọn dẹp reference giúp GC
        current.next = current.prev = null;
        return current.data; // Trả về data đã xóa
    }
}

Ví dụ sử dụng & Test

const list = new DoublyLinkedList();
list.insert(10);    // [10]
list.insert(20);    // [10, 20]
list.insert(30);    // [10, 20, 30]
console.log("Initial:", list.toArray()); // [10, 20, 30]

list.remove(1);     // Xóa index 1 (giá trị 20) -> [10, 30]
console.log("After remove(1):", list.toArray()); 

list.insert(15, 2); // Chèn 15 tại index 2 (cuối) -> [10, 30, 15]
console.log("After insert(15,2):", list.toArray());

list.remove();      // Xóa đầu (default 0) -> [30, 15]
console.log("After remove():", list.toArray());

list.remove(list.length - 1); // Xóa cuối -> [30]
console.log("After remove(last):", list.toArray());

Output

Initial: [ 10, 20, 30 ]
After remove(1): [ 10, 30 ]
After insert(15,2): [ 10, 30, 15 ]
After remove(): [ 30, 15 ]
After remove(last): [ 30 ]

Lưu ý quan trọng

• Index base 0: remove(0) xóa head, remove(length-1) xóa tail.
• Boundary check: Code xử lý position <= 0 (xóa đầu), position >= length (xóa cuối - sau khi length--).
• Dọn dẹp reference: node.next = node.prev = null giúp Garbage Collector giải phóng bộ nhớ node đã xóa (tránh memory leak).
• Trả về data: Thường trả về data của node bị xóa để caller biết gì đã bị xóa.

So sánh xóa Singly vs Doubly

Kết luận: Doubly Linked List làm cho việc xóa Tail và xóa giữa (khi có reference) trở nên O(1) nhờ con trỏ prev. Code xóa cần xử lý 3 trường hợp riêng biệt, cập nhật head/tail đúng, dọn dẹp reference.