import java.util.*;
class Node{
    int info;
    Node next;
    Node prev;
}
public class DLinkedList
{




    static Node create(Node start,Node end){
            Node p;
            Scanner sc=new Scanner(System.in);
            System.out.println(" Enter the node info:");
            start.info=sc.nextInt();

            start.prev=start.next=null;
            System.out.println("Do u want to add new node Yes-1/No-0 \n");
            int option=sc.nextInt();
            while(option != 0 )
                   {
                    p=new Node();
                    System.out.println("Enter the node info");
                    p.info=sc.nextInt();
                    p.prev=p.next=null;
                    p.prev=end;
                    end.next=p;
                    end=p;
                    System.out.println("Do u want to add new node Yes-1/No-0 \n");
                    option=sc.nextInt();
                    }

            return end;



}




    static void display(Node start,Node end)
   {
            Node p=start;
            while(p!=null)
            {
                    System.out.println(p.info);
                    p=p.next;
            }
    }


    static Node InsertBeg(Node start, Node end)
    {
            Scanner sc=new Scanner(System.in);
            Node p=new Node();
            System.out.println("Enter the node info");
            p.info=sc.nextInt();

            p.prev=null;
            p.next=start;
            start.prev=p;
            start=p;
            return start;
    }


    static Node InsertEnd(Node start, Node end)
    {
            Scanner sc=new Scanner(System.in);
            Node p=new Node();
            System.out.println("Enter the node info");
            p.info=sc.nextInt();

            p.next=null;
            p.prev=end;
            end.next=p;
            end=p;
            return end;
    }
    static Node InsertAny(Node start, Node end){
            Scanner sc=new Scanner(System.in);
            System.out.println("Enter the index/location where to insert:");
            int loc=sc.nextInt();
            int count=1;
            Node  p=start;
            while(( p!=null)&&(count<(loc-1))){
                     p= p.next;count++;
                    }
            if( p==null) System.out.println("Too high index");
            else{
            Node curr=new Node();
            System.out.println("Enter the node info");
            curr.info=sc.nextInt();

            curr.next=curr.prev=null;
            curr.next= p.next;
             p.next.prev=curr;
            curr.prev= p;
             p.next=curr;
            }
            return end;
    }

    static Node DeleteBeg(Node start,Node end)
    {
            start.next.prev=null;
            start=start.next;
            return start;
    }

    static Node DeleteEnd(Node s,Node end)
    {
            e.prev.next=null;
            end =end.prev;
            return end;
    }

    static Node DeleteAny(Node start,Node end)
            {
            Scanner sc=new Scanner(System.in);
            Node p=start;
            System.out.println("Enter the node info to delete");
            int item=sc.nextInt();
            while(p!=null && p.info!=item)
                    p=p.next;
            if(p==null) System.out.println("Node not found");
            else{
                    p.prev.next=p.next;
                    p.next.prev=p.prev;
            }
            return start;
    }


    static void Search(Node start)
    {
            Scanner sc=new Scanner(System.in);
            System.out.println("Enter the node info to search");
            int roll=sc.nextInt();
            while(start!=null && start.info!=roll){
                    if(start.info==roll) break;
                    else start=start.next;
                    }
            if(start==null) System.out.println("node not present");
            else System.out.println("node is present");
    }


    public static void main(String[] args)
            {
            Scanner sc=new Scanner(System.in);
            Node start=new Node();
            Node end=start;
            while(true){
            System.out.println("*********************MENU(Doubly Linked List)***************************");
            System.out.println("0: Exit");
            System.out.println("1: Creation");
            System.out.println("2: Display");
            System.out.println("3: Insert at the begenning");
            System.out.println("4: Insert at the end");
            System.out.println("5: Insert at any location");
            System.out.println("6: Delete the first node");
            System.out.println("7: Delete the last node");
            System.out.println("8: Delete any node");
            System.out.println("9: Search a node");
            System.out.println("Enter your choice");
            int choice=sc.nextInt();
            switch(choice){
            case 0:    System.exit(0);
            case 1:
                    end=create(start,end);
                    break;
            case 2:
                    display(start,end);
                    break;
            case 3:
                    start=InsertBeg(start,end);
                    break;
            case 4:
                    end=InsertEnd(start,end);
                    break;
            case 5:
                    end=InsertAny(start,end);
                    break;
            case 6:
                    start=DeleteBeg(start,end);
                    break;
            case 7:
                    end=DeleteEnd(start,end);
                    break;
            case 8:
                    start=DeleteAny(start,end);
                    break;
            case 9:
                    Search(start);
                    break;
            default:
                    System.out.println("Wrong choice");
                    }
            }
    }

}