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

typedef struct node
{
    int a;
    char ch;
    struct node *next;

} node;

node *head;

void insert_nth(int n,int aN,char chN)
{
    node *N=(node*)malloc(sizeof(node));
    N->a=aN;
    N->ch=chN;
    N->next=NULL;
    if(n==1)
    {
        N->next=head;
        head=N;
        return;
    }
    else
    {
        node*list=head;
        n=n-2;
        while(n!=0&&list->next!=NULL)
        {
            list=list->next;
            n--;
        }
        N->next=list->next;
        list->next=N;
    }
}


void display()
{

    node *list=head;
    while(list !=NULL)
    {
        printf("\n\nA= %d ,C= %c\n",list->a,list->ch);


        list=list->next;

    }
}

void insert_end(int aN,char chN)
{
    node *N=(node*)malloc(sizeof(node));
    N->a=aN;
    N->ch=chN;
    N->next=NULL;
    node *list=head;
    if(head==NULL)
    {
        head=N;
        list=N;
    }
    else
    {
        while(list->next!=NULL)
        {
            list=list->next;
        }
        list->next=N;

    }

}

int search(int n)
{
    node*list=head;
    int x=0;
    while(list!=NULL)
    {
        if(list->a==n)
        {
            printf("\n%d is Found\n\n",n);
            x=1;
            break;
        }
        else

            list=list->next;
    }
    if(x==0)
    {
        printf("\n%d is  Not Found\n\n",n);
    }
}

void insert_first(int aN,char chN)
{
    node*p=(node*)malloc(sizeof(node));
    p->a=aN;
    p->ch=chN;
    p->next=NULL;
    if(head==NULL)
    {
        head=p;
        return;
    }
    else
    {
        p->next=head;
        head=p;
    }
}

void delete_item(int value)
{
    node *list = head, *temp=NULL;
    int x = 0;

    while(list!=NULL)
    {
        if(list->a==value)
        {
            if(temp==NULL)
                head = list->next;
            else
                temp->next = list->next;

            printf("%d is deleted from list\n", value);
            x = 1;
            free(list);
            break;
        }
        temp = list;
        list = list->next;
    }
    if(x==0)
        printf("Key not found!\n");
}


void delete_pos(int pos)
{
    node *list=head,*temp=NULL;
    int x=0;
    if(pos==1)
    {
        head=head->next;
        free(list);
        return;
    }
    pos=pos-2;
    while(pos!=0)
    {
        list=list->next;
        pos--;
        if(list==NULL)
            return;
    }
    temp=list->next;
    list->next=temp->next;
    x=1;
    free(temp);
    if(x==1)
    {
        printf("KEY IS DELETED \n\n");
    }
}


void create()
{
    int value;
    char ch;
    while(1)
    {
        printf("   \nENTER  NUMBER & Character(-1 for exit)\n");
        scanf("%d",&value);
        if(value==-1)
        {
            break;
        }
        scanf(" %c",&ch);


        insert_end(value,ch);

    }


}


int main()
{
    head=NULL;
    int x,af,l;
    char cf;

    printf("   \n<<<<<<<<Create Linked List>>>>>>>>\n");
    create();
    display();
    printf("   \n<<<<<<<<Insert At FIRST>>>>>>>>\n");
    scanf("%d",&af);
    scanf(" %c",&cf);
    insert_end(af,cf);
    display();
    printf("   \n<<<<<<<<Insert At END>>>>>>>>\n");
    scanf("%d",&af);
    scanf(" %c",&cf);
    insert_end(af,cf);
    display();
    printf("   \n<<<<<<<<Insert At Nth(pos,int,char)>>>>>>>>\n");
    scanf("%d",&x);
    scanf("%d",&af);
    scanf(" %c",&cf);
    insert_nth(x,af,cf);
    display();
    printf("   \n<<<<<<<<SEARCH VALUE>>>>>>>>\n");
    scanf("%d",&l);
    search(l);
    printf("   \n<<<<<<<<DELETE BY POSITION>>>>>>>>\n");
    scanf("%d",&x);
    delete_pos(x);
    display();
    printf("   \n<<<<<<<<DELETE BY VALUE>>>>>>>>\n");
    scanf("%d",&l);
    delete_item(l);
    printf("   \n<<<<<<<<FINAL VALUE>>>>>>>>\n");
    display();
    return 0;
}