public class DequeReferenceBased<E> implements DequeInterface<E>{

    private DoubleNode<E> head;
    private DoubleNode<E> tail;

    public DequeReferenceBased(){
	head = null;
	tail = null;
    }

    public boolean isEmpty(){
	return head == null;
    }

    public E peekFirst(){
	if (isEmpty())
	    throw new DequeException ("attempt to peekFirst from an "
						   + "empty deque");
	return head.getItem();
    }

    public E removeFirst(){
	if (isEmpty())
	    throw new DequeException ("attempt to removeFirst from an "
				      + "empty deque");
	E ret = head.getItem();
	head = head.getNext();
	if (head == null)
	    tail = null;
	else
	    head.setPrev(null);
	return ret;
    }

    public void addFirst(E newItem){
	head = new DoubleNode<E> (newItem, null, head);
	if (head.getNext() == null)
	    tail = head;
	else
	    head.getNext().setPrev(head);
    }

    public E peekLast(){
	if (isEmpty())
            throw new DequeException ("attempt to peekLast from an "
                                      + "empty deque");
	return tail.getItem();
    }

    public E removeLast(){
	if (isEmpty())
            throw new DequeException ("attempt to removeLast from an "
                                      + "empty deque");
	E ret = tail.getItem();
	tail = tail.getPrev();
	if (tail == null)
	    head = null;
	else
	    tail.setNext(null);
	return ret;
    }

    public void addLast(E newItem){
	tail = new DoubleNode<E> (newItem, tail, null);
	if (tail.getPrev() == null)
	    head = tail;
	else
	    tail.getPrev().setNext(tail);
    }

    public void removeAll(){
	head = null;
	tail = null;
    }
}