The doubly linked list data structure is a set of nodes where each node contains three fields ‘data’ and two ‘reference’ field.

Doubly Linked List Data Structure

The doubly linked list data structure is one type of linked list where the doubly linked list means we are having a two reference field. The first reference stores address of previous node address and Second stores next node address.

Doubly Linked List
Doubly Linked List

A doubly linked list data structure is the most important data structure. A doubly linked list is a set of nodes which are connected to another node sequentially by the reference to its previous and next node.

Types of Doubly linked list

Like singly linked list Doubly Linked list is implemented in two ways which are as follows.

  1. Doubly Linked List
  2. Circular Doubly Linked List

Doubly linked list

The doubly linked list is a type of linked list where a node contains 3 field one contains data in the node and two pointers which store the address of previous and next node.

As node added we stored the previous and next address of a node.
At the initial stage that is there is only one node, the previous and next contains null after as we add node we store previous and next address in a node.
The last node of a linked list does not point to any node which contains its value NULL.

Representation for Doubly Linked list

Doubly Linked List Data structure
Doubly Linked List Data structure

The end of the doubly linked list does not store any address (which means it contains NULL) as shown in the above diagram.

The first node in a linked list is referred to as a Head Node. If the Linked list is empty then Head Node points to Null.
The node consists of three parts
1. Data: the value of the node
2. Previous Address: Reference to the previous node
3. Next Address: Reference to the next node

Last Node Points to NULL indicates its end (Non-circular).

How do you create a Doubly Linked list in Data structure?

1. Declaring the Linked List
The first step we need to define the node.
To implement a node we use a type of structure to form a node.
Struct node
{
int data;
Struct node * prev;
Struct node * next;
}
2. Creating Node
After that we create the node in linked list.
typedef struct Linkedlist *node;
node Createnode(){
node temp;
temp = (node)malloc(sizeof(struct Linkedlist));
temp->prev=NULL;
temp->next=NULL;
return temp;
}
3. Add Node to linked list
To add node to linked list is very important. For This we require to check different conditions
Condition 1: If Linked list is empty then add node to Linked list and assign head to First Node.
Condition 2: If Linked list is not empty (To add Node at end), then traverse the linked list till end and add node at end.

4. Traverse the node
The linked list can be traversed in a while loop by using the head node as a starting reference:
node p;
p = head;
while(p != NULL){
p = p->next;
}

Doubly linked list c program

#define pf printf
#define sf scanf
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
struct node *prev;
};
struct node *start;
void insert_beg(void);
void insert_end(void);
void insert_before(void);
void display(void);
void deleteion(void);
void destroy(void);

void main(void)
{
int ch;
start=NULL;
do{
pf("\n 1. insert_beg\n 2. insert_end\n 3. insert_before\n 4. Display\n 5. Deletion\n 6.Destroy\n 7.Exit \n Enter choice = ");
sf("%d",&ch);
switch(ch){
case 1:
insert_beg();
break;
case 2:
insert_end();
break;

case 3:
insert_before();
break;

case 4:
display();
break;

case 5:
deletion();
break;

case 6:
destroy();
break;

case 7:
break;

}
}while(ch!=7);

}
void insert_beg(void)
{
struct node *nn;
nn=(struct node *)malloc(sizeof(struct node));
pf("\n Enter data = ");
sf("%d",&nn->data);
if(start==NULL){
nn->next=NULL;
nn->prev=NULL;
start=nn;
}
else{
nn->prev=NULL;
nn->next=start;
start->prev=nn;
start=nn;
}
}
void insert_end(void)
{
struct node *nn ,*temp;
nn=(struct node *)malloc(sizeof(struct node));
pf(" Enter data = ");
sf("%d",&nn->data);
if(start==NULL){
nn->prev=NULL;
nn->next=NULL;
start=nn;
}
else{
temp=start;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=nn;
nn->next=NULL;
nn->prev=temp;

}
}
void insert_before(void)
{
struct node *nn ,*temp,*ptemp;
int x;

if(start==NULL){
pf("\n DLL is empty ------");
return;
}
pf("\n Enter data which you want to insert the node = ");
sf("%d",&x);
if(x==start->data){
insert_beg();
return;
}
temp=start;
while(temp!=NULL && temp->data!=x)
{
ptemp=temp;
temp=temp->next;
}
if(temp==NULL)
{
pf("\n %d does not exist:",x);
}
else{
nn=(struct node *)malloc(sizeof(struct node));
pf("\n Enter data = ");
sf("%d",&nn->data);
nn->prev=ptemp;
nn->next=temp;
ptemp->next=nn;
temp->prev=nn;
}
}
void display(void)
{
struct node *temp,*ptemp;
if(start==NULL)
{
pf("\n DLL is empty ----- ");
return;
}
pf("\n Forward order ");
temp=start;
while(temp!=NULL){
pf("| %d | %d | %d | -> ",ptemp,temp->data,temp);
ptemp=temp;
temp=temp->next;
}
pf("\n Reverse order ");
while(ptemp!=NULL){
pf("| %d | %d | %d | -> ",ptemp,ptemp->data,temp);
ptemp=ptemp->prev;
}

}
void deletion(void)
{
struct node *ptemp,*temp,*ntemp;
int x;
if(start==NULL)
{
pf("\n DLL is empty----");
return;
}
pf("\n Enter data to delete = ");
sf("%d",&x);
if(x==start->data)
{
temp=start;
start=start->next;
free(temp);
if(start!=NULL){
start->prev=NULL;
}
return;
}
temp=start;
while(temp!=NULL && temp ->data!=x)
{
ptemp=temp;
temp=temp->next;
}
if(temp==NULL)
{
pf("\n %d does not exist ");

}
else{
ptemp->next=temp->next;
if(temp->next!=NULL)
{
ntemp=temp->next;
ntemp->prev=ptemp;
}
free(temp);
}

}
void destroy(void)
{
struct node *temp,*dp;
if(start==NULL)
{
pf("\n DLL is empty -----");
return;
}
temp=start;
while(temp!=NULL)
{
dp=temp;
temp=temp->next;
free(dp);
}
start=NULL;
}
Output:

