Pages

  • Home
  • About & Contact
  • Archive
  • C Programming Examples

27 July 2012

C Program to implement Doubly Linked List

Here is the simple Program to Implement Doubly Linked list [ DLL ] with Explanation in Detail

#include"stdio.h"
#include"alloc.h"
struct node
{
     struct node *prev;
     int data;
     struct node *next;
};
struct node *start;
void insertbeg(void)          // insert element at the beginning of DLL
{
     int a;
     struct node *nn;
     nn=(struct node *)malloc(sizeof(struct node));
     printf("enter data:");
     scanf("%d",&nn->data);
     a=nn->data;
     if(start==NULL)              //If Linked list is empty
     {
          nn->prev=nn->next=NULL;
          start=nn;
     }
     else
     {
          nn->next=start;
          nn->prev=NULL;
          start->prev=nn;
          start=nn;
     }
     printf("%d succ. inserted\n",a);
     return;
}
void insertend(void)          // insert element at the End of DLL
{
     int b;
     struct node *nn,*lp;
     nn=(struct node *)malloc(sizeof(struct node));
     printf("enter data:");
     scanf("%d",&nn->data);
     b=nn->data;
     if(start==NULL)
     {
          nn->prev=nn->next=NULL;
          start=nn;
     }
     else
     {
          lp=start;
          while(lp->next!=NULL)
          {
                    lp=lp->next;
          }
          nn->prev=lp;
          lp->next=nn;
          nn->next=NULL;
     }
     printf("%d succ. inserted\n",b);
     return;
}
void insertmid(void)        // insert element before the given element of DLL
{
     struct node *nn,*temp,*ptemp;int x,c;
     if(start==NULL)
     {
          printf("dll is empty\n"); return;
     }
     printf("enter data before which new node is to be insreted\n");
     scanf("%d",&x);
     if(x==start->data)
     {
          insertbeg();
          return;
     }
     ptemp=start;
     temp=start->next;
     while(temp!=NULL&&temp->data!=x)
     {
          ptemp=temp;
          temp=temp->next;
     }
     if(temp==NULL)
     {
          printf("%d data does not exist\n",x);
     }
     else
     {
          nn=(struct node *)malloc(sizeof(struct node));
          printf("enter data");
          scanf("%d",&nn->data);
          c=nn->data;
          nn->prev=ptemp;
          nn->next=temp;
          ptemp->next=nn;
          temp->prev=nn;
          printf("%d succ. inserted\n",c);
     }
     return;
}
void deletion(void)
{
     struct node *pt,*t,*nt;
     int x;
     if(start==NULL)
     {
          printf("dll is empty\n");
          return;
     }
     printf("enter data to be deleted");
     scanf("%d",&x);
     if(x==start->data)
     {
          t=start;
          start=start->next;
          free(t);
          printf("%d is succ. deleted\n",x);
          if(start!=NULL)
          {
               start->prev=NULL;
          }
          return;
     }
     pt=start;
     t=start->next;
     while(t!=NULL&&t->data!=x)
     {
          pt=t;
          t=t->next;
     }
     if(t==NULL)
     {
          printf("%d does not exist\n",x);return;
     }
     else
     {
          pt->next=t->next;
          if(t->next!=NULL)
          {
               nt=t->next;
               nt->prev=pt;
          }
          free(t);
     }
     printf("%d is succ. deleted\n",x);
     return;
}
void display(void)
{
     struct node *temp;
     if(start==NULL)
     {
          printf("dll is empty\n");
          return;
     }
     printf("displaying in forword order\n");
     temp=start;
     while(temp!=NULL)
     {
          printf("%d\n",temp->data);
          temp=temp->next;
     }
     return;
}
void main()
{
     int c,a;     start=NULL;
     do
     {
          printf("1:insert\n2:delete\n3:display\n4:exit\nenter choice:");
          scanf("%d",&c);
          switch(c)
          {
               case 1:
               printf("1:insertbeg\n2:insert end\n3:insert mid\nenter choice:");
               scanf("%d",&a);
               switch(a)
               {
                    case 1:insertbeg();break;
                    case 2:insertend();break;
                    case 3:insertmid();break;
               }
               break;
               case 2:deletion();break;
              case 3:display();break;
              case 4:printf("program ends\n");break;
              default:printf("wrong choice\n");
              break;
          }
     }while(c!=4) ;
}

Explanation:
Inserting the new node at the beginning of the Doubly linked list
Consider Inserting the new node at the beginning of the Doubly linked list.In the above image we are adding data 62 at the beginning of the list for this we insert address pointed by Start to next pointer and inserting NULL in prev pointer.Also we have to change the prev pointer pointed by start which contains NULL by the base address of new node.One thing left is change the address pointed by Start to the new node
Inserting element at the mid of the Doubly linked list

Consider Inserting element at the mid of the Doubly linked list.In the above image we are adding 99 before 56 for this we need two temporary pointers i.e temp and ptemp
ptemp is used for backtracking means it would contain the address previously pointed by temp for example when temp will contain the address of the node 56 at that time ptemp will contain address of the node 89.So while inserting new node before 56 temp will point node 56 and ptemp will point 89.New node's prev will contain the address pointed by ptemp and nn's next will contain the address pointed by temp.After that temp's next and ptemp's prev pointer will contain nn's address.
Inserting element at the end of the Doubly linked listConsider Inserting element at the end of the Doubly linked list.In the above image we are adding 29 At the end of list.We have to traversed the list until the next pointer is not NULL.So to insert new node i.e 29 we change the next from NULL to the address of new node and change the prev pointer of new node to address of last node.

DDeleting the element  which is at the beginning of the Doubly linked list Consider Deleting the element  which is at the beginning of the Doubly linked list.In the above image we are deleting 89.For deleting we have to just change the address contain by the next node's prev pointer to NULL and make start to point this next node.

Deleting the element  which is at the present in between of the Doubly linked list
 Consider Deleting the element  which is at the present in between of the Doubly linked list.In the above image we are deleting 56.For deleting we have to traverse just like inserting element before particular value using two temporary pointer's.In above case temp will point to 56 and ptemp to 89.So the address contain by temp->next is inserted into ptemp->next.temp->next->prev in above image it means node 29's prev address is change to address pointed by ptemp and then delete temp.


Deleting the element  which is at the end of the Doubly linked list
 Consider Deleting the element  which is at the end of the Doubly linked list.In the above image we are deleting 56.For deleting we have to traversed upto next pointer not equal to NULL.Change the temp->prev->next to NULL. Its over.

If you liked the post, please '+1' it & share it on other social networks.
Thank You
-Romil Shah

No comments:

Post a Comment