Data Structure - Circular Linked List
A circular linked list is a variant of the linked list structure. Its core feature is that the last node of the linked list no longer points to NULL, but instead points back to the first node, making the entire linked list logically form a ring structure.
Structural characteristics of circular linked list
Singly circular linked list
Doubly circular linked list
Ordinary linked list: end next = NULL, traversal termination condition is cur == NULL
Circular linked list: end next = head, traversal termination condition is cur == head (back to starting point)
Common operations:Insert head node O(n) — need to find the tail node first | traversal uses do...while loop
Insert tail node O(1) (maintain tail pointer) | deletion similarly
Circular linked lists are mainly divided into two types:
- Singly circular linked list: each node stores only one next pointer, and the next of the last node points back to the head node
- Doubly circular linked list: based on the doubly linked list, the next of the last node points to the head node, and the prev of the head node points to the last node
The biggest feature of the circular linked list structure is that it naturally supports continuous traversal where the end connects back to the start.
The condition for determining the end of traversal is not "whether NULL is reached", but "whether the starting node is returned to".
Basic operations
Example
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Create a new node */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = newNode; /* For a single node, next points to itself, forming a self-loop */
return newNode;
}
/* Insert a node at the head of the circular linked list
Time complexity: O(n) — need to find the tail node first to update its next pointer */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
return newNode; /* Empty linked list, the new node forms a self-loop */
}
/* Find the tail node (i.e., the node whose next points to head) */
struct Node* tail = head;
while (tail->next != head) {
tail = tail->next;
}
newNode->next = head; /* The new node's next points to the original head node */
tail->next = newNode; /* The tail node's next points to the new node (new head) */
return newNode; /* The new node becomes the new head node */
}
/* Traverse the circular linked list (one cycle)
Start from the head node, stop when returning to the head node again */
void traverse(struct Node* head) {
if (head == NULL) return;
struct Node* cur = head;
printf("Circular linked list: ");
do {
printf("%d -> ", cur->data);
cur = cur->next;
} while (cur != head); /* Stop when returning to the starting point */
printf("(back to start)\n");
}
int main() {
struct Node* head = NULL;
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverse(head);
/* Output: Circular linked list: 10 -> 20 -> 30 -> (back to start) */
return 0;
}
The key to traversing a circular linked list is to use
do...whilestatement instead ofwhile. Because when usingwhile (cur != head), the initial state cur is equal to head, and the loop will not execute at all. Anddo...whileensures that the loop body is executed at least once, then checks the termination condition.
Classic application: Josephus ring problem
Elimination order and final result (n=7, m=3)
Josephus ring problem (Josephus Problem)is a classic mathematical problem:
Suppose n people stand in a circle. Counting starts from the 1st person, and every m-th person is eliminated from the circle. Then counting restarts from the next person, and this continues until only the last person remains.
This problem naturally fits the structural characteristics of a circular linked list: "connected end-to-end, accessed cyclically."
Example
#include <stdlib.h>
struct Node {
int data; /* Person number */
struct Node* next;
};
/* Josephus ring solution
Parameters: n total number of people, m every m-th counted person leaves the circle
Use a circular linked list to simulate the entire process */
void josephus(int n, int m) {
if (n <= 0) return;
/* Step 1: Create a circular linked list containing n people (numbered 1~n) */
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = head; /* When there is only one person, it forms a self-loop */
struct Node* tail = head;
for (int i = 2; i <= n; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->next = head; /* The new node's next always points to the head */
tail->next = newNode; /* The previous node's next points to the new node */
tail = newNode; /* Advance tail */
}
/* Step 2: Simulate the elimination process */
struct Node* cur = head;
struct Node* prev = tail; /* prev points to cur's predecessor, initially the tail node */
printf("Josephus ring (n=%d, m=%d) elimination order: ", n, m);
while (cur->next != cur) { /* End when only one node remains (self-loop) */
/* Counting: count m-1 times, advancing prev and cur simultaneously */
for (int count = 1; count < m; count++) {
prev = cur;
cur = cur->next;
}
/* When the count reaches m, cur is eliminated */
printf("%d ", cur->data);
prev->next = cur->next; /* Skip cur */
free(cur); /* Free the eliminated node */
cur = prev->next; /* Restart counting from the next person */
}
printf("=> Last survivor: %d\n", cur->data); /* Output the last person */
free(cur);
}
int main() {
josephus(7, 3);
/* Output: Josephus ring (n=7, m=3) elimination order: 3 6 2 7 5 1 => Last survivor: 4 */
return 0;
}
Other application scenarios
| Scenario | Description |
|---|---|
| Operating system round-robin time slice scheduling | The CPU allocates time slices to each process in turn. When a process exhausts its time slice, the next process takes its turn, forming a cycle. |
| Multiplayer games taking turns to play cards | In board and card games, players take turns acting in clockwise (or counterclockwise) order. |
| Circular buffer | A circular buffer for audio/video data streams; when full, it returns to the beginning and overwrites old data. |