Traversal in Circular Linked List in C/C++/Java/Pyhton
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.
In C++
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:
Contents of circular linked list
11 2 56 12
In C
First, we create a class or structure Node. Then an empty circular linked list is created in which we push the elements.
#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; /*For the first node */
*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()
{
/* Initialize lists as empty */
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;
}
The output:
Contents of circular linked list 11 2 56 12
In Java
First, we create a class or structure Node. Then an empty circular linked list is created in which we push the elements.
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);
}
}
// Driver Code
public static void main(String args[])
{
/* Initialize lists as empty */
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);
}
}
The output:
Contents of circular linked list 11 2 56 12
In Python
First, we create a class or structure Node. Then an empty circular linked list is created in which we push the elements.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
# Constructor to create a empty circular linked list
def __init__(self):
self.head = None
def push(self, data):
ptr1 = Node(data)
temp = self.head
ptr1.next = self.head
# If linked list is not None then set the next of
# last node
if self.head is not None:
while(temp.next != self.head):
temp = temp.next
temp.next = ptr1
else:
ptr1.next = ptr1 # For the first node
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()
The output:
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