Doubly Circular Linked List C/C++
Data Structures
Before learning Doubly Circular Linked list you must know about Doubly Linked List that it is a linear data structure that has two pointers *next and *prev pointing to the next and the previous node. so we can traverse the list in both directions forward as well as backward.
Note: Other important topics required to understand this one Linked List, Doubly Linked list, Circular Linked List.
In Circular Singly Linked List, the last node points to the first node instead of NULL value thus making it circular in structure. So we traverse the head or first node of list directly from the last node or tail.
But Circular Doubly Linked List is more flexible and dynamic from all of the above data structures.
In this data structure the last node contains the address of the head node and in return head node pointer *Prev also contains the address of the last node of the list.
So we can traverse the list in a forward direction backward and from tail to head directly, from head to tail directly no need to traverse the whole list.
It is the most flexible data structure we can access the last node directly e.g. temp=head->prev; it is easily done we don’t need to traverse the whole list till we reach the end, here we directly access the last node of the list.
It becomes double circular in nature we access the list from head to tail and from tail to head in circular form in the forward direction. Also, we can access the list backward like from tail to head and from the head back to the tail.
Why Circular
Circular Doubly Linked List can be used in Sorting and Searching and is used in other real-world applications. It is very time-efficient, it reduces the time complexity of accessing the nodes because we can traverse the list in
various ways.
//Doubly Circular Linked List
#include<iostream>
using namespace std;
struct node
{
node *prev;
int data;
node *next;
}*head;
void Insert(int n)
{
node *temp;
temp=new node;
temp->data=n;
temp->prev=NULL;
temp->next=NULL;
if(head==NULL)
{
head=temp;
head->next=temp;
head->prev=temp;
}
else
{
temp->next=head;
temp->prev=head->prev;
head->prev->next=temp;
head->prev=temp;
}
}
void Insert_Front(int n)
{
node *temp=new node;
temp->data=n;
temp->prev=NULL;
temp->next=NULL;
if(head==NULL)
{
Insert(n);
}
else
{
temp->prev=head->prev;
temp->next=head;
head->prev->next=temp;
head->prev=temp;
head=temp;
}
}
void Display()
{
node *ptr=new node;
ptr=head;
if(head!=NULL)
{
cout<<" Nodes in List are: ";
while(ptr->next!=head)
{
cout<<ptr->data<<" <--> ";
ptr=ptr->next;
}
cout<<ptr->data;
}
else
cout<<"Empty List: n";
}
int main()
{
head=NULL;
int choice;
while(1)
{
cout<<"nt Press 1 for Insert at Endn";
cout<<"t Press 2 for Displayn";
cout<<"t Press 3 for Insert at Frontn";
cout<<"t Press 4 to Exitn";
cout<<" Enter you Choice: n";
cin>>choice;
switch(choice)
{
case 1:
Insert(11);
Insert(22);
Insert(33);
break;
case 2:
Display();
break;
case 3:
Insert_Front(99);
Insert_Front(100);
break;
case 4:
exit(0);
default:
cout<<"Wrong Choicen";
}
}
return 0;
}Code language: PHP (php) Following are the programs and functions which we are going to use in this program.
1. First, define a Structure template or framework of the doubly linked list.
2. Create a Menu Driven main program and in proper switch cases call the required functions.
3. After the main() function, now provide the definition of functions e.g. insert at front, insert at the end, and display the nodes in forward and reverse order.
4. You can also add functions like deleting node at front and end, also searching the required node in the list.
You can also copy the source code of other related c/c++ programs