class Linkedlist{

    Node head;

    class Node{

        int val;
        Node next;

        Node(int v)
        {
            val=v;
            next=null;
        }

    }

    public void enqueue(int x)
    {
        Node newnode =new Node(x);

        if(head==null)
        {
            head=new Node(x);
            return;
        }

        newnode.next=null;

        Node cur=head;
        while(cur!=null)
        {
            cur=cur.next;
        }
        cur.next=newnode;
        return;
    }

    public int dequeue()
    {

        Node temp=head;

        head=head.next;
        temp.next=null;
        return temp.val;

    }

    public void printlist()
    {
        Node current=head;

        while(current!=null)
        {
            System.out.println(current.val);
            current=current.next;
        }

   }

    void insertAfterHead(int x)
    {
       Node newnode=new Node(x);

       if(head==null){
           head=newnode;
           return;
       }

       if(head.next==null){

           head.next=newnode;
           return;
       }

       Node current =head.next;
       head.next=newnode;

       while(current!=null)
       {
           current=current.next;


       }
       current.next=null;

    }

    void insertBeforeTail(int x)
    {
        Node newnode=new Node(x);
        Node cur=head;

        while(cur.next.next!=null)
        {
            cur=cur.next;

        }

        Node last=cur.next;

        newnode=cur.next;

        newnode.next=last;


    }
    void insertBeforeVal(int toFind, int toAdd)
    {

       Node newnode =new Node(toAdd);
       Node cur=head;

       while(cur!=null)
       {
           if(cur.next.val==toFind)
           {
               Node temp=cur;
               cur.next=newnode;
               newnode.next=temp;
               return;
           }
           cur=cur.next;
       }
    }

   void insertAfterVal(int toFind, int toAdd)
    {
       Node newnode =new Node(toAdd);
       Node cur=head;

       while(cur!=null)
       {
           if(cur.next.val==toFind)
           {
               Node temp=cur.next.next;
               cur.next.next=newnode;
               temp=newnode.next;
               return;
           }

           cur=cur.next;
       }
    }

    int deleteFromPos(int x)
    {
        Node cur=head;

        int i=0;

        while((i<x)&&(cur!=null))
        {

              cur=cur.next;
            i++;
        }

        Node temp=cur.next;
        cur.next=cur.next.next;
        return temp.val;

        }

    void  deleteVal(int x)
    {
        Node cur=head;
        while(cur!=null)
        {
            if(cur.next.val==x)
            {

              cur.next=cur.next.next;

            }

          }

    }

    int deleteHead()
    {
        Node temp=head;

        head=head.next;

        return temp.val;
    }

     int deleteTail(){

         Node cur=head;

         while(cur.next.next!=null)
         {

             cur=cur.next;
         }

         Node temp=cur.next;

         cur.next=null;

         return temp.val;
     }

     int deleteValAfterHead()
     {
         if(head==null)
             System.out.println("Underflow");

         if(head.next==null)
             head=null;


         Node temp=head.next;
         head.next=head.next.next;
         return temp.val;



     }


    int deleteValBeforeTail()
    {
        if(head==null)
            System.out.println("Underflow");
        if(head.next==null)
            head=null;






        Node cur=head;

        while(cur.next.next.next!=null)
        {

            cur=cur.next;

        }

        Node temp=cur.next;
        cur.next=cur.next.next;
        return temp.val;
    }






}