/*PROGRAM FOR GENERATING AND MANIPULATING A LINKED LIST*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define INV -999

struct node
{
 int data;
 struct node *next;
};
typedef struct node node;

node *first,*old,*newnode,*temp;

void display()
{
 if(first==NULL)
 {
  printf("\nList Empty! Press a key...");
  getch();
 }
 else
 {
  printf("\nThe contents of the Linked List are as follows: \n");
  for(old=first;old!=NULL;old=old->next)
   printf("%d ",old->data);
  printf("\nPress a key...");
  getch();
 }
}

node * search(int sem)
{
 old=first;
 while(old!=NULL)
 {
  if(old->data==sem)
   break;
  else
   old=old->next;
 }
 return(old);
}

void delnode(int pos)
{
 int sem;
 if(first==NULL)
 {
  printf("\nList Underflow! \nCannot perform requested operation! Press a key...");
  getch();
 }
 else
 {
  switch(pos)
  {
   case 1:old=first;
	  first=first->next;
	  free(old);
	  break;
   case 2:if(first->next==NULL)
	  {
	   free(first);
	   first=NULL;
	  }
	  else
	  {
	   old=first;
	   while(old->next!=NULL)
	    old=old->next;
	   temp=old;
	   old=first;
	   while(old->next!=temp)
	    old=old->next;
	   old->next=NULL;
	   free(temp);
	  }
	  break;
   case 3:printf("\nEnter the element to be deleted from the list: ");
	  scanf("%d",&sem);
	  old=search(sem);
	  if(old!=NULL)
	  {
	   if(old==first)
	   {
	    if(first->next==NULL)
	    {
	     free(first);
	     first=NULL;
	    }
	    else
	    {
	     temp=first;
	     first=first->next;
	     free(temp);
	    }
	   }
	   else
	   {
	    temp=old;
	    old=first;
	    while(old->next!=temp)
	     old=old->next;
	    old->next=temp->next;
	    free(temp);
	   }
	  }
	  else
	  {
	   printf("\nThe element you entered does not exist in the list!\nCannot perform the requested operation. Press a key...");
	   getch();
	  }
	  break;
   default:printf("\nOption does not exist! Press a key...");
	   getch();
	   break;
  }
 }
}

void insert(int num,int pos)
{
 int sem;
 if(num==INV)
 {
  printf("\nInvalid Value! Press a key...");
  getch();
 }
 else
 {
  newnode=(node *)malloc(sizeof(node));
  newnode->data=num;
  if(first==NULL)
  {
   first=newnode;
   first->next=NULL;
   old=first;
  }
  else
  {
   switch(pos)
   {
    case 0:old->next=newnode;
	   newnode->next=NULL;
	   old=newnode;
	   break;
    case 1:temp=first;
	   first=newnode;
	   newnode->next=temp;
	   break;
    case 2:old=first;
	   while(old->next!=NULL)
	    old=old->next;
	   old->next=newnode;
	   newnode->next=NULL;
	   break;
    case 3:if(first!=NULL)
	   {
	    printf("\nEnter the element after which the element is to be inserted: ");
	    scanf("%d",&sem);
	    old=search(sem);
	    if(old!=NULL)
	    {
	     temp=old->next;
	     old->next=newnode;
	     newnode->next=temp;
	    }
	    else
	    {
	     printf("\n%d does not exist in the list!\nCannot perform the requested operation. Press a key...",sem);
	     free(newnode);
	     getch();
	    }
	   }
	   else
	   {
	    printf("\nThis option requires to have atleast one element in the list!\nCannot perform the requested operation. Press a key...");
	    free(newnode);
	    getch();
	   }
	   break;
    default:printf("\nInvalid option! Press a key...");
	    free(newnode);
	    getch();
	    break;
   }
  }
 }
}

void create()
{
 int num;
 num=0;
 while(1)
 {
  printf("\nEnter the element: ");
  scanf("%d",&num);
  if(num!=INV)
   insert(num,0);
  else
  {
   printf("\nLinked List created!");
   getch();
   break;
  }
 }
}

void main()
{
 int num;
 char choice,verify,ch;
 choice='0';
 first=NULL;
 while(choice!='6')
 {
  clrscr();
  printf("Program for generating and manipulating a Linked List.\n*** MENU ***\n 1. Create List\n 2. Insert Node\n 3. Delete Node\n 4. Search List\n 5. Display List\n 6. Exit\nEnter Your Choice: ");
  choice=getche();
  switch(choice)
  {
   case '1':printf("\nNote: Contents of existing list \(if any\) will be lost!\nVerify: Create new list? Y/N-> ");
	    verify=getch();
	    if(verify=='Y'||verify=='y')
	    {
	     if(first!=NULL)
	     {
	      old=first;
	      while(old!=NULL)
	      {
	       temp=old;
	       old=old->next;
	       free(temp);
	      }
	      old=first;
	     }
	     create();
	    }
	    else
	    {
	     printf("\nNo action performed! Press a key...");
	     getch();
	    }
	    break;
   case '2':printf("\nINSERT MENU: \n 1. Insert as first node\n 2. Insert as last node\n 3. Insert after certain node \n 4. Abort insertion\nEnter your choice: ");
	    ch=getche();
	    switch(ch)
	    {
	     case '1':
	     case '2':
	     case '3':printf("\nEnter the element to be inserted: ");
		      scanf("%d",&num);
		      insert(num,atoi(&ch));
		      break;
	     default: printf("\nInvalid Input!");
	     case '4':printf("\nInsertion Aborted! Press a key...");
		      getch();
		      break;
	    }
	    break;
   case '3':printf("\nDELETE MENU: \n 1. Delete first node\n 2. Delete last node\n 3. Delete a certain node \n 4. Abort deletion\nEnter your choice: ");
	    ch=getche();
	    switch(ch)
	    {
	     case '1':
	     case '2':
	     case '3':delnode(atoi(&ch));
		      break;
	     default: printf("\nInvalid Input!");
	     case '4':printf("\nDeletion Aborted! Press a key...");
		      getch();
		      break;
	    }
	    break;
   case '4':printf("\nEnter the element to be searched: ");
	    scanf("%d",&num);
	    old=search(num);
	    if(old!=NULL)
	    {
	     printf("\nElement %d Found!",num);
	     for(num=1,temp=first;temp!=old;temp=temp->next)
	      num++;
	     printf("\nElement index = %d",num);
	     display();
	    }
	    else
	    {
	     printf("\nElement %d Not Found!",num);
	     getch();
	    }
	    break;
   case '5':display();
	    break;
   case '6':printf("\nShutting down Linked List program. Clearing memory used...");
	    old=first;
	    while(old!=NULL)
	    {
	     temp=old;
	     old=old->next;
	     free(temp);
	    }
	    printf(" done.\nProgram Terminated.");
	    break;
   default: printf("\nInvalid Input! Press a key...");
	    getch();
	    break;
  }
 }
}