/** Insert the given element at the beginning of the list, returning
    * the new position; O(1) time  */
  public Position insertFirst(Object element) {
    numElts++;
    DNode newNode = new DNode(header, header.getNext(), element);
    header.getNext().setPrev(newNode);
    header.setNext(newNode);
    return newNode;
  }
  /**Remove the given position from the list; O(1) time */
  public Object remove(Position p)
      throws InvalidPositionException {
    DNode v = checkPosition(p);
    numElts--;
    DNode vPrev = v.getPrev();
    DNode vNext = v.getNext();
    vPrev.setNext(vNext);
    vNext.setPrev(vPrev);
    Object vElem = v.element();
    // unlink the position from the list and make it invalid
    v.setNext(null);
    v.setPrev(null);
    return vElem;
  }
  /** Replace the element at the given position with the new element
    * and return the old element; O(1) time  */
  public Object replace(Position p, Object element)
      throws InvalidPositionException {
    DNode v = checkPosition(p);
    Object oldElt = v.element();
    v.setElement(element);
    return oldElt;
  }