Lớp DoublyLinkedList (Danh sách liên kết kép) trong JavaScript

Doubly Linked List (Danh sách liên kết kép) mỗi node có 2 con trỏ: next (tiếp theo) và prev (trước đó). Cho phép duyệt 2 chiều, xóa node O(1) nếu có reference đến node.

Triển khai hoàn chỉnh (ES6 Class)

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    // Node class
    #Node = class {
        constructor(data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    };

    // Chèn tại vị trí (mặc định cuối)
    insert(data, position = this.length) {
        const node = new this.#Node(data);
        
        // 1. List rỗng
        if (!this.head) {
            this.head = this.tail = node;
            this.length++;
            return this.head;
        }
        
        // 2. Chèn đầu (position = 0)
        if (position <= 0) {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
            this.length++;
            return this.head;
        }
        
        // 3. Chèn cuối (position >= length)
        if (position >= this.length) {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
            this.length++;
            return this.tail;
        }
        
        // 4. Chèn giữa
        let current = this.head;
        let index = 0;
        while (index < position - 1) { // Dừng tại node TRƯỚC vị trí chèn
            current = current.next;
            index++;
        }
        // current là node trước vị trí chèn
        node.next = current.next;
        node.prev = current;
        current.next.prev = node;
        current.next = node;
        this.length++;
        return node;
    }

    // Xóa tại vị trí (mặc định đầu)
    remove(position = 0) {
        if (!this.head) return null;
        
        let removedNode;
        
        // 1. Xóa đầu
        if (position <= 0) {
            removedNode = this.head;
            this.head = this.head.next;
            if (this.head) this.head.prev = null;
            else this.tail = null; // List rỗng
        }
        // 2. Xóa cuối
        else if (position >= this.length - 1) {
            removedNode = this.tail;
            this.tail = this.tail.prev;
            if (this.tail) this.tail.next = null;
            else this.head = null;
        }
        // 3. Xóa giữa
        else {
            let current = this.head;
            let index = 0;
            while (index < position) {
                current = current.next;
                index++;
            }
            // current là node cần xóa
            removedNode = current;
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }
        
        this.length--;
        removedNode.next = removedNode.prev = null; // Giúp GC
        return removedNode.data;
    }

    // Tìm kiếm
    find(data) {
        let current = this.head;
        while (current) {
            if (current.data === data) return current;
            current = current.next;
        }
        return null;
    }

    // Duyệt xuôi
    toArray() {
        const arr = [];
        let current = this.head;
        while (current) {
            arr.push(current.data);
            current = current.next;
        }
        return arr;
    }

    // Duyệt ngược
    toArrayReverse() {
        const arr = [];
        let current = this.tail;
        while (current) {
            arr.push(current.data);
            current = current.prev;
        }
        return arr;
    }

    // Hiển thị
    display() {
        console.log(this.toArray().join(" <-> "));
    }
}

// Sử dụng
const dll = new DoublyLinkedList();
dll.insert(10);      // [10]
dll.insert(20);      // [10, 20]
dll.insert(5, 0);    // [5, 10, 20] - chèn đầu
dll.insert(15, 2);   // [5, 10, 15, 20] - chèn giữa
dll.display();       // 5 <-> 10 <-> 15 <-> 20
console.log(dll.toArrayReverse()); // [20, 15, 10, 5]

dll.remove(0);       // Xóa đầu -> [10, 15, 20]
dll.remove();        // Xóa cuối (mặc định 0? code gốc remove(0) xóa đầu. Sửa: remove() không tham số -> xóa cuối? Code gốc: remove(position=0) -> xóa đầu. Cần sửa default hoặc gọi remove(dll.length-1))
// Sửa code remove: default position = this.length - 1 cho xóa cuối? 
// Giữ nguyên code gốc: remove() xóa đầu. Muốn xóa cuối: remove(dll.length-1)
dll.remove(dll.length - 1); // Xóa cuối -> [10, 15]
dll.display();       // 10 <-> 15

Phân tích độ phức tạp

So sánh Singly vs Doubly

• Singly: Nhẹ bộ nhớ hơn (1 pointer), đơn giản, phù hợp stack/queue, forward-only.
• Doubly: Duyệt 2 chiều, xóa O(1) nếu có node ref, dễ implement undo/redo, cache LRU. Tốn bộ nhớ gấp đôi con trỏ.

Lưu ý code gốc: Code trong prompt có logic remove hơi khác (default position=0 xóa đầu, dùng this.tail.next != null check tail - hơi lạ). Code trên là phiên bản chuẩn hóa, rõ ràng hơn.