#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct Node
{
   int data;
   Node *next;
};
Node *start=NULL;
void menu()
{
   cout<<" 1. Add element at last";
   cout<<" 2. Add element at first";
   cout<<" 3. Display our list";
   cout<<" 4. Add element at sorted form";
   cout<<" 5. Delete any element by value";
   cout<<" 6. Search any element by value";
   cout<<" 9. Exit";
}
Node* createNode()
{
   Node *p=new Node;
   cout<<" Enter any value";
   cin>>p->data;
   p->next=NULL;
   return(p);
}
void addNodeAtLast()
{
     Node *t=createNode();
     if(start==NULL)
     {
    start=t;
     }
     else
     {
    Node *temp=start;
    while(temp->next!=NULL)
    {
      temp=temp->next;
    }
    temp->next=t;
     }
}
void displayList()
{
  Node *temp;
  temp=start;
  cout<<" ";
  while(temp!=NULL)
  {
    cout<<temp->data<<"  ";
    temp=temp->next;
  }
}
void addNodeAtFirst()
{
   Node *t=createNode();
   if(start==NULL)
   {
     start=t;
   }
   else
   {
     t->next=start;
     start=t;
   }
}
void addElementBySortedOrder()
{
  Node *t=createNode();
  if(t->data<=start->data)
  {
    t->next=start;
    start=t;
  }
  else
  {
  Node *t1=start;
  Node *t2=start->next;
  while(t2->data<t->data && t2!=NULL)
  {
     t2=t2->next;
     t1=t1->next;
  }
  t1->next=t;
  t->next=t2;
 }
}
void deleteByValue()
{
  int x;
  cout<<" Enter any value to be delete";
  cin>>x;
  int flag=0;
  Node *t=start;
  if(start->data==x)
  {
    start=start->next;
    flag=1;
    cout<<" "<<x<<" has been deleted";
  }
  else
  {
    while(t!=NULL)
    {
      if(t->next->data==x)
      {
     flag=1;
     break;

      }
      t=t->next;
    }

     if(flag==1)
    {
      t->next=t->next->next;
      cout<<endl<<x<<" has been deleted";
    }
    else
    {
       cout<<" Element not found";
    }

  }

}

void searchValue()
{
   int x;
   cout<<" Enter any value to be search";
   cin>>x;
   int cnt=0;
   Node *t=start;
   int flag=0;
   while(t!=NULL)
   {
     cnt++;
     if(t->data==x)
     {
       flag=1;
       break;
     }

     t=t->next;
   }
   if(flag==0)
   cout<<" Element not present in our list";
   else
     cout<<x<<" is present at "<<cnt<<" position";

}
void main()
{
  int ch;
  clrscr();

   while(1)
   {
      menu();
      cout<<" enter your choice";
      cin>>ch;
      switch(ch)
      {
    case 1:
        addNodeAtLast();
        break;
    case 2:
           addNodeAtFirst();
          break;
    case 3:
              displayList();
          break;
    case 4:
              addElementBySortedOrder();
              break;
    case 5:
           deleteByValue();
           break;
    case 6:
         searchValue();
         break;
    case 9:
         exit(0);
         break;
    default:
        cout<<" Invalid value";

      }
   }

}