#include <stdio.h>

struct node {
   int info;
   struct node *link;
}*start;

int createnode(int data);
int addatbeg(int data);
int addinbet(int pos, int data);
int delnode(int m);
int display();
int search(int data);

/* Main function starts here */
int main()
{
    int choice, m, n, i ;
    
    printf("1. Create a Node\n");
    printf("2. Add a node in beginning\n");
    printf("3. Add a node in between or end\n");
    printf("4. delete a node\n");
    printf("5. display a node\n");
    printf("6. Search a node\n");
    printf("7. Quit\n");
    
    while(choice != 0) {
       printf("Enter your choice: ");
       scanf("%d", &choice);
    
       switch(choice) {
          case 1 :
             printf("How many nodes do you want: ");
             scanf("%d", &n);
            
             for(i=0; i<n; i++){
                printf("Enter the number to be entered : \n");
                scanf("%d", &m);
                createnode(m);
             }
             break;
       
          case 2 :
             printf("Enter the element: ");
             scanf("%d", &m);
             addatbeg(m);
             break;
       
          case 3 :
             printf("Enter the position at which you want the node to be entered: ");
             scanf("%d", &n);
             printf("Enter the number that you want to enter: ");
             scanf("%d", &m);
             addinbet(n,m);
             break;
       
          case 4 :
             if(start == NULL) {
                printf("List is empty\n");
                break;
             }
            
             printf("Enter the element for deletion: ");
             scanf("%d", &m);
             delnode(m);
             break;
          
           case 5 :
              display();
              break;
            
           case 6 :
              printf("Enter the element to be searched : ");
              scanf("%d", &m);
              search(m);
              break;
       
           case 7 :
              exit(1);
       
           default :
              printf("Invalid Choice\n");
              break;
       }     
    }  
    fgetc(stdin);
       
}
/* Main function ends here */
   
/* Createnode function starts here */
int createnode(int data)
{
    struct node *tmp, *q;
    
    tmp = malloc(sizeof(struct node));
    
    tmp->info = data;
    tmp->link = NULL ;
    
    if(start == NULL){
       start = tmp;
    }
    
    else {
       q = start;
       
       while(q->link != NULL) {
          q = q->link;
       }
       
       q->link = tmp;
    }
    
}
/* createnode function ends here */

/* addatbeg starts here */
int addatbeg(int data)
{
    struct node *tmp;
    
    tmp = malloc(sizeof(struct node));
    
    tmp->info = data;
    tmp->link = start;
    start = tmp;
}
/* addatbeg ends here */

/* addinbet starts here */
int addinbet(int pos, int data)
{
    struct node *tmp, *q;
    
    int i;
    
    q = start;
    
    for(i=0; i<pos-1; i++) {
       q = q->link;
       
       if(q == NULL) {
          printf("The number at position %d does not exist\n", i);
          return;
       }
    }
    
    tmp = malloc(sizeof(struct node));
    tmp->info = data;
    tmp->link = q->link;
    q->link = tmp;
}
/* Addinbet ends here */

/* delnode function starts here */
int delnode(int data)
{
    struct node *tmp, *q ;
    
    if(start->info == data){
       tmp = start;
       start = start->link ;
       free(tmp);
       return ;
    }
    
    q = start;
    
    while(q->link != NULL) {
       if(q->info == data){
          tmp = q->link;
          q->link = tmp->link;
          free(tmp);
          return;
       }
       q = q->link;
    }
 
    if(q->info == data ) {
       tmp = q->link ;
       free(tmp);
       q->link = NULL;
       return;
    }

    printf("Element %d not found\n", data);
}
/* Delnode function ends here */

int display()
{
    struct node *q;
    if(start == NULL) {
       printf("List is empty\n");
          return ;
    }
         
    q = start;
         
    printf("List is : \n");
    
    while(q != NULL) {
       printf("%d  ", q->info);
       q=q->link;
    }
         
    printf("\n");
    
}
/* Display function ends here */

int search(int data)
{
   struct node *tmp;
   tmp = start;
        
   int pos = 1;
   
   while(tmp != NULL) {
      if(tmp->info == data) {
         printf("Item %d found  at position %d\n", data, pos);
         fgetc(stdin);
         return ;
      }
      
      tmp = tmp->link;
      pos++;
   }
   
   if(tmp == NULL) {
      printf("Item %d not found in the list\n", data);
   }
   
   fflush(stdin);
   fgetc(stdin);
   return 0;
}
/* search function ends here */