/** Doubly linked list with nodes of type DNode storing strings. */
public class DList {
  protected int size;			// number of elements
  protected DNode header, trailer;	// sentinels
  /** Constructor that creates an empty list */
  public DList() { 
    size = 0;
    header = new DNode(null, null, null);	// create header
    trailer = new DNode(null, header, null);	// create trailer
    header.setNext(trailer);	// make header and trailer point to each other
  }
  /** Returns the number of elements in the list */
  public int size() { return size; }
  /** Returns whether the list is empty */
  public boolean isEmpty() { return (size == 0); }
  /** Returns the first node of the list */
  public DNode getFirst() throws IllegalStateException {
    if (isEmpty()) throw new IllegalStateException("List is empty");
    return header.getNext();
  }
  /** Returns the last node of the list */
  public DNode getLast() throws IllegalStateException {
    if (isEmpty()) throw new IllegalStateException("List is empty");
    return trailer.getPrev();
  }
  /** Returns the node before the given node v. An error occurs if v
    * is the header */
  public DNode getPrev(DNode v) throws IllegalArgumentException {
    if (v == header) throw new IllegalArgumentException
      ("Cannot move back past the header of the list");
    return v.getPrev();
  }
  /** Returns the node after the given node v. An error occurs if v
    * is the trailer */
  public DNode getNext(DNode v) throws IllegalArgumentException {
    if (v == trailer) throw new IllegalArgumentException
      ("Cannot move forward past the trailer of the list");
   return v.getNext();
  }