import java.util.Scanner;
public class DLinkedL {
    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 = 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, int key){
        Node newNode = new Node(data);
        Node ptr = head;
        if(head == null){
            addNode(data);
        }else{
            while(ptr != null){
                if(ptr.data == key){
                    newNode.llink = ptr;
                    newNode.rlink = ptr.rlink;
                    if(ptr.rlink != null){
                        ptr.rlink.llink = newNode;
                    }
                    ptr.rlink = newNode;
                    return;
                }
                ptr = ptr.rlink;
            }
            if(ptr==null){
                System.out.println("Key Not Found.");
            }
        }
    }

    //DELETION OF NODES.

     public void delete(int key){
        Node ptr = head;
        if(ptr == null){
            System.out.println("Empty Set.");
            return;
        }
        while(ptr != null && ptr.data != key){
            ptr = ptr.rlink;
        }
        if (ptr == null) {
            System.out.println("Key not found in the list.");
            return;
        }
        if(ptr == head){
            head = head.rlink;
            return;
        }
        if(ptr == tail){
            tail.llink.rlink = null;
            return;
        }
        ptr.llink.rlink = ptr.rlink;
        ptr.rlink.llink = ptr.llink;
    }

    public void display(){
        Node temp = head;
        if(temp == null){
            System.out.println("No Elements in the Set.");
        }
        while(temp != null){
            System.out.println(temp.data);
            temp = temp.rlink;
        }
    }



    public static void main(String[] args){
        Scanner input =  new Scanner(System.in);
        DLinkedL obj = new DLinkedL();
        int data;
        int key;
        int ch = 0;
        while(ch != 6){ 
            System.out.println("1.Inserion at front \n2.Insertion at middle \n3.Insertion at end \n4.Deletion \n5.Display \n6.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 key: ");
                key = input.nextInt();
                System.out.println("Enter the data: ");
                data = input.nextInt();
                obj.addNodemiddle(data, key);
            }else if(ch == 3){
                System.out.println("Enter the data: ");
                data = input.nextInt();
                obj.addNodeend(data);
            }else if(ch == 4){
                System.out.println("Enter the element to delete: ");
                data = input.nextInt();
                obj.delete(data);
            }else if(ch == 5){
                obj.display();
            }else if(ch == 6){
                System.exit(0);
            }
            else{
                System.out.println("Invalid Choice.");
            }
                 
        }
        input.close();
    }
    
}