In this instructional exercise, you will find out about the doubly linked list in C and C++.
In an independently linked list, we can move/cross just one single way on the grounds that
every hub has the location of the following hub as it were. Assume we are in the linked list and we need the location of the past hub then we don’t have any alternative
other than rehashing the crossing from the earliest starting point hub.
To conquer this downside, a doubly linked list can be utilized. In this, there are two pointers.
One of these pointers focuses on the following hub and different focuses on the past hub.
The structure for a doubly-linked list hub can be proclaimed as:
struct node
{
struct node *prev_node;
int info;
struct node *next_node;
};prev_node would contain a pointer to the location of the past hub and next_node would
point the following hub in the list. Thus, we can move in both the headings.
Crossing
Traversal of a doubly linked list is like that of an independently linked list. We need to initially
check for a condition: regardless of whether the linked list is vacant or not. This sets the beginning pointer at a legitimate area.
After that, we get to every hub until the end.
Inclusion
Another hub can be embedded effectively in a doubly-linked list.
We simply need to set the pointers prev_node and next_node cautiously interlinking the
prev_node and the next_node hub with the suitable pointers.
In case you’re embeddings a Node n2 between Node n1 and n3, you should set the pointer prev_node of n2 to n1 and pointer next_node of n2 to n3.
Addition in a doubly-linked list should be possible in different manners:
- Inclusion in the middle of the hubs.
- Inclusion toward the start.
- Addition in an unfilled list.
- Addition toward the finish of the list.
Erasure
A hub can be erased effectively in a doubly-linked list. We simply need to set the pointers prev_node and next_node sensibly to the hubs.
Erasure of the hubs should be possible in the accompanying manners:
- Erase toward the end.
- Erase the main hub.
- Erase in the middle of the hubs.
Turn around a Doubly Linked List
Accept we have four hubs n1, n2, n3 and n4
Steps to invert
- Pointer start focuses on the last hub n4.
- Since the n4 is the main hub now, its prev_node pointer must be NULL.
- Hub n1 is the last hub, henceforth its next_node must be NULL.
- Pointer next_node of n4 focuses on n3, next_node of n3 focuses on n2 and next_node of n2 focuses on n1.
- Pointer prev_node of n1 focuses on n2, prev_node of n2 focuses on n3 and prev_node of n3 focuses on n4.
Program for Doubly Linked List in C
#include<stdlib.h>
#include<stdio.h>
struct node
{
struct node *prev_node;
int info;
struct node *next_node;
};
struct node *create_list(struct node *begin);
void display(struct node *begin);
struct node *addtoemptylist(struct node *begin,int data_element);
struct node *addatbeglist(struct node *begin,int data_element);
struct node *addatendlist(struct node *begin,int data_element);
struct node *addafterlist(struct node *begin,int data_element,int item_pos);
struct node *addbeforelist(struct node *begin,int data_element,int item_pos);
struct node *deletenode(struct node *begin,int data_element);
struct node *reverselist(struct node *begin);
main()
{
int option,data_element,item_pos;
struct node *begin=NULL;
while(1)
{
printf("\n1.Create A New Doubly Linked List\n");
printf("2.Display the Doubly Linked List\n");
printf("3.Add to an Empty Doubly Linked List\n");
printf("4.Add at Starting of the Doubly Linked List\n");
printf("5.Add at Ending\n");
printf("6.Add After a Node\n");
printf("7.Add Before a Node\n");
printf("8.Delete a Node\n");
printf("9.Reverse the Doubly Linked List\n");
printf("10.Exit\n");
printf("Enter your option : ");
scanf("%d",&option);
switch(option)
{
case 1:
begin=create_list(begin);
break;
case 2:
display(begin);
break;
case 3:
printf("Enter the element:");
scanf("%d",&data_element);
begin=addtoemptylist(begin,data_element);
break;
case 4:
printf("Enter the element:");
scanf("%d",&data_element);
begin=addatbeglist(begin,data_element);
break;
case 5:
printf("Enter the element:");
scanf("%d",&data_element);
begin=addatendlist(begin,data_element);
break;
case 6:
printf("Enter the element:");
scanf("%d",&data_element);
printf("Enter the element after which to insert : ");
scanf("%d",&item_pos);
begin=addafterlist(begin,data_element,item_pos);
break;
case 7:
printf("Enter the element: ");
scanf("%d",&data_element);
printf("Enter the element before which to insert : ");
scanf("%d",&item_pos);
begin=addbeforelist(begin,data_element,item_pos);
break;
case 8:
printf("Enter the element to be Deleted : ");
scanf("%d",&data_element);
begin=deletenode(begin,data_element);
break;
case 9:
begin=reverselist(begin);
break;
case 10:
exit(1);
default:
printf("Wrong option\n");
}
}
}
struct node *create_list(struct node *begin)
{
int i,n,data_element;
printf("Enter the number of nodes : ");
scanf("%d",&n);
begin=NULL;
if(n==0)
return begin;
printf("Enter the element: ");
scanf("%d",&data_element);
begin=addtoemptylist(begin,data_element);
for(i=2;i<=n;i++)
{
printf("Enter the element to be inserted : ");
scanf("%d",&data_element);
begin=addatendlist(begin,data_element);
}
return begin;
}
void display(struct node *begin)
{
struct node *p;
if(begin==NULL)
{
printf("List is empty\n");
return;
}
p=begin;
printf("List is :\n");
while(p!=NULL)
{
printf("%d ",p->info);
p=p->next_node;
}
printf("\n");
}
struct node *addtoemptylist(struct node *begin,int data_element)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=data_element;
temp->prev_node=NULL;
temp->next_node=NULL;
begin=temp;
return begin;
}
struct node *addatbeglist(struct node *begin,int data_element)
{
if(begin==NULL)
{
printf("List is empty\n");
return;
}
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->info=data_element;
temp->prev_node=NULL;
temp->next_node=begin;
begin->prev_node=temp;
begin=temp;
return begin;
}
struct node *addatendlist(struct node *begin,int data_element)
{
if(begin==NULL)
{
printf("List is empty\n");
return;
}
struct node *temp,*p;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=data_element;
p=begin;
while(p->next_node!=NULL)
p=p->next_node;
p->next_node=temp;
temp->next_node=NULL;
temp->prev_node=p;
return begin;
}
struct node *addafterlist(struct node *begin,int data_element,int item_pos)
{
struct node *temp,*p;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=data_element;
p=begin;
while(p!=NULL)
{
if(p->info==item_pos)
{
temp->prev_node=p;
temp->next_node=p->next_node;
if(p->next_node!=NULL)
p->next_node->prev_node=temp;
p->next_node=temp;
return begin;
}
p=p->next_node;
}
printf("%d not present in the list\n\n",item_pos);
return begin;
}
struct node *addbeforelist(struct node *begin,int data_element,int item_pos)
{
struct node *temp,*q;
if(begin==NULL )
{
printf("List is empty\n");
return begin;
}
if(begin->info==item_pos)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->info=data_element;
temp->prev_node=NULL;
temp->next_node=begin;
begin->prev_node=temp;
begin=temp;
return begin;
}
q=begin;
while(q!=NULL)
{
if(q->info==item_pos)
{
temp=(struct node *)malloc(sizeof(struct node));
temp->info=data_element;
temp->prev_node=q->prev_node;
temp->next_node = q;
q->prev_node->next_node=temp;
q->prev_node=temp;
return begin;
}
q=q->next_node;
}
printf("%d not present in the list\n",item_pos);
return begin;
}
struct node *deletenode(struct node *begin,int data_element)
{
struct node *temp;
if(begin==NULL)
{
printf("List is empty\n");
return begin;
}
if(begin->next_node==NULL)
if(begin->info==data_element)
{
temp=begin;
begin=NULL;
free(temp);
return begin;
}
else
{
printf("Element %d not found\n",data_element);
return begin;
}
if(begin->info==data_element)
{
temp=begin;
begin=begin->next_node;
begin->prev_node=NULL;
free(temp);
return begin;
}
temp=begin->next_node;
while(temp->next_node!=NULL )
{
if(temp->info==data_element)
{
temp->prev_node->next_node=temp->next_node;
temp->next_node->prev_node=temp->prev_node;
free(temp);
return begin;
}
temp=temp->next_node;
}
if(temp->info==data_element)
{
temp->prev_node->next_node=NULL;
free(temp);
return begin;
}
printf("Element %d not found\n",data_element);
return begin;
}
struct node *reverselist(struct node *begin)
{
if(begin==NULL)
{
printf("List is empty\n");
return begin;
}
struct node *p1,*p2;
p1=begin;
p2=p1->next_node;
p1->next_node=NULL;
p1->prev_node=p2;
while(p2!=NULL)
{
p2->prev_node=p2->next_node;
p2->next_node=p1;
p1=p2;
p2=p2->prev_node;
}
begin=p1;
printf("List reverselistd\n");
return begin;
}Program for Doubly Linked List in C++
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node
{
struct node *prev_node;
int info;
struct node *next_node;
};
struct node *create_list(struct node *begin);
void display(struct node *begin);
struct node *addtoemptylist(struct node *begin,int data_element);
struct node *addatbeglist(struct node *begin,int data_element);
struct node *addatendlist(struct node *begin,int data_element);
struct node *addafterlist(struct node *begin,int data_element,int item_pos);
struct node *addbeforelist(struct node *begin,int data_element,int item_pos);
struct node *deletenode(struct node *begin,int data_element);
struct node *reverselist(struct node *begin);
int main()
{
int option,data_element,item_pos;
struct node *begin=NULL;
while(1)
{
cout<<"\n1.Create A New Doubly Linked List\n";
cout<<"2.Display the Doubly Linked List\n";
cout<<"3.Add to an Empty Doubly Linked List\n";
cout<<"4.Add at Starting of the Doubly Linked List\n";
cout<<"5.Add at Ending\n";
cout<<"6.Add After a Node\n";
cout<<"7.Add Before a Node\n";
cout<<"8.Delete a Node\n";
cout<<"9.Reverse the Doubly Linked List\n";
cout<<"10.Exit\n";
cout<<"Enter your option : ";
cin>>option;
switch(option)
{
case 1:
begin=create_list(begin);
break;
case 2:
display(begin);
break;
case 3:
cout<<"Enter the element:";
cin>>data_element;
begin=addtoemptylist(begin,data_element);
break;
case 4:
cout<<"Enter the element:";
cin>>data_element;
begin=addatbeglist(begin,data_element);
break;
case 5:
cout<<"Enter the element:";
cin>>data_element;
begin=addatendlist(begin,data_element);
break;
case 6:
cout<<"Enter the element:";
cin>>data_element;
cout<<"Enter the element after which to insert : ";
cin>>item_pos;
begin=addafterlist(begin,data_element,item_pos);
break;
case 7:
cout<<"Enter the element: ";
cin>>data_element;
cout<<"Enter the element before which to insert : ";
cin>>item_pos;
begin=addbeforelist(begin,data_element,item_pos);
break;
case 8:
cout<<"Enter the element to be Deleted : ";
cin>>data_element;
begin=deletenode(begin,data_element);
break;
case 9:
begin=reverselist(begin);
break;
case 10:
exit(1);
default:
cout<<"Wrong option\n";
}
}
return 0;
}
struct node *create_list(struct node *begin)
{
int i,n,data_element;
cout<<"Enter the number of nodes : ";
cin>>n;
begin=NULL;
if(n==0)
return begin;
cout<<"Enter the element: ";
cin>>data_element;
begin=addtoemptylist(begin,data_element);
for(i=2;i<=n;i++)
{
cout<<"Enter the element to be inserted : ";
cin>>data_element;
begin=addatendlist(begin,data_element);
}
return begin;
}
void display(struct node *begin)
{
struct node *p;
if(begin==NULL)
{
cout<<"List is empty\n";
return;
}
p=begin;
cout<<"List is :\n";
while(p!=NULL)
{
cout<<p->info<<" ";
p=p->next_node;
}
cout<<"\n";
}
struct node *addtoemptylist(struct node *begin,int data_element)
{
struct node *temp;
temp=new struct node;
temp->info=data_element;
temp->prev_node=NULL;
temp->next_node=NULL;
begin=temp;
return begin;
}
struct node *addatbeglist(struct node *begin,int data_element)
{
if(begin==NULL)
{
cout<<"List is empty\n";
return begin;
}
struct node *temp;
temp = new struct node;
temp->info=data_element;
temp->prev_node=NULL;
temp->next_node=begin;
begin->prev_node=temp;
begin=temp;
return begin;
}
struct node *addatendlist(struct node *begin,int data_element)
{
if(begin==NULL)
{
cout<<"List is empty\n";
return begin;
}
struct node *temp,*p;
temp=new struct node;
temp->info=data_element;
p=begin;
while(p->next_node!=NULL)
p=p->next_node;
p->next_node=temp;
temp->next_node=NULL;
temp->prev_node=p;
return begin;
}
struct node *addafterlist(struct node *begin,int data_element,int item_pos)
{
struct node *temp,*p;
temp=new struct node;
temp->info=data_element;
p=begin;
while(p!=NULL)
{
if(p->info==item_pos)
{
temp->prev_node=p;
temp->next_node=p->next_node;
if(p->next_node!=NULL)
p->next_node->prev_node=temp;
p->next_node=temp;
return begin;
}
p=p->next_node;
}
cout<<item_pos<<" not present in the list\n\n";
return begin;
}
struct node *addbeforelist(struct node *begin,int data_element,int item_pos)
{
struct node *temp,*q;
if(begin==NULL )
{
cout<<"List is empty\n";
return begin;
}
if(begin->info==item_pos)
{
temp = new struct node;
temp->info=data_element;
temp->prev_node=NULL;
temp->next_node=begin;
begin->prev_node=temp;
begin=temp;
return begin;
}
q=begin;
while(q!=NULL)
{
if(q->info==item_pos)
{
temp=new struct node;
temp->info=data_element;
temp->prev_node=q->prev_node;
temp->next_node = q;
q->prev_node->next_node=temp;
q->prev_node=temp;
return begin;
}
q=q->next_node;
}
cout<<item_pos<<" not present in the list\n";
return begin;
}
struct node *deletenode(struct node *begin,int data_element)
{
struct node *temp;
if(begin==NULL)
{
cout<<"List is empty\n";
return begin;
}
if(begin->next_node==NULL)
if(begin->info==data_element)
{
temp=begin;
begin=NULL;
delete(temp);
return begin;
}
else
{
cout<<"Element "<<data_element<<" not found\n";
return begin;
}
if(begin->info==data_element)
{
temp=begin;
begin=begin->next_node;
begin->prev_node=NULL;
delete(temp);
return begin;
}
temp=begin->next_node;
while(temp->next_node!=NULL )
{
if(temp->info==data_element)
{
temp->prev_node->next_node=temp->next_node;
temp->next_node->prev_node=temp->prev_node;
delete(temp);
return begin;
}
temp=temp->next_node;
}
if(temp->info==data_element)
{
temp->prev_node->next_node=NULL;
delete(temp);
return begin;
}
cout<<"Element "<<data_element<<" not found\n";
return begin;
}
struct node *reverselist(struct node *begin)
{
if(begin==NULL)
{
cout<<"List is empty\n";
return begin;
}
struct node *p1,*p2;
p1=begin;
p2=p1->next_node;
p1->next_node=NULL;
p1->prev_node=p2;
while(p2!=NULL)
{
p2->prev_node=p2->next_node;
p2->next_node=p1;
p1=p2;
p2=p2->prev_node;
}
begin=p1;
cout<<"List reverselistd\n";
return begin;
}Output
On the off chance that you have any questions with respect to the above doubly linked list
in Cand C++ instructional exercise at that point remark underneath.