Circular Linked List Traversal

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a circular linked list. We have to traverse the list and print its elements.

Problem Statement Understanding

Let’s try to understand the problem with help of example.

Suppose the given circular linked list is:

Now, we have to traverse this list. So, the output after traversing the list and printing every element will be: 1 7 18 15

Input :

Output: 1 7 18 15

Explanation: We will traverse the given list and while traversing we will print its elements which is the output.

Helpful Observations

This question is not a very complex one.

Let us first think about how we will traverse the circular linked list.

  • As we already know, there is no NULL node in a circular linked list and hence, no endpoint. The last node of the list points back to the first node of the list.
  • So, how can we do a successful traversal of the circular linked list?
    We can counter this by considering any node as the starting point. This is possible because, after a complete traversal, we will reach the starting node again. So, we can use any node as the starting point.

Let us have a glance at the approach.

Approach

Which node should we choose as our starting node?

  • The head node will make our life easier as we already have a pointer to the head of the list.

Create a node temp and make it point to the head. Now, keep incrementing temp while temp is not equal to the head of the list. In every iteration, print the temp’s data.

As explained already, we are using the head as our starting node, and terminating the loop when we are reaching the head again.

Algorithm

  • If the head is NULL, simply return because the list is empty.
  • Create a node temp and make it point to the head of the list.
  • Now, with the help of a do-while loop, keep printing the temp – > data and increment the temp, while temp is not equal to the head of the list.
  • As we have chosen the head as our starting point, we are terminating the loop when we are reaching the head again.

Dry Run

Code Implementation


#include <stdio.h>
#include<stdbool.h>
#include<stdlib.h>
 
struct Node {
    int data;
    struct Node* prev;
    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(void)
{
    struct Node *head = NULL;
    push(&head, 15);
    push(&head, 18);
    push(&head, 7);
    push(&head, 1);
 
    printf( "Contents of Circular Linked List\n ");
    printList(head);
}

#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, 15);
    push(&head, 18);
    push(&head, 7);
    push(&head, 1);
 
    cout << "Contents of Circular Linked List\n ";
    printList(head);
 
    return 0;
}

public class PrepBytes
{
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, 15);
    head = push(head, 18);
    head = push(head, 7);
    head = push(head, 1);
 
    System.out.println("Contents of Circular " +
                                "Linked List:");
    printList(head);
}
}
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(15)
cllist.push(18)
cllist.push(7)
cllist.push(1)

print ("Contents of circular Linked List")
cllist.printList()

Output

Contents of Circular Linked List:
1 7 18 15

Time Complexity: O(n), since we are traversing the linked list once.
[forminator_quiz id=”4102″]

So, in this article, we have tried to explain the most efficient approach to traverse a circular linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Leave a Reply

Your email address will not be published. Required fields are marked *