import java.io.*;
class Node
{
    int data;
    Node next;
    public Node(int d)
    {
        next=null;
        data=d;
    }
    public Node(int d,Node n)
    {
        next=n;
        data=d;
    }
    public void set_data(int d)
    {
        data=d;
    }
    public int get_data()
    {
        return data;
    }
    public void set_next(Node d)
    {
        next=d;
    }
    public Node get_next()
    {
        return next;
    }
}

//implimenting linked list class
class Linkedlist
{
    Node head;
    public Linkedlist()
    {
    head=null;
    }
    public void add(int pos,Node n)
    {
    //pos is the position
    //0 is at the beginning
    if(pos==0)
    {
        if(head==null)
        head=n;
        else
        {
        Node temp=new Node(n.get_data(),head);
        head=temp;
        }
    }
    else
    {
        Node temp=head;
        int count=1;
        int flagfound=0;
        while(temp.get_next()!=null)
        {
            if(count==pos)
            {
                flagfound=1;
                break;
            }
            count++;
            temp=temp.get_next();
        }
        if(flagfound==0)
        {
            System.out.println("problem");
        }
        else
        {
            Node temp1=temp.get_next();
            temp.set_next(n);
            n.set_next(temp1);
        }
    }
    }
    //finished add method
    public void del(int d)
    {
        Node temp=head;
        //check if list is empty
        if(head==null)
        {
            System.out.println("List is empty");
            return;
        }
        //if first node
        if(temp.get_data()==d)
        {
        head=head.get_next();
        return;
        }
        //else if not the first node
        int flag=0;
        while(temp.get_next()!=null)
        {
            if(temp.get_next().get_data()==d)
            {
                flag=1;
                break;   
            }
            else
            {
                temp=temp.get_next();
            }
        }
        if(flag==1)
        {
            Node temp2=temp.get_next().get_next();
            temp.set_next(temp2);
        }
        else
        System.out.println("not found");
    }
    //finished del method

    public void search(int d)
    {
        Node temp=head;
        if(head==null)
        {
            System.out.println("List is empty");
            return;
        }
        //if first node
        int count=1;
        if(head.get_data()==d)
        {
            System.out.println("Node found. Node number= "+count);
            return;
        }
        int flag=0;
        while(temp.get_next()!=null)
        {
            temp=temp.get_next();   
            count++;
            if(temp.get_data()==d)
            {
                flag=1;
                System.out.println("Node found. Node number= "+count);
            }
        }
        if(flag==0)
        {
        System.out.println("Not found in list");
        }
       
    }
    //writing update method
   
    public void update(int olddata,int newdata)
    {
        Node temp=head;
                if(head==null)
                {
                        System.out.println("List is empty");
                        return;
                }
                //if first node
                int count=1;
                if(head.get_data()==olddata)
                {
                        System.out.println("Node found. Node number= "+count);
            head.set_data(newdata);
                        return;
                }
                int flag=0;
                while(temp.get_next()!=null)
               {
                        temp=temp.get_next();
                        count++;
                        if(temp.get_data()==olddata)
                        {
                                flag=1;
                temp.set_data(newdata);
                                System.out.println("Node found. Node number= "+count);
                        }
                }
        if(flag==0)
        System.out.println("node not found");
    }
   
    //writing display method
    public void display()
    {
        //if empty
        if(head==null)
        System.out.println("empty list");   
        else
        {
            Node temp=head;
            System.out.println("Printing the list:");
            System.out.print(head.get_data()+", ");
            while(temp.get_next()!=null)
            {
                temp=temp.get_next();
                System.out.print(temp.get_data()+", ");
            }
        }
    }
}

class check
{
    public static void main(String[] args)throws IOException
    {
        InputStreamReader isr=new InputStreamReader(System.in);
        BufferedReader br=new BufferedReader(isr);
        //create a linkedlist
        Linkedlist ll=new Linkedlist();
        while(true)
        {
        System.out.println("\nWelcome to world of linked lists.Choose an option :");
        System.out.println("1. add(data,pos);");
        System.out.println("2. delete(int d)");
        System.out.println("3. search(int d);");
        System.out.println("4. update(int old,int new)");
        System.out.println("5. display");
        System.out.println("6. exit");
        int n1,n2;
        int ch=Integer.parseInt(br.readLine());
        switch(ch)
        {
        case 1:System.out.println("Enter the data and then pos");
            n1=Integer.parseInt(br.readLine());
            n2=Integer.parseInt(br.readLine());
            Node nn=new Node(n1);
            ll.add(n2,nn);
            break;
        case 2:System.out.println("Enter data");
            n1=Integer.parseInt(br.readLine());
            ll.del(n1);
            break;
        case 3:System.out.println("Enter data");
             n1=Integer.parseInt(br.readLine());
            ll.search(n1);
            break;
        case 4:System.out.println("Enter old data and then new data");
             n1=Integer.parseInt(br.readLine());
             n2=Integer.parseInt(br.readLine());
            ll.update(n1,n2);
            break;
        case 5:ll.display();
            break;
        case 6:System.exit(500);
        default: System.out.println("wrong option try again");
        }
        }
    }
}