New update is available. Click here to update.

Circular Linked List Traversal

Firdausia Fatima
Last Updated: Oct 20, 2022
Linked List

Introduction

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.

Also see, Singly Linked List to Circular Linked List

Problem Statement

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.

Circular Linked List

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.

Let’s try to code it now.

Program

#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.

Frequently Asked Questions 

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.

Recommended Reading: 

Recommended Problems:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on CodeStudio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.

Cheers!

Was this article helpful ?
0 upvotes