.png)
Circular Linked List Traversal
Problem Statement
Given a circular linked list, write a program to traverse the list and print all its elements exactly once.
In a circular linked list, the last node does not point to NULL. Instead, it points back to the first node, forming a loop. Because of this, special care must be taken to avoid infinite traversal.
Example
Input
Circular Linked List:
10 → 20 → 30 → 40 → (back to 10)
Output
10 20 30 40
Approach
- Check if the circular linked list is empty.
- If head == NULL, there are no nodes to traverse.
- Initialize a pointer current with the head node.
- Print the data of the current node.
- Move the pointer to the next node.
- Continue traversal until the pointer reaches the head node again.
- Stop the traversal once all nodes are visited exactly once.
A do-while loop is preferred because the head node must be processed at least once.
Algorithm
- If head is NULL, return.
- Set current = head.
- Repeat:
- Print current.data
- Move current = current.next
- Until current == head
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
Where n is the number of nodes in the circular linked list.
Implementation
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
void traverse(struct Node* head) {
if (head == NULL)
return;
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
}
// Helper to create circular list: 10→20→30→40→head
struct Node* createList() {
struct Node *head, *second, *third, *fourth;
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
fourth = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; head->next = second;
second->data = 20; second->next = third;
third->data = 30; third->next = fourth;
fourth->data = 40; fourth->next = head; // circular link
return head;
}
int main() {
struct Node* head = createList();
traverse(head);
return 0;
}
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
#include "cstdlib"
struct Node {
int data;
struct Node* next;
};
void traverse(struct Node* head) {
if (head == NULL)
return;
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
}
// Helper function
struct Node* createList() {
struct Node *head, *second, *third, *fourth;
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
fourth = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; head->next = second;
second->data = 20; second->next = third;
third->data = 30; third->next = fourth;
fourth->data = 40; fourth->next = head;
return head;
}
int main() {
struct Node* head = createList();
traverse(head);
return 0;
}Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularLinkedListTraversal {
static void traverse(Node head) {
if (head == null)
return;
Node current = head;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
}
}
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverse(head):
if head is None:
return
current = head
while True:
print(current.data, end=" ")
current = current.next
if current == head:
break
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function traverse(head) {
if (head === null) return;
let current = head;
do {
console.log(current.data);
current = current.next;
} while (current !== head);
}
Output-
10 20 30 40Key Points to Remember
- Circular linked lists do not have a NULL pointer
- Traversal must stop when the head node is reached again
- do-while loop is ideal for traversal
- Always handle the empty list case
Conclusion
Circular Linked List Traversal requires a different stopping condition compared to linear linked lists. By checking when the traversal reaches the head node again, all elements can be visited exactly once without causing an infinite loop. This approach is efficient, easy to implement, and commonly asked in data structure interviews and exams.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
