Question

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

I want the answer to be a text not on a paper please

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();

}
}

Answer 1

I have modified the code not to use sentinel nodes. Since the add() method was missing, I have created a new method to add objects to the list.

public class DoublyLinkedList<E> {
   public static class Node<E> {
       private E element;
       private Node<E> prev;
       private Node<E> next;

       public Node(E e, Node<E> p, Node<E> n) {
           element = e;
           prev = p;
           next = n;
       }

       public E getElement() {
           return element;
       }

       public Node<E> getPrev() {
           return prev;
       }

       public Node<E> getNext() {
           return next;
       }

       public void setPrev(Node<E> p) {
           next = p;
       }

       public void setNext(Node<E> n) {
           next = n;
       }
   }

   private Node<E> first;
   private Node<E> last;
   private int size = 0;

   public DoublyLinkedList() {
       first = null;
       last = null;
   }

   public int size() {
       return size;
   }

   public boolean isEmpty() {
       return size == 0;
   }

   public E first() {
       if (isEmpty())
           return null;
       return first.getElement();
   }

   public E last() {
       if (isEmpty())
           return null;
       return last.getElement();
   }
  
  
   public void add(E obj) {
       Node<E> n = new Node<E>(obj, last, null);
       if(isEmpty()) {
           first = last = n;
       }
       else {
           last.next = n;
           last = n;
       }
      
       size++;
   }
}