Search This Blog

Loading...

Operations on Doubly Linked List

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

typedef struct  dnode
 {
       int  data;
       struct dnode *next,*prev;

  }dnode;

dnode * create()
  {
    int x,n,i;
    dnode *head=NULL;
    dnode *p;
    printf("\n Enter no of data : ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
       {
        printf("\n Next Data : ");
        scanf("%d",&x);
        if(head==NULL) // inserting the first node
             {
               head=p=(dnode *) malloc(sizeof(dnode));
               p->next=p->prev=NULL;
               p->data=x;
             }
        else
             {
            p->next=(dnode *) malloc(sizeof(dnode));
            p->next->data=x;
            p->next->prev=p;
            p=p->next;
            p->next=NULL;
            }
       }

  return(head);
  }

void print(dnode *head)
 {
    dnode *p;
    printf("\n Data stored in the Doubly linked list : ");
    for(p=head; p!=NULL ; p=p->next)
        printf("%d   ",p->data);
 }

 int search(dnode *head,int x)
 {
    int i=0;
    dnode *p;
    for(p=head; p!=NULL ; p=p->next)
       {
        if(p->data == x)
            return(i);
        i++;
       }
    return -1;
 }

 dnode *insert(dnode *head,int x,int loc)
 {
    dnode *p,*q;
    int i;
    p=(dnode*)malloc(sizeof(dnode));
    p->data=x;
    p->next=p->prev=NULL;
    if(loc==1) // inserting as a first node
       {
        p->next=head;
        head->prev=p;
        head=p;
       }
    else
       {
        q=head;
        for(i=1; i<loc-1;i++)
            if(q->next!=NULL)
                q=q->next;
            else
               {
                printf("\nOverflow **** ");
                return head;
               }
     //insert a node as next node of q
        p->next=q->next;
        p->prev=q;
        q->next=p;
        q->next->prev=q;
       }
 return(head);
 }

 dnode *Delete(dnode *head,int loc)
 {
    dnode *p,*q;
    int i;
    if(loc==1) //Deleting the first node
       {
        p=head;
        head=head->next;
        head->prev=NULL;
        free(p);
       }
    else
       {
        q=head;
        for(i=1;i<loc;i++) //postion q on the node to be deleted
           {
            if(q->next==NULL)
               {
                printf("\n Undeflow *****");
                return(head);
               }
            else
                q=q->next;
            }
        if(q->next != NULL)
            q->next->prev=q->prev;
        q->prev->next=q->next;
        free(q);
       }
 return(head);
 }

void main()
 {
    int op,x,loc;
    dnode *head=NULL;
    clrscr();
    do
      {
        printf("\n\n1)Create\n2)Print\n3)Insert\n4)Delete\n5)Search");
        printf("\n6)Quit");
        printf("\nEnter your Choice : ");
        scanf("%d",&op);
        switch(op)
          {
            case 1: head=create();break;
            case 2: print(head);break;
            case 3: printf("Enter the location :");
                scanf("%d",&loc);
                printf("Enter the data  :");
                scanf("%d",&x);
                head=insert(head,x,loc);break;
            case 4: printf("Enter the location :");
                scanf("%d",&loc);
                head=Delete(head,loc);break;
            case 5: printf("Enter element to be searched : ");
                scanf("%d",&x);
                loc=search(head,x);
                if(loc==-1)
                    printf("\n Element not found ");
                else
                    printf("\n Found at location :%d ",loc+1);
                break;
        }
    }while(op!=6);
   }

No comments:

Post a Comment