Traversal of Circular Linked List

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.

C++

C

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Contact Us