Introduction to Circular Linked List
Circular linked list can be defined as the list with no end node. If we make the next
pointer of last node in a linked list to point to the head node of the list instead of
NULL, it becomes circular linked list. A circular linked list can be a singly circular
linked list or doubly circular linked list.
In this type of list, we can start from any node to traverse the whole list and stop as
soon as any node visited twice. Also this type of list are helpful in implementing
circular queue. Sometimes when we need to loop through some objects 1-by-1, then
also we can use this type of list.
We can traverse the circular list as below: -
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct Node{
int data;
struct Node *next;
};
// Insert in Beginning
void insertBeg(Node** head, int data){
Node* node = new Node();
Node* t = *head;
node->data = data; // Insert data in new node
node->next = *head; // link new node at beginning of list
if (*head != NULL){
while(t->next != *head)
t = t->next;
t->next = node;
}
else
node->next = node;
*head = node; // Change the head to new node.
}
void printList(Node *first){
Node *temp = first;
if (first != NULL){
// Keep printing nodes till we reach the first node again
do{
cout<< temp->data<<" ";
temp = temp->next;
}while (temp != first);
}
cout<<endl;
}
int main(){
Node* head = NULL;
insertBeg(&head, 6);
insertBeg(&head, 2);
insertBeg(&head, 4);
insertBeg(&head, 8);
insertBeg(&head, 5);
insertBeg(&head, 3);
cout<<"Linked List = ";
printList(head);
return 0;
}
OUTPUT:
Linked List = 3 5 8 4 2 6
Counting the number of nodes in a circular linked list
It will also need to remember the node which we see twice to stop counting. The
following function will return the number of elements in circular linked list: -
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct Node{
int data;
struct Node *next;
};
// Insert in Beginning
void insertBeg(Node** head, int data){
Node* node = new Node();
Node* t = *head;
node->data = data; // Insert data in new node
node->next = *head; // link new node at beginning of list
if (*head != NULL){
while(t->next != *head)
t = t->next;
t->next = node;
}
else
node->next = node;
*head = node; // Change the head to new node.
}
void printList(Node *first){
Node *temp = first;
if (first != NULL){
// Keep printing nodes till we reach the first node again
do{
cout<< temp->data<<" ";
temp = temp->next;
}while (temp != first);
}
cout<<endl;
}
int length(Node* head){
int length = 0;
if(head == NULL)
return 0;
Node* temp = head->next;
while(temp != head){
temp = temp->next;
length++;
}
return length+1;
}
int main(){
Node* head = NULL;
insertBeg(&head, 6);
insertBeg(&head, 2);
insertBeg(&head, 4);
insertBeg(&head, 8);
insertBeg(&head, 5);
insertBeg(&head, 3);
cout<<"Linked List = ";
printList(head);
cout<<"The number of nodes in Circular Linked List = ";
cout<<length(head)<<endl;
return 0;
}
OUTPUT:
Linked List = 3 5 8 4 2 6
The number of nodes in Circular Linked List = 6
