Danh sách liên kết vòng (Circular Linked List) trong JavaScript

Circular Linked List (Danh sách liên kết vòng) là biến thể của Linked List nơi node cuối cùng trỏ về node đầu tiên (và ngược lại nếu là Doubly), tạo thành một vòng tròn. Không có node nào có next (hoặc prev) là null.

Đặc điểm

• Singly Circular: tail.next = head.
• Doubly Circular: tail.next = head VÀ head.prev = tail.
• Không có null terminal. Duyệt vô hạn nếu không có điều kiện dừng.
• Útil cho: Round-robin scheduling, Buffer vòng (Ring buffer), Game loop, Playlist phát lại liên tục.

Triển khai Singly Circular Linked List (ES6 Class)

class CircularLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // Node class bên trong
    #Node = class {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    };

    // Thêm vào cuối (append)
    append(data) {
        const newNode = new this.#Node(data);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
            newNode.next = this.head; // Tự trỏ về mình (vòng 1 node)
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
            this.tail.next = this.head; // Đóng vòng
        }
        this.size++;
        return this;
    }

    // Thêm vào đầu (prepend)
    prepend(data) {
        const newNode = new this.#Node(data);
        if (!this.head) {
            this.head = this.tail = newNode;
            newNode.next = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;
            this.tail.next = this.head; // Cập nhật tail.next
        }
        this.size++;
        return this;
    }

    // Xóa node theo giá trị (phức tạp hơn do vòng)
    remove(data) {
        if (!this.head) return false;
        
        let current = this.head;
        let prev = this.tail; // Bắt đầu từ tail vì vòng
        
        do {
            if (current.data === data) {
                if (current === this.head && current === this.tail) {
                    // Chỉ còn 1 node
                    this.head = this.tail = null;
                } else if (current === this.head) {
                    // Xóa head
                    this.head = this.head.next;
                    this.tail.next = this.head;
                } else if (current === this.tail) {
                    // Xóa tail
                    this.tail = prev;
                    this.tail.next = this.head;
                } else {
                    // Xóa giữa
                    prev.next = current.next;
                }
                this.size--;
                return true;
            }
            prev = current;
            current = current.next;
        } while (current !== this.head); // Duyệt hết vòng
        
        return false; // Không tìm thấy
    }

    // Duyệt (cần điều kiện dừng)
    traverse(callback) {
        if (!this.head) return;
        let current = this.head;
        do {
            callback(current.data);
            current = current.next;
        } while (current !== this.head);
    }

    // Chuyển thành mảng
    toArray() {
        const arr = [];
        this.traverse(data => arr.push(data));
        return arr;
    }
}

// Sử dụng
const list = new CircularLinkedList();
list.append(1).append(2).append(3);
console.log(list.toArray()); // [1, 2, 3]
list.traverse(console.log);  // 1, 2, 3 (in ra rồi dừng)
// list.remove(2);
// console.log(list.toArray()); // [1, 3]

Lưu ý quan trọng khi làm việc Circular List

• Tránh vòng lặp vô tận: Luôn dùng do...while(current !== startNode) hoặc đếm size lần khi duyệt.
• Xóa node phức tạp hơn: Cần theo dõi prev (dùng do...while từ tail hoặc giữ prev biến).
• Không có tail (chỉ có head) thì append/xóa tail là O(n). Nên giữ tail reference.
• Memory Leak: Nên gán node.next = null khi xóa node cuối cùng hoặc clear list để GC giải phóng.

Ứng dụng thực tế

• Round Robin CPU Scheduling: Các process xếp hàng vòng.
• Circular Buffer / Ring Buffer: Queue kích thước cố định, ghi đè cũ nhất (Video streaming, Audio, Log buffer).
• Playlist / Carousel: Phát bài hát/hình ảnh lặp lại.
• Game Development: Turn-based multiplayer (next player).

Tóm lại: Circular Linked List nối đuôi vào đầu. Triển khai cần head, tail, cẩn thận duyệt (tránh lặp vô tận), xóa node phức tạp hơn. Phù hợp cho luồng dữ liệu vòng, scheduling, buffer.