Data Modelling & AI Data Structure & Algorithm

Traversal of Circular Linked List

31 July 2024

2

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++

/* Function to print nodes in
a given Circular linked list */
void printList(Node* head)
{
    Node* temp = head;
 
    // If linked list is not empty
    if (head != NULL) {
 
        // Print nodes till we reach first node again
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
    }
}

C

/* Function to traverse a given Circular linked list and print nodes */
void printList(struct Node *first)
{
    struct Node *temp = first; 
 
    // If linked list is not empty
    if (first != NULL) 
    {
        // Keep printing nodes till we reach the first node again
        do
        {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        while (temp != first);
    }
}

Java

/* Function to print nodes in a
given Circular linked list */
import java.util.*;
 
static void printList(Node head)
{
    Node temp = head;
   
    // If linked list is not empty
    if (head != null) 
    {
       
        // Keep printing nodes till we reach the first node
        // again
        do
        {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
    }
}
 
// This code is contributed by pratham76.

Python3

# Function to print nodes in a given Circular linked list
def printList(self):
 
    temp = self.head
 
    # If linked list is not empty
    if self.head is not None:
        while(True):
 
            # Print nodes till we reach first node again
            print(temp.data, end=" ")
            temp = temp.next
            if (temp == self.head):
                break

C#

/* Function to print nodes in a
given Circular linked list */
static void printList(Node head)
{
    Node temp = head;
   
    // If linked list is not empty
    if (head != null) {
       
        // Keep printing nodes till we reach the first node
        // again
        do {
            Console.Write(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
    }
}
 
//This code is contributed by rutvik_56

Javascript

<script>
/* Function to print nodes in a
given Circular linked list */
function printList(head)
{
    var temp = head;
   
    // If linked list is not empty
    if (head != null) 
    {
       
        // Keep printing nodes till we reach the first node
        // again
        do
        {
            document.write(temp.data + " ");
            temp = temp.next;
        } while (temp != head);
    }
}
 
 
// This code contributed by umadevi9616
</script>

Time Complexity: O(n)
Auxiliary Space: O(1)

Following are complete programs to demonstrate the traversal of a circular linked list.

C++

// C++ program to implement 
// the above approach 
#include <bits/stdc++.h>
using namespace std;
 
/* structure for a node */
class Node 
{ 
    public:
    int data; 
    Node *next; 
}; 
 
/* Function to insert a node at the beginning 
of a Circular linked list */
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; 
} 
 
/* Function to print nodes in 
a given Circular linked list */
void printList(Node *head) 
{ 
    Node *temp = head; 
    if (head != NULL) 
    { 
        do
        { 
            cout << temp->data << " "; 
            temp = temp->next; 
        } 
        while (temp != head); 
    } 
} 
 
/* Driver program to test above functions */
int main() 
{ 
    /* Initialize lists as empty */
    Node *head = NULL; 
 
    /* Created linked list will be 11->2->56->12 */
    push(&head, 12); 
    push(&head, 56); 
    push(&head, 2); 
    push(&head, 11); 
 
    cout << "Contents of Circular Linked List\n "; 
    printList(head); 
 
    return 0; 
} 

C

// C program to implement
// the above approach
#include<stdio.h>
#include<stdlib.h>
 
/* structure for a node */
struct Node
{
    int data;
    struct Node *next;
};
 
/* Function to insert a node at the beginning of a Circular
   linked list */
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 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;
}
 
/* Function to print nodes in a given Circular linked list */
void printList(struct Node *head)
{
    struct Node *temp = head;
    if (head != NULL)
    {
        do
        {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        while (temp != head);
    }
}
 
/* Driver program to test above functions */
int main()
{
    /* Initialize lists as empty */
    struct Node *head = NULL;
 
    /* Created linked list will be 11->2->56->12 */
    push(&head, 12);
    push(&head, 56);
    push(&head, 2);
    push(&head, 11);
 
    printf("Contents of Circular Linked List\n ");
    printList(head);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
import java.io.*;
 
public class GFG {
 
    // node
    static class Node {
        int data;
        Node next;
    };
 
    /* Function to insert a node
    at the beginning of a Circular
    linked list */
    static Node 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;
 
        head_ref = ptr1;
 
        return head_ref;
    }
 
    /* Function to print nodes in a
    given Circular linked list */
    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;
 
        /* Created linked list will
           be 11.2.56.12 */
        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

# Python program to demonstrate 
# circular linked list traversal 
 
# Structure for a Node
class Node:
     
    # Constructor to create  a new 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
 
    # Function to insert a node at the beginning of a
    # circular linked list
    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 
 
    # Function to print nodes in a given circular linked list
    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
 
 
# Driver program to test above function
 
# Initialize list as empty
cllist = CircularLinkedList()
 
# Created linked list will be 11->2->56->12
cllist.push(12)
cllist.push(56)
cllist.push(2)
cllist.push(11)
 
print ("Contents of circular Linked List")
cllist.printList()
          

C#

// C# program to implement
// the above approach
using System;
 
public class GFG{
 
  // node
  public class Node {
    public int data;
    public Node next;
  }
 
  /* Function to insert a node
    at the beginning of a Circular
    linked list */
  static Node 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;
 
    head_ref = ptr1;
 
    return head_ref;
  }
 
  /* Function to print nodes in a
    given Circular linked list */
  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 (){
 
    /* Initialize lists as empty */
    Node head = null;
 
    /* Created linked list will
           be 11.2.56.12 */
    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);
  }
}
 
// This code is contributed by lokesh.

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// node 
class Node
{
    constructor(data)
    {
        this.data=data;
        this.next=null;
    }
}
 
/* Function to insert a node
at the beginning of a Circular
linked list */
function push(head_ref, data)
{
    let ptr1 = new Node();
    let 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; 
   
    head_ref = ptr1;
       
    return head_ref;
}
 
/* Function to print nodes in a 
given Circular linked list */
function printList(head)
{
    let temp = head;
    if (head != null)
    {
        do
        {
            document.write(temp.data + " ");
            temp = temp.next;
        }
        while (temp != head);
    }
}
 
// Driver Code
/* Initialize lists as empty */
let head = null;
 
/* Created linked list will
       be 11.2.56.12 */
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

// Java program
 
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);
  }
}
 
// This code is contributed by lokesh.

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#

// C# program for the above approach
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()
  {
 
    // Code
    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);
  }
}
 
// This code is contributed by lokeshmvs21.

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();
 
// This code is contributed by anskalyan3

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!

Traversal of Circular Linked List

C++

C

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Run Local AWS Cloud Stack using LocalStack on Linux

Learn Terraform Automation in 3 days using Video Courses

How To Expose Ansible AWX Service using Nginx Ingress

LEAVE A REPLY Cancel reply

Most Popular

Sticky Password vs. LastPass 2024: Which Is Better? by Katarina Glamoslija

Galaxy S25 on-device AI capability expands, reducing reliance on the cloud

OnePlus 13R launches with a huge battery upgrade, starting in China

This is my surprise phone of the year [Video]

Recent Comments

EDITOR PICKS

Sticky Password vs. LastPass 2024: Which Is Better? by Katarina Glamoslija

Galaxy S25 on-device AI capability expands, reducing reliance on the cloud

OnePlus 13R launches with a huge battery upgrade, starting in China

POPULAR POSTS

Sticky Password vs. LastPass 2024: Which Is Better? by Katarina Glamoslija

Galaxy S25 on-device AI capability expands, reducing reliance on the cloud

OnePlus 13R launches with a huge battery upgrade, starting in China

POPULAR CATEGORY

ABOUT US

FOLLOW US