#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
    int no;
    struct node *next,*prv;
};
typedef struct node node;
node *head=NULL;
void create();
void inst_last();
void inst_bwt();
void inst_bwt_before();
void inst_bwt_after();
void del_first();
void del_last();
void del_bwt();
void del_bwt_before();
void del_bwt_after();
void search();
void update();
void sort();
void display();
void main()
{
    int ch;
    clrscr();
    while(1)
    {
        printf("\n1.Create");
        printf("\n2.Insert Last");
        printf("\n3.Insert Between");
        printf("\n4.Insert Between Before");
        printf("\n5.Insert Between After");
        printf("\n6.Delete first");
        printf("\n7.Delete Last");
        printf("\n8.Delete Between");
        printf("\n9.Delete Between Before");
        printf("\n10.Delete Between After");
        printf("\n11.Search Node Using Values");
        printf("\n12.Update Node Values");
        printf("\n13.Display Values");
        printf("\n14.Sort Node Values");
        printf("\n15.Exit - - - - - - - - - - - - - - - - >");
        printf("\nEnter Your Choice :");
        scanf("%d",&ch);

            switch(ch)
            {
                case 1:
                    create();
                    break;
                case 2:
                    inst_last();
                    break;
                case 3:
                    inst_bwt();
                    break;
                case 4:
                    inst_bwt_before();
                    break;
                case 5:
                    inst_bwt_after();
                    break;
                case 6:
                    del_first();
                    break;
                case 7:
                    del_last();
                    break;
                case 8:
                    del_bwt();
                    break;
                case 9:
                    del_bwt_before();
                    break;
                case 10:
                    del_bwt_after();
                    break;
                case 11:
                    search();
                    break;
                case 12:
                    update();
                    break;
                case 13:
                    display();
                    break;
                case 14:
                    sort();
                    break;
                case 15:
                    exit();
                    break;
                default:
                    printf("\n\n\n\n\ninvalid choice\n\n\n\n\n\n");
            }
    }
getch();
}
void create()
{
    node *tmp;
    tmp=(node *)malloc(sizeof(node));
    printf("\nEnter Head Node Value :");
    scanf("%d",&tmp->no);
    tmp->next=NULL;
    tmp->prv=NULL;
        if(head==NULL)
        {
            head=tmp;
            printf("\n\n\n\n\n\n\n\n\nFirst Node Created With Value : %d\n\n\n",tmp->no);
        }
        else
        {
            printf("\n\n\n\n\n\n\n\n\nYou Can't Create First Node Twice");
        }
}
void inst_bwt()
{
    node *tmp,*cur=head,*cur1;
    int i=1,p;
    tmp=(node *)malloc(sizeof(node));
    printf("\nEnter position number :");
    scanf("%d",&p);
    printf("\nEnter %d Node Value :",p);
    scanf("%d",&tmp->no);
    tmp->next=NULL;
    tmp->prv=NULL;
        if(head==NULL)
        {
            printf("\n\n\n\n\n\n\n\n\nYou Can't Create First Node Twice");
        }
        else
        {
            while(cur->next!=NULL&&i<p)
            {
                cur1=cur;
                cur=cur->next;
                i++;
            }
            cur->prv=tmp;
            tmp->next=cur;
            cur1->next=tmp;
            tmp->prv=cur1;
            printf("\n\n\n\n\n\n\n\n\nPosition Number %d Node Created With Value : %d\n\n\n",p,tmp->no);
        }
}
void inst_bwt_before()
{
    node *tmp,*cur=head,*cur1;
    int i=2,p;
    tmp=(node *)malloc(sizeof(node));
    printf("\nEnter position number :");
    scanf("%d",&p);
    printf("\nEnter %d Node Value :",p);
    scanf("%d",&tmp->no);
    tmp->next=NULL;
    tmp->prv=NULL;
        if(head==NULL)
        {
            printf("\n\n\n\n\n\n\n\n\nYou Can't Create First Node Twice");
        }
        else
        {
            while(cur->next!=NULL&i<p)
            {
                cur1=cur;
                cur=cur->next;
                i++;
            }
            cur->prv=tmp;
            tmp->next=cur;
            cur1->next=tmp;
            tmp->prv=cur1;
            printf("\n\n\n\n\n\n\n\n\nPosition Number %d Node Created With Value : %d\n\n\n",p,tmp->no);
        }
}
void del_first()
{
    node *cur=head;
    if(head==NULL)
    {
        printf("\n\n\n\n\n\n\n\n\nYou Can't Create First Node Twice");
    }
    else
    {
        head=cur->next;
        head->prv=NULL;
        free(cur);
        printf("\n\n\n\n\n\n\n\n\n\n\n\nFirst Node Deleted\n");
    }
}

