Loading

C - Program for Doubly Linked List

C - Program for Implementation Doubly Linked List



/* Accept input as a string and construct a Doubly Linked List for the input
   string with each node contains, as a data one character from the string and
   perform :
   a) Insert b) delete c)Display forward d) Display backward
*/

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

typedef struct node
   { char data;
     struct node *next,*prev;
   }node;

node *create();
node *insert_b(node *head,char x);
node *insert_e(node *head,char x);
node *insert_in(node *head,char x);
node *delete_b(node *head);
node *delete_e(node *head);
node *delete_in(node *head);
void displayforward(node *head);
void displaybackward(node *head);
void main()
{ int op,op1;
  char x;
  node *head=NULL;
  clrscr();
  do
    { flushall();
      printf("\n\n1)create\n2)Insert\n3)Delete");
      printf("\n4)Display forward\n5)Display backward\n6)Quit");
      printf("\nEnter your Choice:");
      scanf("%d",&op);
      switch(op)
       { case 1:head=create();break;
     case 2:printf("\n\t1)Beginning\n\t2)End\n\t3)In between");
        printf("\nEnter your choice : ");
        scanf("%d",&op1);
        printf("\nEnter the data to be inserted : ");
        flushall();
        x=getchar();
        switch(op1)
         {  case 1: head=insert_b(head,x);
                break;
            case 2: head=insert_e(head,x);
                break;
            case 3: head=insert_in(head, x);
                break;
          }
        break;
     case 3:printf("\n\t1)Beginning\n\t2)End\n\t3)In between");
        printf("\nEnter your choice : ");
        scanf("%d",&op1);
        switch(op1)
         {  case 1:head=delete_b(head);
               break;
            case 2:head=delete_e(head);
               break;
            case 3:head=delete_in(head);
               break;
          }
         break;
     case 4:displayforward(head);break;
     case 5:displaybackward(head);break;
       }
    }while(op!=6);
}

node *create()
{ node *head,*p;
  char x;
  head=NULL;
  printf("\n Enter a string :");
  flushall();
  while((x=getchar())!='\n')
   {
     if(head==NULL)
    {
          head=p=(node*)malloc(sizeof(node));
          head->next=head->prev=NULL;
    }
     else
       {
          p->next=(node*)malloc(sizeof(node));
          p->next->prev=p;
          p=p->next;
          p->next=NULL;
       }
    p->data=x;
   }
 return(head);
}

node *insert_b(node *head,char  x)
{   node *p;
    p=(node*)malloc(sizeof(node));
    p->data=x;
   if(head==NULL)
    {
          head=p;
          head->next=head->prev=NULL;
    }
   else
       {
          p->next=head;
          head->prev=p;
          p->prev=NULL;
          head=p;
       }
   return(head);
}
node *insert_e(node *head,char  x)
{   node *p,*q;
    p=(node*)malloc(sizeof(node));
    p->data=x;
   if(head==NULL)
    {
          head=p;
          head->next=head->prev=NULL;
    }
   else
       {
          for(q=head; q->next != NULL ; q=q->next)
          ;
          q->next=p;
          p->prev=q;
          p->next=NULL;

       }
   return(head);
}


node *insert_in(node *head,char x)
{   node *p,*q;
    char  y;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    printf("\Insert after which character ? : ");
    flushall();
    y=getchar();
    //locate the lthe data 'y'
    for(q=head ; q != NULL && q->data != y; q=q->next)
    ;
    if(q->data==y)
      {
        p->next=q->next;
        p->prev=q;
        p->next->prev=p;
        p->prev->next=p;
      }
    else
       printf("\nData not found ");
    return(head);
}
node *delete_b(node *head)
{
  node *p,*q;
  if(head==NULL)
     {
      printf("\nUnderflow....Empty Linked List");
      return(head);
     }
  if(head->next==NULL)//delete the only node
    {
     p=head;
     free(p);
     head=NULL;
    }
  else
    {
     p=head;
     head=head->next;
     head->prev=NULL;
     free(p);
    }
  return(head);

}
node *delete_e(node *head)
{
  node *p;
  if(head==NULL)
     {
      printf("\nUnderflow....Empty Linked List");
      return(head);
     }
  if(head->next==NULL)//delete the only node
    {
      p=head;
      free(p);
      head=NULL;
    }
  else
    {
      for(p=head ; p->next != NULL ; p=p->next)
      ;
      p->prev->next=NULL;
      free(p);
    }
  return(head);

}

node *delete_in(node *head)
{
  node *p,*q;
  char x;
  if(head==NULL)
     {
    printf("\nUnderflow....Empty Linked List");
    return(head);
     }
  printf("\nEnter the data to be deleted : ");
  flushall();
  x=getchar();
  for(p=head ; p !=NULL && p->data != x ; p=p->next)
  ;

   if(p->data!=x)
     {
      printf("\nUnderflow.....data not found");
      return(head);
     }
 if(p==head)
  {
      head=head->next;
      if(head != NULL)
         head->prev=NULL;
      free(p);
  }
 else
  {
      p->prev->next=p->next;
      p->next->prev=p->prev;
      free(p);
   }
 return(head);
}

void displayforward(node *head)
{ node *p;
  printf("\n");
  if(head != NULL)
     {
     for(p=head ;p!=NULL ; p=p->next)
        printf("%c",p->data);
     }
}
void displaybackward(node *head)
{ node *p;
  printf("\n");
  if(head != NULL)
     {   // go to the last node
     for(p=head ;p->next!=NULL ; p=p->next)
     ;
     for( ;p!=NULL ; p=p->prev)
        printf("%c",p->data);
     }
}

Click Here to Download Source Code with Executable Program.


This entry was posted in . Bookmark the permalink.

Leave a reply