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

void insertafter(struct node ** ,int ,int);
void insertatbeg(struct node ** ,int );
void add(struct node ** ,int);
void search(struct node **,int);
void del(struct node ** ,int);
void count(struct node * );
void display(struct node *);
void auxsearch(struct node ** , int );
void revtraverse(struct node **);

struct node
{
    int data;
    struct node *link;
};

void main()
{
    int elmt,choice,pos,num;
    char wish;
    struct node *p;

    p=NULL;
    printf("\t\t\tmenu\n\n");
    printf("1.Add element\n2.Display elements\n3.Count of nodes\n4.Insert at begginning\n5.Insert at middle\n6.Insert at end\n7.Delete the element\n8.Search an element\n9.auxiliary search\n10.reverse list\n");
    do
    {
        printf("\nenter the choice\t");
        scanf("%d",&choice);
        
        switch(choice)
        {
        case 1:
        case 6:
            printf("enter the element \t");
            scanf("%d",&elmt);
            add(&p,elmt);
            break;
        case 2:
            display(p);
            break;
        case 3:
            count(p);
            break;
        case 4:
            printf("\nenter the element to be inserted\t");
            scanf("%d",&num);
            insertatbeg(&p,num);
            break;
        case 5:
            printf("\nenter the position to insert\t");
            scanf("%d",&pos);
            pos--;
            printf("enter the element to insert\t");
            scanf("%d",&num);
            insertafter(&p,pos,num);
            break;
        case 7:
            printf("\nenter the element to be deleted\t");
            scanf("%d",&num);
            del(&p,num);
            break;
        case 8:
            printf("\nenter the element to search\t");
            scanf("%d",&num);
            search(&p,num);
            break;
        case 9:
            printf("\nenter the element to search\t");
            scanf("%d",&num);
            auxsearch(&p,num);
            break;
        case 10:
            printf("\nafter reversing...\n");
            revtraverse(&p);
            display(p);
            break;
        }
        printf("\ndo you want to continue? {y/n} \t");
        wish=getche();
    }while(wish=='y' || wish =='Y');
    getch();
}

void add(struct node **q ,int num)
{
    struct node *temp,*r;
    temp=*q;
    if(*q==NULL)
    {
        temp=(struct node*)malloc(sizeof(struct node));
        temp->data=num;
        temp->link=NULL;
        *q=temp;
    }
    else
    {
        temp=*q;
        while(temp->link!=NULL)
            temp=temp->link;
        r=(struct node*)malloc(sizeof(struct node));
        r->data=num;
        r->link=NULL;
        temp->link=r;
    }
}

void display(struct node *q )
{
    if(q == NULL)
        printf("\nNo elements in the list...");
    else
    {
        printf("\nthe elements in the list are\t");
        while(q!=NULL)
        {
            printf("\n %d",q->data);
            q=q->link;
        }
    }
    
}

void count(struct node *q )
{
    int c=0;
    
    while(q!=NULL)
    {
        q=q->link;
        c++;
    }
    printf("the number of nodes is %d\t",c);
}

void insertafter(struct node**q ,int pos,int num)
{
    struct node *temp,*r;
    int i;
    temp=*q;
    for(i=0;i<pos;i++)
        temp=temp->link;
    if(temp==NULL)
    {
        printf("there are less than %d elements in list\n",pos);
        return;
    }
    r=(struct node*)malloc(sizeof(struct node));
    r->data=num;
    r->link=temp->link;
    temp->link=r;
    
}

void insertatbeg(struct node **q ,int num)
{
    struct node *temp;
    temp=(struct node*)malloc(sizeof(struct node));
    temp->data = num;
    temp->link = *q;
    *q=temp;
}

void del(struct node **q ,int num)
{
    struct node *old,*temp;
    temp=*q;
    while(temp!=NULL)
    {
        if(temp->data == num)
        {
            if(temp==*q)
            {
                *q=temp->link;
                free(temp);
                return;
            }
            else
            {
                old->link=temp->link;
                free(temp);
                return;
            }
        }
        else
        {
            old=temp;
            temp=temp->link;
        }
    }
    printf("\n element not found in list\n");
}

void search(struct node **q,int num)
{
    int flag=0,c=0;
    struct node *temp;
    temp=*q;
    
    while(temp != NULL)
    {
        if(temp->data == num)
            flag=1;
        temp=temp->link;
        c++;
    }
    if(flag)
        printf("\nelement found");
    else
        printf("\nno such element ");
}

void auxsearch(struct node **q , int num)
{
    int flag=0;
    struct node *temp;
    temp=*q;
    while(temp->link != NULL)
    {
        if(temp->link->data == num)
        {
            flag=1;
            printf("\nthe elmt is %d",temp->link->data);
            printf("\nthe prior elmt is %d",temp->data);
            break;
        }
        temp=temp->link;
    }
    if(flag==0)
        printf("\nno such element");
}

void revtraverse(struct node **q)
{
    struct node *r,*temp,*s;
    temp=*q;
    r=NULL;
    while(temp != NULL)
       {
        s=r;
        r=temp;
        temp=temp->link;
        r -> link=s;
        
    }
    *q=r;
}