// Double Linked List

public class List {
  ListNode _head;

  public List() {
    _head = new ListNode();
  }

  // Add a node to the front of list
  public void addToFront( ListNode newNode ) {
    newNode.setNext( _head.getNext() );
    newNode.setPrevious( _head );
    _head.getNext().setPrevious( newNode );
    _head.setNext( newNode );
  }

  // Add a node to the back of the list
  public void addToTail( ListNode newNode ) {
    newNode.setNext( _head );
    newNode.setPrevious( _head.getPrevious() );
    _head.getPrevious().setNext( newNode );
    _head.setPrevious( newNode );
  }

  // Remove node from front. Return null if empty
  public ListNode removeFront() {
    if ( isEmpty() ) {
      return null;
    }

    ListNode tmp = front();
    tmp.unlink();

    return tmp;
  }

  // Remove node from tail. Return null if empty
  public ListNode removeTail() {
    if ( isEmpty() ) {
      return null;
    }

    ListNode tmp = tail();
    tmp.unlink();

    return tmp;
  }

  // Return true if list is empty and false otherwise.
  public boolean isEmpty() {
    return _head.getNext() == _head;
  }

  // Return head of double linked list
  public ListNode head() {
    return _head;
  }

  // Return node at front without removing it
  // Return null if list is empty
  public ListNode front() {
    if ( isEmpty() ) {
      return null;
    }

    return _head.getNext();
  }

  // Return node at tail without removing it
  // Return null if list is empty
  public ListNode tail() {
    if ( isEmpty() ) {
      return null;
    }

    return _head.getPrevious();
  }

  // Clear list
  public void clear() {
    _head.setNext( _head );
    _head.setPrevious( _head );
  }

  // Appends the elements of "other" at the end of "this". 
  // "other" becomes empty.
  public void append( List other ) {
    other._head.getNext().setPrevious( this._head.getPrevious() );
    other._head.getPrevious().setNext( this._head );
    this._head.getPrevious().setNext( other._head.getNext() );
    this._head.setPrevious( other._head.getPrevious() );

    other.clear();
  }

};