Circular Linked List Traversal

Problem Statement: Given a Circular Linked List, Write a program to print all elements of the List.

Example:
Input:


Result:
 2     4      6      8      10

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

Since it is a Circular Linked List , There is no last element which is pointing to NULL so The Normal Linked List Traversal Approach doesn’t work here.
In a Circular Linked List , The last element of the Linked List is pointing to it’s head so we can use that property to traverse all elements.
Set a Node* pointer ptr = head.
Now using a do-while loop traverse all the elements using pointer ptr until ptr == head.
Why do – while?

Before writing the loop we have set ptr = head . Incase we write a while or a for loop it will not run because these two loops checks the condition first and the execute.
Whereas , do-while loop executes the code and then checks the code in the first iteration which is what we need so we can mode ptr to head->next.

Dry Run:

After the code executed first time , while condition is not true here.

Here, The loop will terminate because ptr = head.

Code:

C++ Code

#include <iostream>

using namespace std;
class Node {
  public:
    int data;
  Node * next;
  Node(int val) {
    data = val;
    next = NULL;
  }

};

void InsertAtHead(Node * & head, int val) {
  Node * n = new Node(val);
  if (head == NULL) {
    n -> next = n;
    head = n;
    return;
  }
  Node * temp = head;
  while (temp -> next != head) {
    temp = temp -> next;
  }
  temp -> next = n;
  n -> next = head;
  head = n;
}

void InsertatTail(Node * & head, int val) {

  if (head == NULL) {
    InsertAtHead(head, val);
    return;
  }
  Node * n = new Node(val);
  Node * temp = head;
  while (temp -> next != head) {
    temp = temp -> next;
  }
  temp -> next = n;
  n -> next = head;
}

void Traverse(Node * head) {
  Node * ptr = head;
  do {
    cout << ptr -> data << "      ";
    ptr = ptr -> next;
  } while (ptr != head);
  cout << endl;
}

int main() {
  Node * head = NULL;
  InsertAtHead(head, 2);
  InsertatTail(head, 4);
  InsertatTail(head, 6);
  InsertatTail(head, 8);
  InsertatTail(head, 10);
  Traverse(head);

}

Output:

2 4 6 8 10

Time Complexity: O(N), where N is The Number of elements in a Linked List.

Reason: Iterating the entire list once.

Space Complexity: O(1) because no other data structure is used.

Java Code

import java.util.*;

class Node {
  
  int data;
  Node  next;
  Node(int val) {
    data = val;
    next = null;
 }
}
class TUF{
static Node InsertAtHead(Node head, int val) {
  Node  n = new Node(val);
  if (head == null) {
    n . next = n;
    head = n;
    return head;
  }
  Node  temp = head;
  while (temp . next != head) {
    temp = temp . next;
  }
  temp . next = n;
  n . next = head;
  head = n;
  return head;
}

static Node InsertatTail(Node head, int val) {

  if (head == null) {
    head = InsertAtHead(head, val);
    return head;
  }
  Node  n = new Node(val);
  Node  temp = head;
  while (temp . next != head) {
    temp = temp . next;
  }
  temp . next = n;
  n . next = head;
  return head;
}

static void Traverse(Node  head) {
  Node  ptr = head;
  do {
    System.out.print(ptr . data +"      ");
    ptr = ptr . next;
  } while (ptr != head);
 
}

public static void main(String args[]) {
  Node  head = null;
  head = InsertAtHead(head, 2);
  head = InsertatTail(head, 4);
  head = InsertatTail(head, 6);
  head = InsertatTail(head, 8);
  head = InsertatTail(head, 10);
  Traverse(head);

}
}

Output:

2 4 6 8 10

Time Complexity: O(N), where N is The Number of elements in a Linked List.

Reason: Iterating the entire list once.

Space Complexity: O(1) because no other data structure is used.

Special thanks to Gaur Sundar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article