title: Java Deque Implementation
body: <p>Java newbie question: I'm trying to implement a deque in Java and am having issues with the dequeueBack (remove an element from the rear of the queue) and enqueueFront (add an element to the front of the queue) methods. I've gotten the opposite methods to work (dequeueFront and enqueueBack), but I'm stumped at this point. Any suggestions?</p>
  
  <pre><code>public class Carr_A06Q4
  {
  /**
   * Program entry point for deque testing.
   * @param args Argument list.
   */    
  public static void main(String[] args)
  {
      LinkedDequeue&lt;Integer&gt; deque = new LinkedDequeue&lt;Integer&gt;();
  
      System.out.println("DEQUE TESTING");
  
      //per Q1
      deque.enqueueBack(3);
      deque.enqueueBack(7);
      deque.enqueueBack(4);
      deque.dequeueFront();        
      deque.enqueueBack(9);
      deque.enqueueBack(8);
      deque.dequeueFront();
      System.out.println("The size of the deque is: " + deque.size());
      System.out.println("The deque contains:\n" + deque.toString());   
  
      //new features
      System.out.println(deque.dequeueFront());
      deque.enqueueFront(1);
      deque.enqueueFront(11);                         
      deque.enqueueFront(3);                 
      deque.enqueueFront(5);
      System.out.println(deque.dequeueBack());
      System.out.println(deque.dequeueBack());        
      System.out.println(deque.last());
      deque.dequeueFront();
      deque.dequeueFront();
      System.out.println(deque.first());        
      System.out.println("The size of the deque is: " + deque.size());
      System.out.println("The deque contains:\n" + deque.toString());            
  }
  
  /**
   * LinkedDeque represents a linked implementation of a deque.
   * 
   */
  public static class LinkedDequeue&lt;T&gt; implements DequeADT&lt;T&gt;
  {
      private int count;
      private LinearDoubleNode&lt;T&gt; head, tail; //front, back
  
      /**
       * Creates an empty queue.
       */
      public LinkedDequeue()
      {
          count = 0;
          head = tail = null;
      }
  
      /**
       * Adds the specified element to the tail of this queue.
       * @param element the element to be added to the tail of the queue
       */
      public void enqueueBack(T element)
      {
          LinearDoubleNode&lt;T&gt; node = new LinearDoubleNode&lt;T&gt;(element);
  
          if (isEmpty())
              head = node;
          else
              tail.setNext(node);
  
          tail = node;
          count++;
      }
  
      /**
       * Adds the specified element to the head of this queue.
       * @param element the element to be added to the head of the queue
       */
      public void enqueueFront(T element)
      {
          LinearDoubleNode&lt;T&gt; node = new LinearDoubleNode&lt;T&gt;(element);
  
          count++ ;    
          if (head == null) 
          {
              head = node;
          }
          else 
          {
              node.setNext(head);
              head = node;
          }
      }
  
      /**
       * Removes the element at the head of this queue and returns a
       * reference to it. 
       * @return the element at the head of this queue
       * @throws EmptyCollectionException if the queue is empty
       */
      public T dequeueFront() throws EmptyCollectionException
      {
         if (isEmpty())
              throw new EmptyCollectionException("queue");
  
          T result = head.getElement();
          head = head.getNext();
          count--;
  
          if (isEmpty())
              head = null;
  
          return result;
      }
  
      /**
       * Removes the element at the tail of this queue and returns a
       * reference to it. 
       * @return the element at the tail of this queue
       * @throws EmptyCollectionException if the queue is empty
       */
      public T dequeueBack() throws EmptyCollectionException
      {
          if (isEmpty())
              throw new EmptyCollectionException("queue");
  
          T result = tail.getElement();
          tail = tail.getNext();
  
          if (isEmpty())
              head = null;
          count --;
  
          return result;
      }
  
      /**
       * Returns a reference to the element at the head of this queue.
       * The element is not removed from the queue.  
       * @return a reference to the first element in this queue
       * @throws EmptyCollectionsException if the queue is empty
       */
      public T first() throws EmptyCollectionException
      {
          if (isEmpty())
              throw new EmptyCollectionException("stack");
  
          T result = head.getElement();
          return result;
      }
  
      /**
       * Returns a reference to the element at the tail of this queue.
       * The element is not removed from the queue.  
       * @return a reference to the first element in this queue
       * @throws EmptyCollectionsException if the queue is empty
       */
      public T last() throws EmptyCollectionException
      {
          if (isEmpty())
              throw new EmptyCollectionException("stack");
  
          T result = tail.getElement();
          return result;
      }
  
      /**
       * Returns true if this queue is empty and false otherwise. 
       * @return true if this queue is empty 
       */
      public boolean isEmpty()
      {
          if (head == null)
          {
              return true;
          }
          else
          {
              return false;
          }
      }
  
      /**
       * Returns the number of elements currently in this queue.
       * @return the number of elements in the queue
       */
      public int size()
      {
          return count;
      }
  
      /**
       * Returns a string representation of this queue. The front element
       * occurs first, and each element is separated by a space. If the
       * queue is empty, returns "empty".
       * @return the string representation of the queue
       */
      public String toString()
      {
          StringBuilder sb = new StringBuilder();
         LinearDoubleNode&lt;T&gt; tmp = head;
         while (tmp != null)
         {
          sb.append(tmp.getElement()).append(" ");
          tmp = tmp.getNext();
         }
         return sb.toString();
      }
  }
  </code></pre>
  
  <p>}</p>
  
  <p><strong>I need to get an output of:</strong></p>
  
  <p>DEQUE TESTING:
  The size of the deque is: 3
  The deque contains:</p>
  
  <p>498</p>
  
  <p>4</p>
  
  <p>8</p>
  
  <p>9</p>
  
  <p>1</p>
  
  <p>11</p>
  
  <p>The size of the deque is: 2
  The deque contains:
  11 1</p>
  
  <p><strong>But instead I'm getting:</strong></p>
  
  <p>DEQUE TESTING:
  The size of the deque is: 3
  The deque contains:</p>
  
  <p>498</p>
  
  <p>4</p>
  
  <p>8</p>
  
  <p>and then I get a NullPointerException in the dequeueBack method.</p>
  
  <p>Any help is appreciated!</p>
  
  <p>Also, the interface is:</p>
  
  <pre><code>public interface DequeADT&lt;T&gt;
  {
  /**  
   * Adds one element to the front of this deque. 
   * @param element the element to be added to the front of the deque  
   */
  public void enqueueFront(T element); //deque specific
  
  /**  
   * Adds one element to the back of this deque. 
   * @param element the element to be added to the back of the deque  
   */
  public void enqueueBack(T element);
  
  /**  
   * Removes and returns the element at the front of this deque.
   * Should throw an exception if the deque is empty.
   * @return the element at the front of this deque
   */
  public T dequeueFront();
  
  /**  
   * Removes and returns the element at the back of this deque.
   * Should throw an exception if the deque is empty.
   * @return the element at the back of the deque. 
   */
  public T dequeueBack(); //deque specific  
  
  /**  
   * Returns, without removing, the element at the front of this deque.
   * Should throw an exception if the deque is empty.
   * @return the first element in the deque
   */
  public T first();
  
  /**  
   * Returns, without removing, the element at the back of this deque.
   * Should throw an exception if the deque is empty.
   * @return the last element in the deque
   */
  public T last(); //deque specific  
  
  /**  
   * Returns true if this deque is empty and false otherwise.
   * @return true if this deque is empty
   */
  public boolean isEmpty();
  
  /**  
   * Returns the number of elements in this deque. 
   * @return the number of elements in the deque
   */
  public int size();
  
  /**  
   * Returns a string representation of this deque. The front element
   * occurs first, and each element is separated by a space. If the
   * deque is empty, returns "empty".
   * @return the string representation of the deque
   */
  public String toString();
  </code></pre>
  
  <p>}</p>
  
  <p>and a description of the node is:</p>
  
  <pre><code>public class LinearDoubleNode&lt;T&gt;
  {
  private LinearDoubleNode&lt;T&gt; next;
  private T element;
  
  /**
   * Creates an empty node.
   */
  public LinearDoubleNode()
  {
      next = null;
      element = null;
  }
  
  /**
   * Creates a node storing the specified element.
   * @param elem element to be stored
   */
  public LinearDoubleNode(T elem)
  {
      next = null;
      element = elem;
  }
  
  /**
   * Returns the node that follows this one.
   * @return reference to next node
   */
  public LinearDoubleNode&lt;T&gt; getNext()
  {
      return next;
  }
  
  /**
   * Sets the node that follows this one.
   * @param node node to follow this one
   */
  public void setNext(LinearDoubleNode&lt;T&gt; node)
  {
      next = node;
  }
  
  /**
   * Returns the element stored in this node.
   * @return element stored at the node
   */
  public T getElement()
  {
      return element;
  }
  
  /**
   * Sets the element stored in this node.
   * @param elem element to be stored at this node
   */
  public void setElement(T elem)
  {
      element = elem;
  }
  </code></pre>
  
  <p>}</p>