We have discussed Circular Linked List Introduction and Applications, in the previous post on Circular Linked List. In this post, traversal operation is discussed.
In a conventional linked list, we traverse the list from the head node and stop the traversal when we reach NULL. In a circular linked list, we stop traversal when we reach the first node again. Following is the C code for the linked list traversal.
C++
void printList(Node* head)
{
Node* temp = head;
if (head != NULL) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
}
|
C
void printList(struct Node *first)
{
struct Node *temp = first;
if (first != NULL)
{
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != first);
}
}
|
Java
import java.util.*;
static void printList(Node head)
{
Node temp = head;
if (head != null)
{
do
{
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
|
Python3
def printList(self):
temp = self.head
if self.head is not None:
while(True):
print(temp.data, end=" ")
temp = temp.next
if (temp == self.head):
break
|
C#
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
Console.Write(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
|
Javascript
<script>
function printList(head)
{
var temp = head;
if (head != null)
{
do
{
document.write(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
Following are complete programs to demonstrate the traversal of a circular linked list.
C++
#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 (*head_ref != NULL)
{
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1;
*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;
}
|
C
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void push(struct Node **head_ref, int data)
{
struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));
struct Node *temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
if (*head_ref != NULL)
{
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1;
*head_ref = ptr1;
}
void printList(struct Node *head)
{
struct Node *temp = head;
if (head != NULL)
{
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
}
}
int main()
{
struct Node *head = NULL;
push(&head, 12);
push(&head, 56);
push(&head, 2);
push(&head, 11);
printf("Contents of Circular Linked List\n ");
printList(head);
return 0;
}
|
Java
import java.util.*;
import java.io.*;
public class GFG {
static class Node {
int data;
Node next;
};
static Node push(Node head_ref, int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
if (head_ref != null) {
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
public static void main(String args[])
{
Node head = null;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
System.out.println("Contents of Circular "
+ "Linked List:");
printList(head);
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def push(self, data):
ptr1 = Node(data)
temp = self.head
ptr1.next = self.head
if self.head is not None:
while(temp.next != self.head):
temp = temp.next
temp.next = ptr1
else:
ptr1.next = ptr1
self.head = ptr1
def printList(self):
temp = self.head
if self.head is not None:
while(True):
print (temp.data, end=" ")
temp = temp.next
if (temp == self.head):
break
cllist = CircularLinkedList()
cllist.push(12)
cllist.push(56)
cllist.push(2)
cllist.push(11)
print ("Contents of circular Linked List")
cllist.printList()
|
C#
using System;
public class GFG{
public class Node {
public int data;
public Node next;
}
static Node push(Node head_ref, int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
if (head_ref != null) {
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
Console.Write(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
static public void Main (){
Node head = null;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
Console.WriteLine("Contents of Circular "
+ "Linked List:");
printList(head);
}
}
|
Javascript
<script>
class Node
{
constructor(data)
{
this.data=data;
this.next=null;
}
}
function push(head_ref, data)
{
let ptr1 = new Node();
let temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
if (head_ref != null)
{
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
function printList(head)
{
let temp = head;
if (head != null)
{
do
{
document.write(temp.data + " ");
temp = temp.next;
}
while (temp != head);
}
}
let head = null;
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
document.write("Contents of Circular " +
"Linked List:<br>");
printList(head);
</script>
|
Output
Contents of Circular Linked List
11 2 56 12
Time Complexity: O(n) As we need to move through the whole list
Auxiliary Space: O(1) As no extra space is used
Program to traverse a linked list using recursion is as follows:
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
class GFG {
private:
Node* head;
public:
GFG() {
this->head = nullptr;
}
void push(int data, Node* temp) {
if (this->head == nullptr) {
Node* node = new Node(data);
this->head = node;
node->next = this->head;
return;
}
if (temp == nullptr) {
temp = this->head;
}
if (temp->next == this->head) {
Node* node = new Node(data);
node->next = this->head;
temp->next = node;
return;
}
push(data, temp->next);
}
void traverse(Node* temp) {
if (temp == nullptr) {
temp = this->head;
}
if (temp->next == this->head) {
cout << temp->data << endl;
return;
}
cout << temp->data << "-->";
traverse(temp->next);
}
};
int main() {
GFG clist = GFG();
clist.push(2, nullptr);
clist.push(3, nullptr);
clist.push(7, nullptr);
clist.push(5, nullptr);
cout << "Traversed Circular Linked List: " << endl;
clist.traverse(nullptr);
return 0;
}
|
Java
import java.io.*;
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
public class GFG {
Node head;
public GFG() { this.head = null; }
public void push(int data, Node temp)
{
if (this.head == null) {
Node node = new Node(data);
this.head = node;
node.next = this.head;
return;
}
if (temp == null) {
temp = this.head;
}
if (temp.next == this.head) {
Node node = new Node(data);
node.next = this.head;
temp.next = node;
return;
}
push(data, temp.next);
}
public void traverse(Node temp)
{
if (temp == null) {
temp = this.head;
}
if (temp.next == this.head) {
System.out.print(temp.data + "\n");
return;
}
System.out.print(temp.data + "-->");
traverse(temp.next);
}
public static void main(String[] args)
{
GFG clist = new GFG();
clist.push(2, null);
clist.push(3, null);
clist.push(7, null);
clist.push(5, null);
System.out.println(
"Traversed Circular Linked List: ");
clist.traverse(null);
}
}
|
Python3
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def push(self, data, temp=None):
if self.head == None:
node = Node(data)
self.head = node
node.next = self.head
return
if temp == None:
temp = self.head
if temp.next == self.head:
node = Node(data)
node.next = self.head
temp.next = node
return
self.push(data, temp.next)
def traverse(self, temp=None):
if temp == None:
temp = self.head
if temp.next == self.head:
print(temp.data, end="\n")
return
print(temp.data, end="-->")
self.traverse(temp.next)
if __name__ == "__main__":
clist = CircularLinkedList()
clist.push(2)
clist.push(3)
clist.push(7)
clist.push(5)
print("Traversed Circular Linked List: ", end="\n")
clist.traverse()
|
C#
using System;
public class Node {
public int Data;
public Node Next;
public Node(int data)
{
this.Data = data;
this.Next = null;
}
}
public class GFG {
public Node Head
{
get;
set;
}
public GFG() { this.Head = null; }
public void Push(int data, Node temp)
{
if (this.Head == null) {
Node node = new Node(data);
this.Head = node;
node.Next = this.Head;
return;
}
if (temp == null) {
temp = this.Head;
}
if (temp.Next == this.Head) {
Node node = new Node(data);
node.Next = this.Head;
temp.Next = node;
return;
}
Push(data, temp.Next);
}
public void Traverse(Node temp)
{
if (temp == null) {
temp = this.Head;
}
if (temp.Next == this.Head) {
Console.WriteLine(temp.Data);
return;
}
Console.Write(temp.Data + "-->");
Traverse(temp.Next);
}
static public void Main()
{
GFG clist = new GFG();
clist.Push(2, null);
clist.Push(3, null);
clist.Push(7, null);
clist.Push(5, null);
Console.WriteLine(
"Traversed Circular Linked List:");
clist.Traverse(null);
}
}
|
Javascript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class GFG {
constructor() {
this.head = null;
}
push(data, temp) {
if (!this.head) {
this.head = new Node(data);
this.head.next = this.head;
return;
}
temp = temp || this.head;
if (temp.next === this.head) {
const node = new Node(data);
node.next = this.head;
temp.next = node;
return;
}
this.push(data, temp.next);
}
traverse() {
var x=""
let temp = this.head;
while (temp.next !== this.head) {
x=x+temp.data + "-->";
temp = temp.next;
}
x=x+temp.data ;
console.log(x);
}
}
const clist = new GFG();
clist.push(2);
clist.push(3);
clist.push(7);
clist.push(5);
console.log('Traversed Circular Linked List:');
clist.traverse();
|
Output
Traversed Circular Linked List:
2-->3-->7-->5
Time Complexity: O(n)
Auxiliary Space: O(1)
You may like to see the following posts on Circular Linked List
Split a Circular Linked List into two halves
Sorted insert for circular linked list
We will soon be discussing the implementation of insert-delete operations for circular linked lists.
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
