[DSA] Danh sách liên kết vòng (circular linked list)

1. Danh sách liên kết vòng là gì?

Danh sách liên kết vòng (circular linked list) là một dạng danh sách liên kết trong đó mỗi nút (node) có tham chiếu tới nút tiếp theo trong danh sách, và nút cuối cùng của danh sách có tham chiếu tới nút đầu tiên để tạo thành một vòng liên kết.

Trong một danh sách liên kết vòng, ta có thể bắt đầu từ bất kỳ nút nào trong danh sách và duyệt qua toàn bộ các nút trong danh sách bằng cách theo dõi các tham chiếu tới nút tiếp theo, cho đến khi quay lại nút ban đầu.

2. Các phép toán của danh sách liên kết vòng

Các phép toán chính của danh sách liên kết vòng (circular linked list) bao gồm:

• Thêm một nút vào danh sách (Insert): Thêm một nút mới vào danh sách liên kết vòng ở vị trí mong muốn.
• Xóa một nút khỏi danh sách (Delete): Xóa một nút khỏi danh sách liên kết vòng.
• Tìm kiếm một nút trong danh sách (Search): Tìm kiếm một nút với giá trị dữ liệu nhất định trong danh sách liên kết vòng.
• Hiển thị danh sách (Display): Hiển thị toàn bộ các nút trong danh sách liên kết vòng.
• Đếm số lượng nút trong danh sách (Count): Đếm số lượng nút trong danh sách liên kết vòng.
• Đảo ngược danh sách (Reverse): Đảo ngược thứ tự của các nút trong danh sách liên kết vòng.
• Chèn một nút theo thứ tự (InsertSorted): Chèn một nút mới vào danh sách liên kết vòng sao cho danh sách vẫn được sắp xếp theo thứ tự tăng dần hoặc giảm dần.
• Xóa toàn bộ danh sách (DeleteList): Xóa toàn bộ danh sách liên kết vòng và giải phóng bộ nhớ đã được cấp phát cho danh sách.

Các phép toán này giúp ta quản lý, thêm, sửa và xóa các nút trong danh sách liên kết vòng.

3. Ứng dụng của danh sách liên kết vòng

Danh sách liên kết vòng (circular linked list) có nhiều ứng dụng trong lập trình, bao gồm:

• Implement các cấu trúc dữ liệu khác: Danh sách liên kết vòng được sử dụng để xây dựng các cấu trúc dữ liệu phức tạp hơn như queue, stack, hash table, và các cấu trúc dữ liệu khác.
• Thực hiện các phép toán trên danh sách lặp đi lặp lại: Trong một số trường hợp, việc duyệt qua danh sách liên kết vòng có thể giúp ta giảm thiểu số lần phải thực hiện các phép toán trên danh sách, và giảm thiểu chi phí tính toán.
• Tạo vòng lặp vô hạn: Các danh sách liên kết vòng có thể được sử dụng để tạo ra các vòng lặp vô hạn trong các chương trình lập trình.
• Giải quyết các bài toán mô phỏng: Danh sách liên kết vòng cũng được sử dụng trong các bài toán mô phỏng và đồ họa để tạo ra các hiệu ứng chuyển động.
• Lưu trữ dữ liệu trên thiết bị nhúng: Với các thiết bị nhúng như vi điều khiển và các cảm biến, danh sách liên kết vòng là một cách tiết kiệm bộ nhớ để lưu trữ dữ liệu.

4. Hiện thực một số phép toán

#include <stdio.h>

#include <stdlib.h>

// Define a structure for a node

typedef struct Node {

int data;

struct Node* next;

} Node;

// Function to create a new node

Node* createNode(int data) {

Node* newNode = (Node*)malloc(sizeof(Node));

newNode->data = data;

newNode->next = NULL;

return newNode;

}

void insertNode(Node** head, int data, int position) {

Node* newNode = createNode(data);

// If the list is empty, make the new node the head node

if (*head == NULL) {

*head = newNode;

(*head)->next = *head;

return;

}

// If the new node is to be inserted at the beginning of the list

if (position == 1) {

newNode->next = (*head)->next;

(*head)->next = newNode;

return;

}

// Traverse the list to find the node after which the new node is to be inserted

Node* temp = (*head)->next;

int i;

for (i = 1; i < position - 1 && temp != *head; i++) {

temp = temp->next;

}

// If the given position is greater than the number of nodes in the list, insert at the end

if (temp == *head) {

while (temp->next != *head)

temp = temp->next;

}

// Insert the new node at the specified position

newNode->next = temp->next;

temp->next = newNode;

}

