#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct Dnode
{
        int data;
        struct Dnode* next;
        struct Dnode* prev;
}Dnode;

Dnode* create(int);
void print(Dnode*);
int count(Dnode*);
Dnode* insertB(Dnode*,int);
Dnode* insertM(Dnode*,int);
Dnode* insertE(Dnode*,int);
Dnode* del(Dnode*);
void main()
{
    Dnode *HEAD;
    int n,number,ch,value;
    clrscr();
    printf("\n Enter no. of Item");
    scanf("%d",&n);

    HEAD=create(n);

    do
    {
        printf("\n 1.Insert at Begining \n 2.Insert after a specified value \n 3.Insert at End \n 4.DELETE \n 5.Display \n 6.Count \n 7.Exit \n");
        printf("Enter your choice \n");
        scanf("%d",&ch);

        switch(ch)
        {
            case 1:
                printf("Enter the value to be inserted");
                scanf("%d",&value);
                HEAD = insertB(HEAD,value);
            break;
            case 2:
                  printf("Enter the value to be inserted");
                  scanf("%d",&value);
                  HEAD = insertM(HEAD,value);
            break;
            case 3:
                  printf("Enter the value to be inserted");
                  scanf("%d",&value);
                  HEAD = insertE(HEAD,value);
            break;
            case 4:
                HEAD=del(HEAD);
                break;
            case 5:
                print(HEAD);
            break;
            case 6:
                number = count(HEAD);
                printf("Number of Nodes = %d",number);
            break;
            case 7:
                printf("Exit");
            break;
            default:
            printf("Invalid input \n");

        }



    }
    while(ch!=7);
    getch();
}

Dnode* create(int n)
{
    Dnode *head,*P,*Q;

    int i;

    head=(Dnode*)malloc(sizeof(Dnode));
    head->next=NULL;
    printf("Enter your Data \n");
    scanf("%d",(&head->data));

    P=head;

    for(i=1;i<n;i++)
    {
        P->next=(Dnode*)malloc(sizeof(Dnode));
        (P->next)->prev = P;
        P=P->next;

        printf("Enter your Data \n");
        scanf("%d",(&P->data));
        P->next=NULL;
    }
    return(head);
}

void print(Dnode *P)
{
    while(P!=NULL)
    {
        printf("--%d--",P->data);
        P=P->next;
    }
}

int count(Dnode *P)
{
    int i=0;
    while(P!=NULL)
    {
        P=P->next;
        i++;
    }
    return(i);
}

Dnode* insertB(Dnode* HEAD,int x)
{
    Dnode* p;
    p=(Dnode*)malloc(sizeof(Dnode));
    p->data = x;

    if(HEAD==NULL)
    {
        HEAD=p;
        HEAD->next=NULL;
    }
    else
    {
        p->next=HEAD;
        HEAD=p;
    }
    HEAD->prev=NULL;
    return(HEAD);
}

Dnode* insertM(Dnode* HEAD,int x)
{
    Dnode* p,*q;
    int y;

    p=(Dnode*)malloc(sizeof(Dnode));
    p->data = x;
    p->next = NULL;
    p->prev = NULL;

    printf("Insert after which number \n");
    scanf("%d",&y);

    q=HEAD;

    while(q!=NULL && q->data!=y)
    {
        q=q->next;
    }

    if(q!=NULL)
    {
        p->next = q->next;
        p->prev = q;
        (p->next)->prev = p;
        q->next = p;
    }
    else
    {
        printf("Data not found \n");
    }
    return(HEAD);
}

Dnode* insertE(Dnode* HEAD,int x)
{
    Dnode* p,*q;
    p=(Dnode*)malloc(sizeof(Dnode));
    p->data = x;
    p->next = NULL;
    p->prev = NULL;

    if(HEAD==NULL)
    {
        return(p);
    }

    q=HEAD;
    while(q->next!=NULL)
    {
        q=q->next;
    }
    q->next = p;
    p->prev = q;

    return(HEAD);
}
Dnode* del(Dnode * HEAD)
{
    Dnode *p,*q;
    int e;

    if(HEAD==NULL)
    {
        printf("Empty LL \n");
        return(HEAD);
    }

    printf("Enter element to be deleted \n");
    scanf("%d",&e);
    flushall();
    p=HEAD;

    if(HEAD->data==e)
    {
        HEAD = HEAD->next;
        free(p);
        return(HEAD);
    }


    while(p!=NULL && (p->next)->data!=e)
    {
        p=p->next;
    }

    if( (p->next)->data!=e)
    {
        printf("Data not found");
        return(HEAD);
    }
    else
    {
        q=p->next;
        p->next=q->next;
        (q->next)->prev = p;
        free(q);
        return(HEAD);
    }


}