import java.util.LinkedList;

public class LL {
    private Node head;
    private Node tail;
    private int size;
    public LL(){
        this.size=0;
    }

    public void insertFront(int value){
        Node newNode = new Node(value);
        newNode.next = head;
        head = newNode;

       if(tail==null){
           tail = head;
       }
       size+=1;
    }

     public void insert(int value,int index){
        if(index==0){
            insertFront(value);
        }
        if(index==size){
            insertBack(value);
        }

        Node temp=head;
        for(int i=1;i<index;i++){
            temp=temp.next;

        }
        Node newNode = new Node(value);
        newNode.next = temp.next;
        temp.next = newNode;
     }

    public void insertBack(int value){
        if(tail==null){
            insertFront(value);
        }
        Node newNode = new Node(value);
        tail.next=newNode;
        tail = newNode;
        size+=1;


    }

    public int deleteFirst(){
        int val=head.value;
        head=head.next;
        if(head==null){
            tail=null;
        }
        size-=1;
        return val;
    }

    public int deleteLast(){
        if(size<=1){
            return deleteFirst();
        }
         Node secondlast=get(size-2);
         int val=tail.value;
         tail=secondlast;
         tail.next=null;
         return val;
    }

    public int deleteAtIndex(int index){
        if(index==0){
            return deleteFirst();
        }
        if(index==size-1){
            return deleteLast();
        }
        Node prev=get(index-1);
        int val=prev.next.value;
        prev.next=prev.next.next;
        return val;
    }
    public Node get(int index){
        Node node=head;
        for(int i=0;i<index;i++){
            node=node.next;
        }
        return node;
    }

    public Node find(int value){
        Node node=head;
        while(node!=null){
            if(node.value==value){
                return node;
            }
            node=node.next;
        }
        return null;
    }



    public void display(){
        Node temp=head;
        while(temp!=null){
            System.out.println(temp.value+"->");
            temp=temp.next;
        }
        System.out.println("END");
    }
    private class Node{
        private int value;
        private Node next;

        public Node(int value){
            this.value = value;
        }
        public Node(int value, Node next){
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LL list=new LL();
        list.insertFront(3);
        list.insertFront(5);
        list.insertFront(7);
        list.insertFront(9);
        System.out.println(list.find(5));
//        list.insertBack(10);
//        list.insert(11,2);
//        System.out.println(list.deleteFirst());
//        System.out.println(list.deleteLast());
        list.display();

//        System.out.println(list.deleteAtIndex(2));
    }
}