// Function to insert a node at the end of the list

void insertNodeAtTheEnd(Node** head, int data) {

// Create a new node

Node* newNode = createNode(data);

// If the list is empty, set the new node as the head node

if (*head == NULL) {

*head = newNode;

newNode->next = *head;

return;

}

// Otherwise, find the last node in the list and insert the new node after it

Node* last = *head;

while (last->next != *head)

last = last->next;

last->next = newNode;

newNode->next = *head;

}

// Function to delete a node with a given data value

void deleteNode(Node** head, int key) {

// Check if the list is empty

if (*head == NULL)

return;

// Find the node to be deleted

Node* curr = *head;

Node* prev = NULL;

while (curr->data != key) {

prev = curr;

curr = curr->next;

if (curr == *head)

return; // the node is not in the list

}

// Check if node is the only node in the list

if (curr->next == *head && curr == *head) {

*head = NULL;

free(curr);

return;

}

// Check if node is the head node

if (curr == *head) {

prev = *head;

while (prev->next != *head)

prev = prev->next;

*head = curr->next;

prev->next = *head;

free(curr);

}

// Node is not the head node

else {

prev->next = curr->next;

free(curr);

}

}

// Function to display the contents of the list

void display(Node* head) {

Node* curr = head;

if (curr == NULL) {

printf("The list is empty.\n");

return;

}

printf("Contents of the list: ");

do {

printf("%d ", curr->data);

curr = curr->next;

} while (curr != head);

printf("\n");

}

// Function to search for a node with a given data value

int search(Node* head, int key) {

Node* curr = head;

if (curr == NULL)

return 0;

do {

if (curr->data == key)

return 1;

curr = curr->next;

} while (curr != head);

return 0;

}

// Main function to test the circular linked list operations

int main() {

Node* head = NULL;

int choice, data, position, key;

while (1) {

printf("===========================");

printf("\nCircular Linked List Operations:\n");

printf("1. Insert a node\n");

printf("2. Delete a node\n");

printf("3. Display the contents of the list\n");

printf("4. Search for a node\n");

printf("5. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter the data to insert: ");

scanf("%d", &data);

printf("Enter the position to insert (1 for first, 2 for second, etc.): ");

scanf("%d", &position);

insertNode(&head, data, position);

break;

case 2:

printf("Enter the data to delete: ");

scanf("%d", &key);

deleteNode(&head, key);

break;

case 3:

display(head);

break;

case 4:

printf("Enter the data to search: ");

scanf("%d", &key);

if (search(head, key))

printf("Node found in the list.\n");

else

printf("Node not found in the list.\n");

break;

case 5:

printf("Exiting the program...\n");

exit(0);

default:

printf("Invalid choice. Please try again.\n");

break;

}

}

return 0;

}

Chú ý: 

Lý do chúng ta sử dụng Node** head thay vì Node* head trong hàm insertNode(Node** head, int data, int position) vì:

• Chúng ta cần cập nhật con trỏ head của danh sách liên kết vòng khi một nút mới được chèn vào đầu danh sách. 
• Nếu chúng ta chuyển Node* head làm đối số, thì bất kỳ thay đổi nào được thực hiện đối với con trỏ head bên trong hàm sẽ không được phản ánh bên ngoài hàm.
• Bằng cách dùng Node** head, chúng ta đang truyền địa chỉ của chính con trỏ head, điều này cho phép chúng ta cập nhật con trỏ head bên trong hàm và những thay đổi đó được phản ánh bên ngoài hàm.

Vì vậy, tóm lại, chúng ta sử dụng Node** head trong hàm insertNode(Node** head, int data, int position) để có thể cập nhật con trỏ head của danh sách và để những thay đổi đó được cập nhật ra bên ngoài hàm. Tuy nhiên, nếu bạn không muốn sử dụng Node** head, bạn có thể sử dụng Node* head và trả về con trỏ head sau khi đã được cập nhật dữ liệu từ hàm. Điều này sẽ yêu cầu thay đổi định nghĩa hàm thành: Node* insertNode(Node* head, int data, int position).