Danh sách liên kết đôi vòng (Doubly Linked Circular List) trong C++

Danh sách liên kết vòng: nút đầu trỏ đến nút cuối, nút cuối trỏ đến nút đầu. Cả danh sách đơn và đôi đều có thể làm vòng.

Danh sách liên kết đôi vòng: next của nút cuối trỏ về nút đầu, prev của nút đầu trỏ về nút cuối → vòng hai chiều.

Các thao tác chính

• Duyệt xuôi (displayForward): từ head đến last qua next
• Duyệt ngược (displayBackward): từ last về head qua prev
• Thêm đầu (insertFirst): cập nhật head, prev của head cũ
• Thêm cuối (insertLast): cập nhật last, next của last cũ
• Thêm sau khóa (insertAfter): tìm khóa, chèn nút mới sau nó
• Xóa đầu (deleteFirst): cập nhật head, prev của head mới
• Xóa cuối (deleteLast): cập nhật last, next của last mới
• Xóa theo khóa (deleteNode): tìm nút, cập nhật next/prev của hàng xóm

Ví dụ mã nguồn hoàn chỉnh

#include <iostream>
using namespace std;

class Node {
public:
    int data, key;
    Node *next, *prev;
};

Node *head = NULL, *last = NULL;

bool isEmpty() { return head == NULL; }

void hienThiXuoi() {
    Node *ptr = head;
    cout << "\n[ ";
    while (ptr != NULL) {
        cout << "(" << ptr->key << "," << ptr->data << ") ";
        ptr = ptr->next;
    }
    cout << "]";
}

void hienThiNguoc() {
    Node *ptr = last;
    cout << "\n[ ";
    while (ptr != NULL) {
        cout << "(" << ptr->key << "," << ptr->data << ") ";
        ptr = ptr->prev;
    }
    cout << "]";
}

void themDau(int key, int data) {
    Node *link = new Node();
    link->key = key; link->data = data;
    if (isEmpty()) last = link;
    else head->prev = link;
    link->next = head;
    head = link;
}

void themCuoi(int key, int data) {
    Node *link = new Node();
    link->key = key; link->data = data;
    if (isEmpty()) last = link;
    else { last->next = link; link->prev = last; }
    last = link;
}

Node* xoaDau() {
    Node *temp = head;
    if (head->next == NULL) last = NULL;
    else head->next->prev = NULL;
    head = head->next;
    return temp;
}

Node* xoaCuoi() {
    Node *temp = last;
    if (head->next == NULL) head = NULL;
    else last->prev->next = NULL;
    last = last->prev;
    return temp;
}

Node* xoaKhoa(int key) {
    Node *curr = head, *prev = NULL;
    if (!head) return NULL;
    while (curr->key != key) {
        if (!curr->next) return NULL;
        prev = curr; curr = curr->next;
    }
    if (curr == head) head = head->next;
    else prev->next = curr->next;
    if (curr == last) last = prev;
    else curr->next->prev = prev;
    return curr;
}

bool themSau(int key, int newKey, int data) {
    Node *curr = head;
    if (!head) return false;
    while (curr->key != key) {
        if (!curr->next) return false;
        curr = curr->next;
    }
    Node *newLink = new Node();
    newLink->key = newKey; newLink->data = data;
    if (curr == last) { newLink->next = NULL; last = newLink; }
    else { newLink->next = curr->next; curr->next->prev = newLink; }
    newLink->prev = curr;
    curr->next = newLink;
    return true;
}

int main() {
    themDau(1,10); themDau(2,20); themDau(3,30);
    themDau(4,1); themDau(5,40); themDau(6,56);
    cout << "Danh sách (đầu→cuối):"; hienThiXuoi();
    cout << "\nDanh sách (cuối→đầu):"; hienThiNguoc();
    cout << "\nSau xóa đầu:"; xoaDau(); hienThiXuoi();
    cout << "\nSau xóa cuối:"; xoaCuoi(); hienThiXuoi();
    cout << "\nChèn sau khóa 4:"; themSau(4,7,13); hienThiXuoi();
    cout << "\nXóa khóa 4:"; xoaKhoa(4); hienThiXuoi();
    return 0;
}

Kết quả chạy chương trình

Danh sách (đầu→cuối): [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Danh sách (cuối→đầu): [ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
Sau xóa đầu: [ (5,40) (4,1) (3,30) (2,20) (1,10) ]
Sau xóa cuối: [ (5,40) (4,1) (3,30) (2,20) ]
Chèn sau khóa 4: [ (5,40) (4,1) (7,13) (3,30) (2,20) ]
Xóa khóa 4: [ (5,40) (7,13) (3,30) (2,20) ]