Q1) Our implementation of a doubly list relies on two sentinel nodes, header and trailer. Re-implement the DoublyLinkedList without using these nodes.

class DoublyLinkedList:

public class DoublyLinkedList {

public static class Node{

private E element;

private Node prev;

private Node next;

public Node(E e, Node p, Node n){

element = e;

prev = p;

next = n;

}

public E getElement() {

return element;

}

public Node getPrev() {

return prev;

}

public Node getNext() {

return next;

}

public void setPrev(Node p) {

next = p;

}

public void setNext(Node n) {

next = n;

}

}

private Node header;

private Node trailer;

private int size = 0;

public DoublyLinkedList(){

header = new Node<>(null,null,null);

trailer = new Node<>(null, header, null);

header.setNext(trailer);

}

public int size(){

return size;

}

public boolean isEmpty(){

return size ==0;

}

public E first(){

if(isEmpty())

return null;

return header.getNext().getElement();

}

public E last(){

if(isEmpty())

return null;

return trailer.getPrev().getElement();

} }