Doubly Linked List
Program to create a doubly linked list with the possible operations that can be done is given below:
/*Program to create a doubly linked list along with various operations that can be performed on it.*/
/*Doubly Linked List*/
#include
#include
#include
typedef struct dlist
{
int info;
struct dlist *prev;
struct dlist *next;
}dlist;
/*creation*/
dlist *create();
dlist *makenode(int);
/*Insert a node at the end*/
dlist *insertend(dlist *,int);
/*Insert a node after a given node*/
dlist *insaftelement(dlist *,int,int);
/*Insert a node before a given node*/
dlist *insbefelement(dlist *,int,int);
/*delete the given node*/
dlist *delelement(dlist *,int);
/*delete node after a given node*/
dlist *delafternode(dlist *,int);
/*delete node before a given node*/
dlist *delbeforenode(dlist *,int);
/*In-order traversal*/
void displaylr(dlist *);
/*Reversal traversal*/
void displayrl(dlist *);
/*searching a given node*/
int search(dlist *,int);
/*disposing list*/
dlist *dispose(dlist *);
void main()
{
dlist *head=NULL;
int x,ch,val;
while(1)
{clrscr();
printf(“ntMenu(Doubly Linked List)”);
printf(“nt1. Create”);
printf(“nt2. Display L to R”);
printf(“nt3. Display R to L”);
printf(“nt4. Insert after element”);
printf(“nt5. Insert before element”);
printf(“nt6. Delete given node”);
printf(“nt7. Delete after given node”);
printf(“nt8. Delete before given node”);
printf(“nt9. Dispose list”);
printf(“nt10. Exit”);
printf(“ntEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“ntEnter number?”);
scanf(“%d”,&x);
head=insertend(head,x);
break;
case 2:
displaylr(head);
getch();
break;
case 3:
displayrl(head);
getch();
break;
case 4:
printf(“ntEnter number?”);
scanf(“%d”,&x);
printf(“ntEnter no. after which to insert?”);
scanf(“%d”,&val);
head=insaftelement(head,val,x);
break;
case 5:
printf(“ntEnter number?”);
scanf(“%d”,&x);
printf(“ntEnter no. before which to insert?”);
scanf(“%d”,&val);
head=insbefelement(head,val,x);
break;
case 6:
printf(“nEnter node to delete?”);
scanf(“%d”,&x);
head=delelement(head,x);
break;
case 7:
printf(“nEnter node after which to delete?”);
scanf(“%d”,&x);
head=delafternode(head,x);
break;
case 8:
printf(“nEnter node before which to delete?”);
scanf(“%d”,&x);
head=delbeforenode(head,x);
break;
case 9:
printf(“nDisposing list. “);
printf(“Press any key to continue…!”);
getch();
head=dispose(head);
break;
case 10:
exit(0);
default:
printf(“ntInvalid Choice.”);
}
getch();
}
}
dlist *create()
{
dlist *ptr=(dlist *)malloc(sizeof(dlist));
if(ptr==NULL)
{printf(“Memory allocation error!”);
exit(1);
}
return ptr;
}
dlist *makenode(int x)
{
dlist *ptr=create();
ptr->info = x;
ptr->prev=NULL;
ptr->next=NULL;
return ptr;
}
dlist *insertend(dlist *head,int x)
{
dlist *temp,*ptr=makenode(x);
if(head==NULL)
head=ptr;
else
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next = ptr;
ptr->prev = temp;
}
return head;
}
void displaylr(dlist *head)
{
dlist *temp;
if(head==NULL)
{printf(“List is empty.”);
}
else
{
temp=head;
while(temp!=NULL)
{printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}
}
void displayrl(dlist *head)
{
dlist *temp;
if(head==NULL)
{printf(“List is empty.”);
}
else
{
for(temp=head;temp->next!=NULL;temp=temp->next);
while(temp!=head)
{
printf(“%d->”,temp->info);
temp=temp->prev;
}
printf(“%d->”,temp->info);
}
printf(“bb “);
}
dlist *delelement(dlist *head,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,x);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
if(head==NULL)
printf(“nList is empty.”);
else
{temp=head;
while(temp->next->info!=x)
temp=temp->next;
ptr=temp->next;
temp->next=temp->next->next;
if(temp->next!=NULL)
temp->next->prev=ptr->prev;
free(ptr);
}
return head;
}
/*delete node after a given node*/
dlist *delafternode(dlist *head,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,x);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->next==NULL)
{printf(“nCannot delete. Only one node exists.”);
getch();
return head;
}
temp=head;
/*position temp at node after which to delete*/
while(temp->info!=x)
temp=temp->next;
ptr=temp->next;
temp->next=temp->next->next;
if(temp->next!=NULL)
temp->next->prev=ptr->prev;
free(ptr);
return head;
}
/*delete node before a given node*/
dlist *delbeforenode(dlist *head,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,x);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
if(head==NULL)
{printf(“nList is empty.”);
return head;
}
if(head->next==NULL)
{printf(“nCannot delete. Only one node exists.”);
return head;
}
temp=head;
/*position temp at node before which to delete*/
while(temp->info!=x)
temp=temp->next;
ptr=temp->prev;
if(ptr->prev!=NULL)
{ptr->prev->next=temp;
temp->prev=ptr->prev;
}
else
{temp->prev=NULL;
head=temp;
}
free(ptr);
return head;
}
int search(dlist *head,int x)
{
dlist *temp;
temp=head;
while(temp!=NULL)
{
if(temp->info==x)
return 1;
temp=temp->next;
}
return 0;
}
/*Insert a node after given node*/
dlist *insaftelement(dlist *head,int val,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,val);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
ptr=makenode(x);
temp=head;
while(temp->info!=val)
temp=temp->next;
ptr->next=temp->next;
ptr->prev=temp;
temp->next=ptr;
if(ptr->next!=NULL)
ptr->next->prev=ptr;
return head;
}
/*Insert a node before a given node*/
dlist *insbefelement(dlist *head,int val,int x)
{
dlist *temp,*ptr;
int ans;
ans=search(head,val);
if(ans==0)
{printf(“nNumber does not exist.”);
return head;
}
ptr=makenode(x);
if(head->info==val)
{
ptr->next=head;
head->prev=ptr;
head=ptr;
return head;
}
temp=head;
/*position temp on the node
before which to insert*/
while(temp->info!=val)
temp=temp->next;
ptr->next=temp;
ptr->prev=temp->prev;
temp->prev=ptr;
if(ptr->prev!=NULL)
ptr->prev->next=ptr;
return head;
}
/*disposing list*/
dlist *dispose(dlist *head)
{
dlist *temp;
while(head!=NULL)
{temp=head;
head=head->next;
free(temp);
}
return head;
}