import java.util.Scanner;
public class doubly {
    Scanner input = new Scanner(System.in);
    class Node{
        int data;
        Node rlink;
        Node llink;
        Node(int data){
            this.data = data;
        }
    }

    public Node head = null;
    public Node tail = null;

    //INSERTION OF NODES.

    public void addNode(int data){
        Node newNode = new Node(data);
        if(head == null){
            head = newNode;
            tail = newNode;
        }
    }

    public void addNodefront(int data){
        Node newNode = new Node(data);
        if(head == null){
            addNode(data);
        }else{
            newNode.rlink = head;
            head.llink = newNode;
            head = newNode;
        }
    }

    public void addNodeend(int data){
        Node newNode = new Node(data);
        if(head == null){
            addNode(data);
            return;
        }else{
            tail.rlink = newNode;
            newNode.llink = tail;
        }
        tail = newNode;
    }

    public void addNodemiddle(int data){
        Node newNode = new Node(data);
        Node ptr = head;
        if(head == null){
            addNode(data);
        }else{
            System.out.println("Enter the key: ");
            int key = input.nextInt();
            while(ptr != null){
                if(ptr.data == key){
                    newNode.llink = ptr;
                    newNode.rlink = ptr.rlink;
                    ptr.rlink.llink = newNode;
                    ptr.rlink = newNode;
                    return;
                }
                ptr = ptr.rlink;
            }
        }
    }

    //DELETION OF NODES.

    public void deleteFront(){
        Node ptr = head;
        if(ptr == null){
            System.out.println("Empty set.");
            return;
        }
        if(ptr != null){
            head = head.rlink;
            head.llink = null;
        }
    }

    public void deleteEnd(){
        if(head == null){
            System.out.println("Empty Set");
            return;
        }else{
            tail.llink.rlink = null;
        }

    }

    public void deleteMiddle(){
        Node ptr = head;
        if(ptr == null){
            System.out.println("Empty Set.");
            return;
        }
        System.out.println("Enter the key.");
        int key = input.nextInt();
        while(ptr != null && ptr.data != key){
            ptr = ptr.rlink;
        }
        if(ptr == head){
            deleteFront();
            return;
        }
        if(ptr == tail){
            deleteEnd();
            return;
        }
        ptr.llink.rlink = ptr.rlink;
        ptr.rlink.llink = ptr.llink;
    }

    public void display(){
        Node temp = head;
        while(temp != null){
            System.out.println(temp.data);
            temp = temp.rlink;
        }
    }



    public static void main(String[] args){
        Scanner input =  new Scanner(System.in);
        doubly obj = new doubly();
        int data;
        int ch = 0;
        while(ch != 8){ 
            System.out.println("1.Inserion at front \n2.Insertion at middle \n3.Insertion at end \n4.Deletion at front \n5.Deletion at middle \n6.Deletion at end \n7.Display \n8.Exit Operaton \nEnter your choice below: ");
            ch = input.nextInt();
            if(ch == 1){
                System.out.println("Enter the data: ");
                data = input.nextInt();
                obj.addNodefront(data);
            }else if(ch == 2){
                System.out.println("Enter the data: ");
                data = input.nextInt();
                obj.addNodemiddle(data);
            }else if(ch == 3){
                System.out.println("Enter the data: ");
                data = input.nextInt();
                obj.addNodeend(data);
            }else if(ch == 4){
                obj.deleteFront();
            }else if(ch == 5){
               obj.deleteMiddle();
            }else if(ch == 6){
                obj.deleteEnd();
            }else if(ch == 7){
                obj.display();
            }else if(ch == 8){
                System.exit(0);
            }else{
                System.out.println("Invalid Choice.");
            }
                 
        }
        input.close();
    }
}