Doubly Linked List

Doubly Circular Linked List

The doubly linked list means we create a node with a 3 field which stores data and two address pointer as a previous and next node address.
Doubly circular state that our end node will point to start node and start node will point to the end node to form a circular linked list.
As its circular doubly linked list initially if we have one node then that node point to itself.

Doubly Circular Linked List
Doubly Circular Linked List

Each node stores its previous and next node address, As its circular doubly linked list last node point to first and first node point to last node.

Representation of Doubly Circular Linked List

Doubly Circular Linked List Data Structure
Doubly Circular Linked List Data Structure

We can see that the last node points to the first node to form a circular list.
Except connecting the last node with first node the implementation of Doubly Circular linked list is similar to the doubly linked list.

Doubly circular linked list program in c

#include<stdio.h>
#include<alloc.h>
struct node{
int data;
struct node *next;
struct node *prev;
}
struct node *start;
void insert_beg(void);
void insert_end(void);
void insert_before(void);
void display(void);
void deleteion(void);
void destroy(void);
#define pf printf
#de4fine sc scanf
void main(void)
{
int ch;
start=NULL;
do{
pf(“\n 1. insert_beg\n
2. insert_end\n
3. insert_before\n
4. Display\n
5. Deletion\n
6.Destroy
\n7.Exit”);
sf(“%d”,&ch);
switch(ch){
case 1:
insert_beg();
break;
case 2:
insert_end();
break;

case 3:
insert_before();
break;

case 4:
display();
break;

case 5:
deletion();
break;

case 6:
destroy();
break;

case 7:
exit(0);
break;

}
}while(ch!=7);

}
void insert_beg(void)
{
struct node *nn,*lp;
nn=(strcut node *)malloc(sizeof(struct node));
pf(“Enter data”);
sf(“%d”,&nn->data);
if(start==NULL){
nn->next=nn;
nn->prev=nn;
start=nn;
}
else{
lp=start->prev;
nn->prev=lp;
nn->next=start;
start->prev=nn;
lp->next=nn;
start=nn;
}
}
void insert_end(void)
{
struct node *nn ,*lp;
nn=(strcut node *)malloc(sizeof(struct node));
pf(“Enter data”);
sf(“%d”,&nn->data);
if(start==NULL){
nn->prev=nn;
nn->next=nn;
start=nn;
}
else{
lp=start->prev;
nn->next=start;
nn->prev=lp;
start->prev=nn;
lp->next=nn;

}
}
void insert_before(void)
{
struct node *nn ,*temp,*ptemp;
int x;

if(start==NULL){
pf(“DLL is empty”);
return;
}
pf(“Enter data which you want to insert the node”);
sf(“%d”,&x);
if(x==start->data){
insert_beg();
return;
}
temp=start;
while(temp!=NULL && temp->data!=x)
{
ptemp=temp;
temp=temp->next;
if(temp==start)
{
pf(“%d does not exist:”,x);
return;
}
}
nn=(strcut node *)malloc(sizeof(struct node));
pf(“Enter data”);
sf(“%d”,&nn->data);
nn->prev=ptemp;
nn->next=temp;
ptemp->next=nn;
temp->prev=nn;

}
void display(void)
{
struct node *temp*ptemp;
if(start==NULL)
{
pf(“\n DLL is empty”);
return;
}
pf(“Forward order”);
temp=start;
do{
pf(“%d”,temp->data);
temp=temp->next;
}while(temp!=start);
temp=start->prev;
pf(“reverse order”);
do{
pf(“%d”,temp->data);
temp=temp->prev;
}while(temp!=start->prev);

}
void deletion(void)
{
struct node *ptemp,*temp,*ntemp,*lp;
int x;
if(start==NULL)
{
pf(“\n DLL is empty”);
return;
}
pf(“Enter data to delete”);
sf(“%d”,&x);
if(x==start->data)
{
if(start==start->next){
temp=start;
start=null;
free(temp);
}
else{
temp=start;
lp=start->prev;
start=start->next;
free(temp);
start->prev=lp;
lp->next=start;
}
return;
}
temp=start;
while(temp ->data!=x)
{
ptemp=temp;
temp=temp->next;
if(temp==start)
{
pf(“%d does not exist”);
return;
}
}
ptemp->next=temp->next;
ntemp=temp->next;
ntemp->prev=ptemp;
free(temp);
}

}
void destroy(void)
{
struct node *temp,*dp;
if(start==NULL)
{
pf(“\n DLL is empty”);
return;
}
temp=start;
while(temp!=NULL)
{
dp=temp;
temp=temp->next;
free(dp);
}
start=NULL;
}
Output:

Doubly circular linked list

Advantages of Doubly Linked List

1. We can traverse in both directions i.e. from start to end and as well as the end to start.
2. Easy to reverse a linked list.

Disadvantages of Doubly Linked list

1. Requires extra space required to store the previous pointer.
2. Insertion and deletion take more time because more pointer operations are required.

Write A Comment