#include<iostream>
using namespace std;
template<class T>
class Linklist;
template<class T>
class Node
{

    T data;
    Node *next;
    friend class Linklist<T>;
};
template<class T>
class Linklist
{
    Node<T> *head;
public:

    Linklist()
    {
        head=NULL;
    }
    void insert(T value)
    {
        Node<T> *cur,*prev;
        if(head==NULL)
        {
            cur=new Node<T>;
            cur->data=value;
            cur->next=NULL;
            head=cur;
        }
        else
        {
            cur=head;
            while(cur!=NULL)
            {
                prev=cur;
                cur=cur->next;
            }
        
        cur=new Node<T>;
        cur->data=value;
        prev->next=cur;
        }
    }
    void display()
    {
        Node<T>*cur;
        cur=head;
        cout<<"the elements and address is \n";
        while(cur!=NULL)
        {
            cout<<cur->data<<"->";
            cur=cur->next;
        }
        cout<<"NULL\n";
    }
    int search(T value)
    {
        
        Node<T>*cur;
        cur=head;
        while(cur!=NULL)
        {
            if(value==cur->data)
            {
                cout<<"the element is present\n";
                break;
            }
            else
            {
                cur=cur->next;
            }
            
        }if(cur==NULL)
            {
                cout<<"the element is not present\n";
                return 0;
            }
    }
    void insertpos(int pos,T val)
    {
        int **1;
        Node<T>*cur,*prev;
        cur=head;
        prev=NULL;
        while(i<pos&&cur!=NULL)
        {
            prev=cur;
            cur=cur->next;
            i++;
        }
        if(cur==head)
        {
            cur=new Node<T>;
            cur->data=val;
            cur->next=head;
            head=cur;
        }
        else
        {
            cur=new Node<T>;
            cur->data=val;
            cur->next=prev->next;
            prev->next=cur;
        }
    }
    void Delete(T val)
    {
        Node<T>*cur,*prev;
        cur=head;
        while(cur!=NULL)
        {
            if(cur->data!=val)
            {
                prev=cur;
                cur=cur->next;
            }
            else
            {
                break;
            }
        }
            if(cur==head)
            {
                head=cur->next;
                delete cur;
            }
            else
            {
                prev->next=cur->next;
                delete cur;
            }
}    
};
int main()
{
        Linklist<int>ob;
        int ch,val,p;
        do
        {
            cout<<"1-insert,2-insertposition,3-search,4-delete,5-display\n";
            cout<<"enter your choice\n";
            cin>>ch;
            switch(ch)
            {
            case 1:
                cout<<"enter value\n";
                cin>>val;
                ob.insert(val);
                break;
            case 2:
                cout<<"enter position and value\n";
                cin>>val;
                cin>>p;
                ob.insertpos(val,p);
                break;
            case 3:
                cout<<"enter the searching value\n";
                cin>>val;
                ob.search(val);
                break;
            case 4:
                cout<<"enter the value\n";
                cin>>val;
                ob.Delete(val);
                break;
            case 5:
                cout<<"print the all elements\n";
                ob.display();
                break;
            }
        }while(ch!=6);
}