Even someone who knows nothing about binary arithmetic, algebra, or the difference between system calls and kernels will find computer science fascinating. This is a topic about which I am passionate. Data Structures is the most enjoyable to learn of all the topics in CSE. "Smart data structures and dumb code work a lot better than the other way around," said Sir Eric S. Raymond.

Data Structures is a format for organizing, managing, and storing data that allows quick access and modification. We use different data structures for various objectives depending on the use case.

Today's topic is traversing a circular linked list, a DS topic.

Given a pointer 'HEAD' to the first node of a circular linked list, we have to write a function to traverse and print its elements.

Approach

To begin, we must understand what a circular linked list is to solve the problem.

A circular linked list is one in which the last node, or tail, points to the linked list's first node, i.e., ‘HEAD’. And hence theirs no NULL node at the end of CLL. While traversing the CLL, we have to check if we’ve completed the list once and are now on the first node ‘HEAD’; else, we’ll be looping through it endlessly.

This is how a circular linked list looks.

Now that we’ve understood what a circular linked list is, let's discuss how the algorithm will work.

The 'HEAD' node address will be stored in a 'TEMP' pointer, and we'll loop until 'TEMP' is not NULL, which will never happen in a circular linked list because the tail point to the head. So, for CLL, the end case is to check if 'TEMP' is back on the 'HEAD' node, i.e., 'TEMP == HEAD,' and then exit the loop.

Algorithm

Initialise the ‘TEMP’ pointer to point to the ‘HEAD’ of the circular linked list.

Then we loop till ‘TEMP’ is not NULL(which will never happen).

Print the current node and check if ‘TEMP == HEAD’, then we know we’ve reached the end of the list and are now at the beginning of CLL, so we break from the loop.

Else we increment the ‘TEMP’ pointer to its next node and continue.

#include <iostream>
using namespace std;
// Class for Circular Linked List Node.
class Node
{
public:
// Variable to store the data.
int data;
// Pointer to the next node.
Node *next;
};
// Function to traverse a circular linked list.
void traverseLinkedList(Node *head)
{
// Create a temporary pointer pointing to the blogs whether 'HEAD' of the circular linked list.
Node *temp = head;
// Loop until the 'TEMP' is not pointing to a NULL node, which will not happen, but we'll break the loop using break keyword.
while (temp != NULL)
{
// Printing node's data.
cout << temp->data;
// Moving to the next node.
temp = temp->next;
// If we are back on the 'HEAD' node, break from the loop.
if (temp == head)
break;
cout << " -> ";
}
}
int main()
{
int n, x;
cout << "Enter the number of elements in the circular linked list: ";
cin >> n;
Node *head = new Node();
Node *temp = head;
cout << " Enter the Elements: ";
for (int i = 0; i < n; i++)
{
cin >> x;
Node *ptr = new Node();
ptr->data = x;
temp->next = ptr;
temp = ptr;
}
head = head->next;
temp->next = head;
traverseLinkedList(head);
return 0;
}

Input

Enter the number of elements in the circular linked list: 7
Enter the Elements: 4 10 7 8 9 21 -1

Output

4 -> 10 -> 7 -> 8 -> 9 -> 21 -> -1

Complexities

Time Complexity

O(N), where ‘N’ is the number of elements in the Circular Linked List.

Since we are visiting 'N' elements hence, the time complexity is O(N).

Space Complexity

O(1), since we are not using any extra auxiliary space.

Can we access the random element of the LinkedList?

We can not access any element of the LinkedList directly. We don’t have direct access to every element of LinkedList. If we want to access the ith element of the LinkedList, then we need to traverse the LinkedList till the ith index.

What is the key difference between Circular Linked List and a Singly Linked List?

Circular Linked List much like a circle had no beginning or ending node whereas Singly Linked Lists have clear starting and ending nodes.

Conclusion

I hope you had fun reading the article, where circular linkedlist traversal is the main concern. In this blog we have traversed the circular linked list using Java language.