Doubly Linked List - Data Structure

One natural characteristic of singly linked list (SLL)is that it is asymmetric. Meaning a node only knows its next node. In doubly linked list (DLL) a node can refer to its previous and next nodes.

Image obtained from : http://www.cs.usfca.edu/~srollins/courses/cs112-f07/web/notes/linkedlists/ll5.gif

In DLL we need 2 sentinels (Dummy nodes) for header and trailer.

Initially empty list is created so that,
header.next -----points to ------>  trailer
trailer.prev -----points to -------> header

header and trailer sentinels(dummy nodes) never change. Their next and prev changes with the intermediate nodes.


Doubly linked lists implementation - for illustration purposes



private static class Node<E> {
  private E element;
  private Node<E> prev;          // this the only additional reference comparing with singly linked list 
  private Node<E> next;

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


public class DoublyLinkedList<E> {

  private Node<E> header;   // header and trailer sentimental for setting up the boundary of the list
  private Node<E> trailer;
  private int size = 0;


public DoublyLinkedList( ) {
  header = new Node<>(null, null, null);      // initiall creates an emptry list where header and trailer
  trailer = new Node<>(null, header, null);   // sentinels are referred to each other
  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( );
}


public void addFirst(E e) {
  addBetween(e, header, header.getNext( ));    // adds e node between header and header.next
 }


public void addLast(E e) {
  addBetween(e, trailer.getPrev( ), trailer);     // add e node between trailer and trailer.prev
}


public E removeFirst( ) {
  if (isEmpty( )) return null;                       // cant remove node from an empty list
  return remove(header.getNext( ));          
}


public E removeLast( ) {
  if (isEmpty( )) return null;
  return remove(trailer.getPrev( ));
}


private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
  
  // newest node's next and previous is set to left side and right side nodes
  Node<E> newest = new Node<>(e, predecessor, successor);
 // left sides nodes next is set to newest node
  predecessor.setNext(newest);
  //right side nodes previous is set to newest node
  successor.setPrev(newest);
  size++;
}

private E remove(Node<E> node) {
  Node<E> predecessor = node.getPrev( );    // Temporary predecessor and successor is set
  Node<E> successor = node.getNext( );       //  their next and prev is set to each other
  predecessor.setNext(successor);                 //
  successor.setPrev(predecessor);                  //
  size−−;
  return node.getElement( );
}