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

node* create(int);
void print(node*);
int count(node*);
node* insertB(node*,int);
node* insertM(node*,int);
node* insertE(node*,int);
node* del(node*);
void main()
{
    node *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();
}

node* create(int n)
{
    node *head,*P;

    int i;

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

    P=head;
    for(i=1;i<n;i++)
    {
        P->next=(node*)malloc(sizeof(node));
        P=P->next;
        printf("Enter your Data \n");
        scanf("%d",(&P->data));
        P->next=NULL;
    }
    return(head);
}

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

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



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

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

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

    p=(node*)malloc(sizeof(node));
    p->data = x;
    p->next = 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;
        q->next = p;
    }
    else
    {
        printf("Data not found \n");
    }
    return(HEAD);
}

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

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

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

    return(HEAD);
}
node* del(node * HEAD)
{
    node *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;
        free(q);
        return(HEAD);
    }


}