Traversal in a Circular Linked List in C++

In the following explanation, we will discuss how to traverse a Circular Linked List in C++.

What we know

We know how to traverse a linked list, we simply start from the head and traverse all way through the nodes till next of the current node is NULL.

Linked list

8, 1, 3, 2, 11

Approach

We will create a temp variable pointing to the head and will traverse the linked list using the temp variable and will stop when next of the current node is head.

Circular linked list traversal

55, 12, 24, 2, 4
  • Set TEMP = HEAD
  • If TEMP == NULL
    • NO ELEMENTS IN LIST
  • Else repeat next 2 steps UNTIL TEMP->NEXT != HEAD
  • Print TEMP->DATA
  • TEMP = TEMP->NEXT
  • [END LOOP]
  • PRINT TEMP->DATA
  • END

Full Implementation

#include<bits/stdc++.h>
using namespace std;

// Blueprint of Node
class Node{
    public:
        int data;
        Node *next;
};

// Function for inserting node in the
// Circular Linked List
void insert(Node **head, int value){
    Node *last = *head;
    Node *newNode = new Node;
    newNode->data = value;
    newNode->next = *head;
    if(*head != NULL){
        while(last->next != *head){
            last = last->next;
        }
        last->next = newNode;
    }else{
        newNode->next = newNode;       
    }
    *head = newNode;
}

// Traversing the Circular Linked List
// Printing elements
void print(Node *head){
    cout << "Elements in Circular Linked List:\n";
    Node *temp = head;
    // Checking if Linked List is empty
    if(head != NULL){
        // Looping till next of current node is not
        // pointing to the head
        do{
            cout << temp->data << " ";
            temp = temp->next;
        }while(temp != head);
    }else{
        // Empty Linked List
        cout << "No elements in linked List" << endl;
    }
}

int main(){
    Node *head = NULL;
    int elements;
    cout << "To stop adding elements enter -1\n";
    while(1){
        cin >> elements;
        if(elements >= 0){
            insert(&head, elements);
        }else{
            break;
        }
    }
    print(head);
    return 0;
}

Input/Output

To stop adding elements enter -1
55 12 24 2 4
-1
Elements in Circular Linked List:
4 2 24 12 55

Leave a Reply

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