/** An instance is a doubly linked list with head and tail */
public class DoublyLinkedList {
    ListNode head; // the header node of this doubly linked list.
                   // head.prev = null, always
    ListNode tail; // the tail node of this doubly linked list
                   // tail.next = null, always
    int size;      // number of nodes in this doubly linked list
    
    /** Constructor: an empty linked list */
    public DoublyLinkedList() {
        head= new ListNode(null, null, null);
        tail= new ListNode(head, null, null);
        head.next= tail;
        size= 0;
    }
    
    /** = the linked list is empty */
    public boolean isEmpty() 
        {  return size == 0;  }

    /** Remove all items from this linked list */
    public void makeEmpty() {
        head.next= tail;
        tail.prev= head;
        size= 0;
    }
    
    /** = size of this linked list */
    public int size() 
        {  return size;  }
        
    /** = the first node in the list (tail if none) */
    public ListNode first() 
        {  return head.next;  }
    
    /** = the last node in the list (head if none) */
    public ListNode last() 
        {  return tail.prev;  }
    
    /** = "p is valid --is not one of head and last" */
    public boolean isValid(ListNode p) 
        {  return p != head && p != tail; }

    /** = "a node of the list follows p" */
    public boolean hasNext(ListNode p) 
        {  return p != tail && p.next != tail;  }
   
    
    /** = "a node of the list precedes p" */
    public boolean hasPrec(ListNode p) 
        {  return p != head && p.prev != head;  }
    
    /** = the node following node p (null if p is the tail)
          Precondition: p is not null */
    public ListNode next(ListNode p) 
        {  return p.next;  }

    /** = the node preceding node p (null if p is the head) 
          Precondition: p is not null*/
    public ListNode prev(ListNode p) 
        {  return p.prev;  }
    
    /** if p is not tail, insert object x after node p. */
    public void insert(Object x, ListNode p) {
        if (p == tail)
            return; 
        ListNode n= new ListNode(p, x, p.next);
        p.next.prev= n;
        p.next= n;
        size= size+1;
    }
        
    /** if p is not head or tail, delete node p from the list.  */
    public void delete(ListNode p) {
        if (!isValid(p))
            return;
        p.prev.next= p.next;
        p.next.prev= p.prev;
        size= size-1;
    }   
 
    /** = a string that contains the elements of the list separated
          by commas and enclosed in "(" ")".
      */
    public String toString() {
        String s= "(";
        ListNode c= head.next;
        while (c != tail) {
            s= s + c.element;
            c= c.next;
            if (c != tail)
                s= s + ", ";
        }
        return s + ")";
    }
       
}