Circular Linked List Traversal

Firdausia Fatima
Last Updated: May 13, 2022

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 organising, 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.

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.

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

Time Complexity

O(N), where ‘N’ is the number of elements in 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.

Key Takeaways

I hope you had fun reading the article. Other linked list blogs I recommend going through are Pairwise swap adjacent nodes of a linked list by changing pointersSingly Linked List to Circular Linked List, Applications of Linked List Data Structure, and many more

Head over to CodeStudio to read other such exciting blogs. 

Was this article helpful ?
0 upvotes