In this tutorial you will learn about doubly linked list in C and C++.
In singly linked list, we can move/traverse only in one single direction because each node has the address of the next node only. Suppose we are in the middle of the linked list and we want the address of previous node then we don’t have any option other than repeating the traversing from the beginning node.
To overcome this drawback, a doubly linked list can be used. In this, there are two pointers. One of these pointers points to the next node and the other points to the previous node.
The structure for a doubly linked list node can be declared as:
struct node
{
struct node *prev_node;
int info;
struct node *next_node;
};
prev_node would contain a pointer to the address of the previous node and next_node would point the next node in the list. Hence, we can move in both the directions.
Traversing
Traversal of a doubly linked list is similar to that of a singly linked list. We have to first check for a condition: whether the linked list is empty or not. This helps to set the start pointer at a proper location. After that we access each node till end.
Insertion
A new node can be inserted very easily in a doubly linked list. We just need to set the pointers prev_node and next_node carefully interlinking the prev_node and the next_node node with the appropriate pointers.
If you’re inserting 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.
Insertion in a doubly linked list can be done in multiple ways:
1. Insertion in between the nodes.
2. Insertion at the beginning.
3. Insertion in an empty list.
4. Insertion at the end of the list.
Deletion
A node can be deleted very easily in a doubly linked list. We just need to set the pointers prev_node and next_node logically to the nodes.
Deletion of the nodes can be done in the following ways:
1. Delete at the end.
2. Delete the first node.
3. Delete in between the nodes.
Reverse a Doubly Linked List
Assume we have four nodes n1, n2, n3 and n4
Steps to reverse
1. Pointer begin points to the last node n4.
2. Since, the n4 is the first node now, its prev_node pointer must be NULL.
3. Node n1 is the last node, hence its next_node must be NULL.
4. Pointer next_node of n4 points to n3, next_node of n3 points to n2 and next_node of n2 points to n1.
5. Pointer prev_node of n1 points to n2, prev_node of n2 points to n3 and prev_node of n3 points to 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
If you have any doubts regarding above doubly linked list in C and C++ tutorial then comment below.
ugghhhh the flashbacks to freshman year of college are real!
plz give me doubly linked list using class in c++
teaching is not to showing your looong, show your lessss