Doubly-linked list is a more sophisticated form of linked list data structure. Each node of the list contain two references (or links) – one to the previous node and other to the next node. The previous link of the first node and the next link of the last node points to NULL. In comparison to singly-linked list, doubly-linked list requires handling of more pointers but less information is required as one can use the previous links to observe the preceding element. It has a dynamic size, which can be determined only at run time.
Example program to implement Doubly Linked List
#include <stdio.h>
#include <malloc.h>
struct node
{
struct node *prev;
int info;
struct node *next;
}*start;
main()
{
int choice,n,m,po,i;
start=NULL;
while(1)
{
printf("1.Create Listn");
printf("2.Add at beginingn");
printf("3.Add aftern");
printf("4.Deleten");
printf("5.Displayn");
printf("6.Countn");
printf("7.Reversen");
printf("8.exitn");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("How many nodes you want : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the element : ");
scanf("%d",&m);
create_list(m);
}
break;
case 2:
printf("Enter the element : ");
scanf("%d",&m);
addatbeg(m);
break;
case 3:
printf("Enter the element : ");
scanf("%d",&m);
printf("Enter the position after which this element is inserted : ");
scanf("%d",&po);
addafter(m,po);
break;
case 4:
printf("Enter the element for deletion : ");
scanf("%d",&m);
del(m);
break;
case 5:
display();
break;
case 6:
count();
break;
case 7:
rev();
break;
case 8:
exit();
default:
printf("Wrong choicen");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
create_list(int num)
{
struct node *q,*tmp;
tmp= malloc(sizeof(struct node));
tmp->info=num;
tmp->next=NULL;
if(start==NULL)
{
tmp->prev=NULL;
start->prev=tmp;
start=tmp;
}
else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=tmp;
tmp->prev=q;
}
}/*End of create_list()*/
addatbeg(int num)
{
struct node *tmp;
tmp=malloc(sizeof(struct node));
tmp->prev=NULL;
tmp->info=num;
tmp->next=start;
start->prev=tmp;
start=tmp;
}/*End of addatbeg()*/
addafter(int num,int c)
{
struct node *tmp,*q;
int i;
q=start;
for(i=0;i<c-1;i++)
{
q=q->next;
if(q==NULL)
{
printf("There are less than %d elementsn",c);
return;
}
}
tmp=malloc(sizeof(struct node) );
tmp->info=num;
q->next->prev=tmp;
tmp->next=q->next;
tmp->prev=q;
q->next=tmp;
}/*End of addafter() */
del(int num)
{
struct node *tmp,*q;
if(start->info==num)
{
tmp=start;
start=start->next; /*first element deleted*/
start->prev = NULL;
free(tmp);
return;
}
q=start;
while(q->next->next!=NULL)
{
if(q->next->info==num) /*Element deleted in between*/
{
tmp=q->next;
q->next=tmp->next;
tmp->next->prev=q;
free(tmp);
return;
}
q=q->next;
}
if(q->next->info==num) /*last element deleted*/
{ tmp=q->next;
free(tmp);
q->next=NULL;
return;
}
printf("Element %d not foundn",num);
}/*End of del()*/
display()
{
struct node *q;
if(start==NULL)
{
printf("List is emptyn");
return;
}
q=start;
printf("List is :n");
while(q!=NULL)
{
printf("%d ", q->info);
q=q->next;
}
printf("n");
}/*End of display() */
count()
{ struct node *q=start;
int cnt=0;
while(q!=NULL)
{
q=q->next;
cnt++;
}
printf("Number of elements are %dn",cnt);
}/*End of count()*/
rev()
{
struct node *p1,*p2;
p1=start;
p2=p1->next;
p1->next=NULL;
p1->prev=p2;
while(p2!=NULL)
{
p2->prev=p2->next;
p2->next=p1;
p1=p2;
p2=p2->prev; /*next of p2 changed to prev */
}
start=p1;
}/*End of rev()*/