Circular Linked List C/C++ Data Structures

Published by Lonz on

Circular Linked List in C/C++
or
Simple Circular Linked List in C/C++

Circular Linked list is simply a singly Linked List in which the link field of the last node contains the address of the first node of the list.  Before learning this you must have a good hold on a single linked list.

circular linked list

In Circular Linked list the link field of the last node does not point to NULL, rather it points back to the first node or head of the list, thus making it hypothetically circular in structure.

Therefore, it has no end so we must establish the First and Last nodes of this list, in order to access all the nodes.

For simplicity, we can assign only the Tail pointer to access the whole list because of the last node or tail is not set to null it points to the first node, so we access the first node just like Tail->next is head done.


Why we use a circular linked list?


1. The Nodes are accessed easily because we can traverse the list from the tail to back to the list.
2. And the Deletion is also easy, by traversing from head to tail and from tail to head back.
3. It is Best for Searching and Sorting Algorithms because it is time sufficient.


Operations on Circular Linked List.
All the operations that are possible for the simple linked list are also applicable to the circular linked lists. We can use operations Like, Insert at the end, insert at front, insert in between, delete front, delete at the end, delete at the middle, etc.

1. Insert at End:
First Create a new node like Node *temp=new node and assign data temp->data=n, temp->next=NULL;


1. If(Tail==NULL); Now if it is the first node then,
a. put temp->next=temp like temp is pointing to temp thus making it circular because the last node of the list is pointing to the first node.
b. After assigning put temp in the tail like Tail=temp, because there is only one node so it is tail.


2. Else, if there are nodes inserted already, the tail is not now null.
a. Temp->Next=Tail->Next; Recall we are inserting at the end, so temp is going to end, and what ends points it points the first node, tail->next is the first node.


 b. Tail->Next=Temp; what tail is for it points the last now the temp is going the last node, so the tail is now temp.
c. Tail=Temp; Now temp is the new tail in the list.

insert node to circular linked list

2. Insert at Front or Add at Begin:
First, create a new node temp with data n and link with NULL the same as above.


a. If(tail==NULL), that means there is no node.
so tail=temp, tail->next=tail.
b. Else, there are some nodes either 1, 2 or much more.


1. Temp->Next=Tail->Next; Now look here tail-next is actually the first node,   so we are pointing head to the new node.
because we are inserting at the front, thus temp is going to be the first node.
 2. Tail->Next=Temp; Now tail is pointing to the temp making it new head.

3. Display();
Now display or traverse in a circular linked list is different from the simple   linked list because in this list we must terminate it otherwise it will go in an infinite loop.

1. Make a temporary pointer Node *front and assign it to the first node like front=tail->next.
2. First check if(tail==NULL) then cout empty list;
3. start a while loop While(front!=tail) that means traverse till tail is visited.
4. Inside loop display the data like cout<data;
5. Now all nodes are visited except the tail, now outside the loop set condition if(front=tail) then simply display it and all the nodes are now printed.

4. Delete at Front;
Create a node pointer *temp;
1. Check if the list is empty like If(tail==NULL) then simply print cout<<“List Empty”; and Return;
Also if there is only one node, if(tail==tail->next) then set tail==Null.


2. Else, Since we are deleting the head, so first put the head in temp as temp=tail->next;
a. now we need to assign new head node to tail, i.e, tail->next=temp->next
b. Delete temp and Return now all is done;

Download the Full Circular linked list code below

#include<iostream>
 using namespace std;
 struct Node
 {
 	int data;
 	Node *next;
 }*tail;
 
class Circular_LinkedList
 {
 	public:
 		void Insert_at_Front(int n);
 		void Insert_at_End(int n);
 		void Delete_at_Front();
 		void Display();
 	};
 
 int main()
 {
 	int choice;
	 Circular_LinkedList object;
 	tail=NULL;
  while(1)
  {	
  	cout<<"\n\t Press 1 for Insert at Front\n";
  	cout<<"\t Press 2 for Insert at End\n";
  	cout<<"\t Press 3 for Delete at Front\n";
  	cout<<"\t Press 4 for Display Nodes\n";
  	cout<<"\t Press 5 to Exit\n";
  	cout<<" Enter you Choice: \n";
  	cin>>choice;
  	 switch(choice)
  	 {
  	 	case 1:
  	 		object.Insert_at_Front(3);//Passing values
  	 		object.Insert_at_Front(2);
  	 		object.Insert_at_Front(1);
  	 		break;
  	 	case 2:
  	 		object.Insert_at_End(4);
  	 		object.Insert_at_End(5);
  	 		break;
  	 	case 3:
  	 		object.Delete_at_Front();
  	 		break;
  	 	case 4:
  	 		object.Display();
  	 		break;
  	 	case 5:
  	 		exit(0);
  	 	default:
  	 		cout<<"Wrong Choice\n";
	   }
  }
  return 0;
 }
 
 void Circular_LinkedList::Insert_at_Front(int n)
 {
 	Node *temp;
 	temp=new Node;
 	temp->data=n;
 	temp->next=NULL;
  if(tail==NULL)
  {
  	tail=temp;
  	tail->next=tail;
  }
  else
   {
   	temp->next=tail->next;
   	tail->next=temp;
   }
 }
 
 void Circular_LinkedList::Insert_at_End(int n)
  {
  	Node *temp;
 	temp=new Node;
 	temp->data=n;
 	temp->next=NULL;
  if(tail==NULL)
  {
  	temp->next=temp;
  	tail=temp;
  }
  else
   {
   	temp->next=tail->next;
   	tail->next=temp;
   	tail=temp;
   }
  }
  
 void Circular_LinkedList::Display()
  {
  	Node *front;
  	front=tail->next;
  	 if(tail==NULL)
  	  {
  	  	cout<<"Empty List: \n";
  	  }
  	cout<<"\tNodes are:\t";
  	while(front!=tail)
  	{
  		cout<<front->data<<" --> ";
  		front=front->next;
	  }
	  if(front==tail)
	  {
	  	cout<<front->data;
	  }
	  delete front;
	  cout<<endl;
  }
  
  void Circular_LinkedList::Delete_at_Front()
  {
  	Node *temp=new Node;
  	temp=tail->next;
  	if(tail==NULL)
  	 {
	   cout<<"Empty List\n";
	   return;
	 }
  	if(temp==tail)
  	{
  		delete temp;

	  }
	  else
	  {
	  	tail->next=temp->next;
	  	delete temp;
	  }
  }

0 Comments

Leave a Reply

%d bloggers like this: