You are NOT allowed to use JAVA API Container classes!!!! READ before coding!!!

Implement a generic Deque $($double ended queue$)$ based on a DoublyLinkedList. Deque is an ADT that allows use to add or remove element from either the front or the back of the Deque. Implement the following methods to your MyDeque class; insert element at back, insert element at front, remove last element, remove first element. Both remove methods should return the element being removed. Size is NOT an attribute of this class. Use the given generic Node class that allows you to build the DoublyLinkedList for MyDeque, and test your MyDeque with the given main method. All classes must be in a single Java program called MyDeque.java.

Copy and paste the code below on to a program named MyDeque.java. Write the $4$ methods, paste output on the bottom of the source program, finally attach the program to this question. Do not change the Node class or the main method.

public class MyDeque$\{$

$//$implement the rest of the code.

$\}$

class Node $\{$

E element;

Node prev;

Node next;

public Node$($E e$)\{$ element $=$ e;$\}$

$\}$

public static void main$($String$[]$ args$)\{$

MyDeque dq $=$ new MyDeque$<>()$;

System.out.println$("$Removing back value $"+$ dq$.$removeBack$())$;

System.out.println$("$Removing front value $"+$ dq$.$removeFront$())$;

dq$.$insertBack$(23)$;

dq$.$insertBack$(34)$;

System.out.println$("$Removing front value $"+$ dq$.$removeFront$())$;

dq$.$insertBack$(55)$;

dq$.$insertFront$(12)$;

dq$.$insertFront$(17)$;

System.out.println$("$Removing front value $"+$ dq$.$removeFront$())$;

System.out.println$("$Removing Back value $"+$ dq$.$removeBack$())$;

System.out.println$("$Removing front value $"+$ dq$.$removeFront$())$;

System.out.println$("$Removing Back value $"+$ dq$.$removeBack$())$;

System.out.println$("$Removing Back value $"+$ dq$.$removeBack$())$;

System.out.println$("$Removing front value $"+$ dq$.$removeFront$())$;

$\}$