/* header files*/
#include<stdio.h>
#include<stdlib.h>

/* Node definition */
typedef struct node
{
    int info;
    struct node *link;
}list;

/* Function declaration */
void display(list * start);
void search(list *start,int item);
list *addAtBegin(list *start, int data);
list *addAtEnd(list *start, int data);
list *addAfter(list *start,int data,int item);
list *addBefore(list *start,int data,int item);
list *addAtPosition(list *start,int data,int pos);
list *Pop(list *start);
list *Del(list *start,int data);
list *reverseList(list *start);
int main()
{
    int data,choice,item,pos;
    list * start = NULL;
    while(1)
    {
        printf("1.Add at Begin\t");
        printf("2.Add at End\n");
        printf("3.Display list\t");
        printf("4.Search an Item\n");
        printf("5.Enter an Item to insert after\n");
        printf("6.Enter an Item to insert before\n");
        printf("7.Enter a Position in which want to insert \n");
        printf("8.Pop operation...\n");
        printf("10.Delete any node\n");
        printf("11. Reverse list..\n");
        printf("9.QUIT.....\n");
        printf("Enter choice:");
        scanf("%d",&choice);
        printf("\n");
    switch(choice)
    {
    case 1:
        printf("Enter data to Add at begin:");
        scanf("%d",&data);
        start=addAtBegin(start,data);
        break;
    case 2:
        printf("Enter data to Add at end:");
        scanf("%d",&data);
        start=addAtEnd(start,data);
        break;
    case 3:
        display(start);
        break;
    case 4:
        printf("Enter item to search:");
        scanf("%d",&item);
        search(start,item);
        break;
    case 5:
        printf("Enter data to insert:");
        scanf("%d",&data);
        printf("Enter item after which want to insert:");
        scanf("%d",&item);
        start=addAfter(start,data,item);
        break;

    case 6:
        printf("Enter data to insert:");
        scanf("%d",&data);
        printf("Enter item before which want to insert:");
        scanf("%d",&item);
        start=addBefore(start,data,item);
        break;

    case 7:
        printf("Enter data to insert:");
        scanf("%d",&data);
        printf("Enter pos in which want to insert:");
        scanf("%d",&pos);
        start=addAtPosition(start,data,pos);
        break;

    case 8:
        start=Pop(start);
        break;

    case 9:
        exit(0);

    case 10:
        printf("Enter node to be deleted:");
        scanf("%d",&data);
        start=Del(start,data);
        printf("%d deleted..\n",data);
        break;
    case 11:
        printf("The list before reverse.\n");
        display(start);
        printf("The list after reverse.\n");
        start = reverseList(start);
        display(start);
        break;
    }/* End switch*/
    }/* End of while*/

}/* End of main*/

void display(list * start)
{
    list *p;
    p=start;
    if(p==NULL)
        printf("List is empty..\n");
    printf("Start -> ");
    while(p!=NULL)
    {
        printf("%d -> ",p->info);
        p=p->link;
    }
    printf("NULL");
    printf("\n");
}
void search(list *start,int item)
{
    list *p;
    int pos =1;
    p=start;
    if(p==NULL)
    {
      printf("List is empty BOSS...\n");
      return;
    }
    while(p!=NULL)
    {
        if(p->info==item)
        {
            printf("%d found in %d position\n",item,pos);
            return;
        }
            pos++;
            p=p->link;
    }
    printf("%d not present ....\n",item);
}
list *addAtBegin(list *start, int data)
{
    list *tmp;
    tmp=(list *)malloc(sizeof(list));
    tmp->info=data;
    tmp->link=start;
    start=tmp;
    return start;
}

list *addAtEnd(list *start, int data)
{
    list *tmp,*p;
    p=start;
    tmp=(list *) malloc(sizeof(list));
    tmp->info=data;
    while(p->link!=NULL)
        p=p->link;

    p->link=tmp;
    tmp->link=NULL;

    return start;
}
list *addAfter(list *start,int data,int item)
{
    list *p,*tmp;
    if(start==NULL)
    {
      printf("List is empty BOSS...\n");
      return start;
    }
    p=start;
    while(p->link!=NULL)
    {
        if(p->info==item)
        {
            tmp= (list *)malloc(sizeof(list));
            tmp->info=data;

            tmp->link=p->link;
            p->link=tmp;

            return start;
        }
        p=p->link;
    }
    printf("%d not present in the list...\n",item);
    return start;
}
list *addBefore(list *start,int data,int item)
{
    list *tmp,*p;

    if(item==start->info)
    {
        tmp= (list *)malloc(sizeof(list));
        tmp->info=data;
        tmp->link=start;
        start=tmp;
        return start;
    }
    p=start;

    while(p->link!=NULL)
    {
        if(p->link->info==item)
        {
            tmp= (list *)malloc(sizeof(list));
            tmp->info=data;

            tmp->link=p->link; // Important to remember this order/
            p->link=tmp;
            return start;
        }
        p=p->link;
    }
    printf("%d not present in the list...\n",item);
    return start;
}
list *addAtPosition(list *start,int data,int pos)
{
    list *tmp,*p;
    int i;
    tmp=(list *)malloc(sizeof(list));
    tmp->info=data;
    if(pos==1)
    {
        tmp->link=start;
        start=tmp;
        return start;
    }
    p=start;
    for(i=1; i<pos-1 && p!=NULL; i++)
        p=p->link;

        if(p==NULL)
        {
            printf("Less than %d position in the list..\n",pos);
        }
        else{
            tmp->link=p->link;
            p->link=tmp;
        }

    return start;
}
list *Pop(list *start)
{
    list *p;
    p=start;
    if(start==NULL)
      printf("List is empty BOSS...\n");
    else{
        start=start->link;
        free(p);
        printf("Popping Done...\n\n");
    }
     return start;
}
list *Del(list *start,int data)
{
    list *p,*tmp;

    if(start==NULL){
      printf("List is empty BOSS...\n");
      return start;
    }
    if(start->info==data)
    {
        tmp=start;
        start=start->link;
        free(tmp);
        return start;
    }
    p=start;

    while(p->link!=NULL)
      {
        if(p->link->info==data)
        {
            tmp=p->link;
            p->link=tmp->link;
            free(tmp);
            return start;
        }
        p=p->link;
      }
      printf("%d not found...\n",data);
      return start;
}
list *reverseList(list *start)
{
    list *prev,*p,*next;
    prev=NULL;
    next=NULL;
    p=start;
    while(p!=NULL)
    {
        next=p->link;
        p->link=prev;
        prev=p;
        p=next;
    }
    start=prev;
    return start;
}