Chương trình C++ triển khai danh sách liên kết đơn vòng (Circular Singly Linked List)

Danh sách liên kết đơn vòng (Circular Singly Linked List): mỗi nút chứa dữ liệu và con trỏ next. Nút cuối trỏ về head (nút đầu), tạo thành vòng tròn.

Ví dụ

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *next;
};

struct Node* head = NULL;

void insert(int newdata) {
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* ptr = head;
    newnode->data = newdata;
    newnode->next = head;
    if (head != NULL) {
        while (ptr->next != head)
            ptr = ptr->next;
        ptr->next = newnode;
    } else
        newnode->next = newnode;
    head = newnode;
}

void display() {
    struct Node* ptr;
    ptr = head;
    do {
        cout << ptr->data << " ";
        ptr = ptr->next;
    } while (ptr != head);
}

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout << "The circular linked list is: ";
    display();
    return 0;
}

Kết quả

The circular linked list is: 9 2 7 1 3

Cấu trúc Node

struct Node {
    int data;
    struct Node *next;
};

Hàm insert() - Thêm vào đầu

Tạo newnode, next = head. Nếu head != NULL: tìm nút cuối (ptr->next == head), gán ptr->next = newnode. Nếu head == NULL: newnode->next = newnode (tự trỏ). Cập nhật head = newnode.

void insert(int newdata) {
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* ptr = head;
    newnode->data = newdata;
    newnode->next = head;
    if (head != NULL) {
        while (ptr->next != head)
            ptr = ptr->next;
        ptr->next = newnode;
    } else
        newnode->next = newnode;
    head = newnode;
}

Hàm display() - Hiển thị

Dùng vòng lặp do-while: bắt đầu từ head, in dữ liệu, chuyển next, dừng khi quay về head.

void display() {
    struct Node* ptr;
    ptr = head;
    do {
        cout << ptr->data << " ";
        ptr = ptr->next;
    } while (ptr != head);
}

Hàm main()

int main() {
    insert(3);
    insert(1);
    insert(7);
    insert(2);
    insert(9);
    cout << "The circular linked list is: ";
    display();
    return 0;
}