void del_last()
{
    node *cur=head,*cur1;
    if(head==NULL)
    {
        printf("\n\n\n\n\n\n\n\n\nYou Can't Create First Node Twice");
    }
    else
    {
        while(cur->next!=NULL)
        {
            cur1=cur;
            cur=cur->next;
        }
        cur1->next=NULL;
        free(cur);
        printf("\n\n\n\n\n\n\n\n\n\n\n\nFirst Node Deleted\n");
    }
}
void del_bwt()
{
    node *cur=head,*cur1;
    int i=1,p;
    printf("Enter Position Number :");
    scanf("%d",&p);
    if(head==NULL)
    {
        printf("\n\n\n\n\n\n\n\n\nYou Can't Create First Node Twice");
    }
    else
    {
        while(cur->next!=NULL&&i<p)
        {
            cur1=cur;
            cur=cur->next;
            i++;
        }
        cur1->next=cur->next;
        cur->next->prv=cur1;
        free(cur);
        printf("\n\n\n\n\nbwt node deleted");

    }

}
void del_bwt_before()
{
    node *cur=head,*cur1;
    int i=2,p;
    printf("Enter Position Number :");
    scanf("%d",&p);
    if(head==NULL)
    {
        printf("\n\n\n\n\n\n\n\n\nYou Can't Create First Node Twice");
    }
    else
    {
        while(cur->next!=NULL&&i<p)
        {
            cur1=cur;
            cur=cur->next;
            i++;
        }
        cur1->next=cur->next;
        cur->next->prv=cur1;
        free(cur);
        printf("\n\n\n\n\nbwt node deleted");

    }

}

void del_bwt_after()
{
    node *cur=head,*cur1;
    int i=0,p;
    printf("Enter Position Number :");
    scanf("%d",&p);
    if(head==NULL)
    {
        printf("\n\n\n\n\n\n\n\n\nYou Can't Create First Node Twice");
    }
    else
    {
        while(cur->next!=NULL&&i<p)
        {
            cur1=cur;
            cur=cur->next;
            i++;
        }
        cur1->next=cur->next;
        cur->next->prv=cur1;
        free(cur);
        printf("\n\n\n\n\nbet node deleted");

    }
}

void inst_bwt_after()
{
    node *tmp,*cur=head,*cur1;
    int i=0,p;
    tmp=(node *)malloc(sizeof(node));
    printf("\nEnter position number :");
    scanf("%d",&p);
    printf("\nEnter %d Node Value :",p);
    scanf("%d",&tmp->no);
    tmp->next=NULL;
    tmp->prv=NULL;
        if(head==NULL)
        {
            printf("\n\n\n\n\n\n\n\n\nYou Can't Create First Node Twice");
        }
        else
        {
            while(cur->next!=NULL&i<p)
            {
                cur1=cur;
                cur=cur->next;
                i++;
            }
            cur->prv=tmp;
            tmp->next=cur;
            cur1->next=tmp;
            tmp->prv=cur1;
            printf("\n\n\n\n\n\n\n\n\nPosition Number %d Node Created With Value : %d\n\n\n",p,tmp->no);
        }
}

void inst_last()
{
    node *tmp,*cur=head;
    tmp=(node *)malloc(sizeof(node));
    printf("\nInsert Last Node Value :");
    scanf("%d",&tmp->no);
    tmp->next=NULL;
    tmp->prv=NULL;
        if(head==NULL)
        {
            printf("First Node Was Not Created");
        }
        else
        {
               while(cur->next!=NULL)
               {
                cur=cur->next;
               }
               tmp->prv=cur;
               cur->next=tmp;
               printf("\n\n\n\n\n\n\n\n\nLast Node Created With Value : %d\n\n\n",tmp->no);
        }
}
void search()
{
    int s,flag=0;
    node *cur=head;
    printf("\n\nEnter Node Value Number To Serch");
    scanf("%d",&s);
    if(head==NULL)
    {
        printf("First Node Was Not Created");
    }

    else
    {
        while(cur!=NULL)
        {
            if(cur->no==s)
            {
                flag=1;
                break;
            }
            cur=cur->next;
        }
        if(flag==1)
        {
            printf("\n\n\n\n\n\n\n\n\nNode Found\n\n\n",cur->no);
        }
        else
        {
            printf("\n\n\n\n\n\n\nNode Note found Any where In Current Linked-list\n\n\n\n\n\n");
        }
    }
}

void update()
{
    int s,u,i=1,flag=0;
    node *cur=head;
    printf("\n\nEnter Node Value Mendetory it is exist in current linked list");
    scanf("%d",&s);
    printf("\n\n\nEnter New Value Which You Want To Update");
    scanf("%d",&u);
    if(head==NULL)
    {
        printf("First Node Was Not Created");
    }

    else
    {
        while(cur!=NULL)
        {
            if(cur->no==s)
            {
                cur->no=u;
                flag=1;
                break;
            }
            cur=cur->next;
            i++;
        }
        if(flag==1)
        {
            printf("\n\n\n\n\n\n\n\n\nNode Updated with Value : %d \nNew Node Position Number is :%d \n\n\n",cur->no,i);
        }
        else
        {
            printf("\n\n\n\n\n\n\nNode Note found Any where In Current Linked-list\n\n\n\n\n\n");
        }
    }
}
void sort()
{
    node *cur=head;
    int tmp;
    while(cur->next!=NULL)
    {
        if(cur->no>cur->next->no)
        {
            tmp=cur->next->no;
            cur->next->no=cur->no;
            cur->no=tmp;
        }
        cur=cur->next;
    }
}

void display()
{
    node *cur=head;
    int i=1;
     printf("\n\n\n\n\n\n\n\n\n\n\n\nNO | PREVIOUS ADD | NODE VALUE | OWN ADD | NEXT ADD\t|\n");
    while(cur!=NULL)
    {
        printf("%d  |\t%u\t  |\t%d     |  %u\t |  \t%u\t|\n",i,cur->prv,cur->no,cur,cur->next);
        i++;
        cur=cur->next;
    }
}