Traversal in Circular Linked List in C++

A circular linked list is a linked list where common nodes are connected to form a circle. There is no NULL at the end.

In this, any node can be at the starting point. So, we can traverse from any point. We can maintain a pointer to the last inserted node and the front can always be obtained as next of last and it is useful to implement a queue. Circular lists are useful in applications to go around the list. 

They are useful in solving Advance levels of data structure problems.      

Now let’s see how traversal works in a circular linked list in different programming languages.   

Code of Traversal in Circular Linked List

First, we create a class or structure Node. Then an empty circular linked list is created in which we push the elements.

#include <bits/stdc++.h>
using namespace std;

class Node
{
	public:
	int data;
	Node *next;
};

void push(Node **head_ref, int data)
{
	Node *ptr1 = new Node();
	Node *temp = *head_ref;
	ptr1->data = data;
	ptr1->next = *head_ref;

	/* If linked list is not NULL then
	set the next of last node */
	if (*head_ref != NULL)
	{
		while (temp->next != *head_ref)
			temp = temp->next;
		temp->next = ptr1;
	}
	else
		ptr1->next = ptr1; /*For the first node */

	*head_ref = ptr1;
}
void printList(Node *head)
{
	Node *temp = head;
	if (head != NULL)
	{
		do
		{
			cout << temp->data << " ";
			temp = temp->next;
		}
		while (temp != head);
	}
}

 int main()
{
	Node *head = NULL;

	push(&head, 12);
	push(&head, 56);
	push(&head, 2);
	push(&head, 11);

	cout << "Contents of Circular Linked List\n ";
	printList(head);

	return 0;
}

The output:

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

We earn a commission if you make a purchase, at no additional cost to you.

Contents of circular linked list

11 2 56 12

Time and Space Complexity

Time Complexity: O(n) As we need to move through the whole list

Auxiliary Space: O(1) As no extra space is used

Leave a Reply