#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
    int info;
    struct node *next;
}*start,*p,*q,*temp,*i;
node * create_node(int value)
{
    struct node *temp;
    temp = new(struct node);
    temp->info = value;
    temp->next = NULL;
    return temp;
}
void display()
{
    struct node *i=start;
    cout<<"------My List------"<<endl;
    while(i!=NULL)
    {
        cout<<i->info<<" ";
        i=i->next;
    }
}
void insert_beg()
{
    int element;
    cout<<"enter info part:";
    cin>>element;
    struct node* temp = create_node(element);
    if(start==NULL)
    start=temp;
    else
    {
     temp->next=start;
     start=temp;
    }
}
void delete_first()
{
    if(start!=NULL)
    start=start->next;
}

void delete_pos()
{
    int pos, counter;
    cout<<"Enter position :";
    cin>>pos;
    if(pos==1)
        delete_first();
    else
    {
        for(counter=1;counter<pos && p!=NULL;counter++)
        {
            q=p;
            p=p->next;
        }
    q->next=p->next;
    }
}
void insert_pos()
{
    int pos,element;
    cout<<"enter position :";
    cin>>pos;
    cout<<"enter info part :";
    cin>>element;
    struct node*temp=create_node(element);
    if(start==NULL)
    start=temp;
    else
    {
        p=q=start;
        int j=1;
        while(p!=NULL && j<pos)
        {
            q=p;
            p=p->next;
            j++;
        }
    q->next=temp;
    temp->next=p;
    }
}
void insert_end()
{
    int element;
    cout<<"enter info part :";
    cin>>element;
    temp=create_node(element);
    if(start==NULL)
    start=temp;
    else
    {
        for(p=start;p->next!=NULL;p=p->next);
        p->next=temp;
    }
}

void search()
{
    int element, ind=1, found=0;
    if(start==NULL)
        cout<<"List is Empty";
    else
    {
    cout<<"Enter element to search";
    cin>>element;
    for(i=start;i!=NULL;i=i->next,ind++)
    {
        if(i->info==element)
        {
            cout<<"Found at Position"<<ind;
            found=1;
        }
    }
    if(!found)
        cout<<"Element not found";
    }
}

void reverse()
{
    struct node *curr, *prev, *nextptr;
    curr=prev=nextptr=start;
    if(start==NULL)
    cout<<"List is Empty";
    else
    {
    while(curr!=NULL)
    {
        nextptr=curr->next;
        curr->next=prev;
        prev=curr;
        curr=nextptr;
    }
    start->next=NULL;
    start=prev;
    }
}

int main()
{
    int choice=0;
    do
    {
        cout<<"1. insert at begin"<<endl;
        cout<<"2. display list"<<endl;
        cout<<"3. insert at position"<<endl;
        cout<<"4. insert at end"<<endl;
        cout<<"5. delete first element"<<endl;
        cout<<"6, delete at position"<<endl;
        cout<<"7. search"<<endl;
        cout<<"8. reverse the list"<<endl;
        cout<<"9. exit"<<endl;
        cin>>choice;
        switch(choice)
        {
            case 1: insert_beg();break;
            case 2: display();break;
            case 3: insert_pos();break;
            case 4: insert_end();break;
            case 5: delete_first();break;
            case 6: delete_pos();break;
            case 7: search();break;
            case 8: reverse();break;
            case 9: exit(1);
        }
    }
    while(choice!=9);
}