Data Structures, Algorithms, & Applications in Java
Chapter 10, Exercise 15

(a)

The left end of the deque is the left end of the chain. We use data members to keep track of the leftmost and the rightmost nodes of the chain. The code is given below.

---

public class LinkedDeque implements Deque
{
   // data members
   protected ChainNode leftEnd;
   protected ChainNode rightEnd;

   // constructors
   /** create a deque that is empty */
   public LinkedDeque(int initialCapacity)
   {
      // the default initial values of leftEnd and rightEnd are null
   }
  

   public LinkedDeque()
      {this(0);}

   // methods
   /** @return true iff deque is empty */
   public boolean isEmpty()
      {return leftEnd == null;}

   /** @return leftmost element of deque
     * @return null if deque is empty */
   public Object getLeftElement()
   {
      if (isEmpty())
         return null;
      else
         return leftEnd.element;
   }

   /** @return rightmost element of deque
     * @return null if the deque is empty */
   public Object getRightElement()
   {
      if (isEmpty())
         return null;
      else
         return rightEnd.element;
   }

   /** insert theElement at the rightEnd of the deque */
   public void putAtRight(Object theElement)
   {
      // create node for theElement
      ChainNode x = new ChainNode(theElement);
      if (isEmpty())
         // create a one element deque
         leftEnd = rightEnd = x;
      else
      {// add at right end
         rightEnd.next = x;
         rightEnd = x;
      }
   }

   /** insert theElement at the leftEnd of the deque */
   public void putAtLeft(Object theElement)
   {
      // create node for theElement
      ChainNode x = new ChainNode(theElement);
      if (isEmpty())
         // create a one element deque
         leftEnd = rightEnd = x;
      else
      {// add at left end
         x.next = leftEnd;
         leftEnd = x;
      }
   }

   /** remove an element from the left end of the deque
     * @return removed element
     * @return null if the deque is empty */
   public Object removeFromLeft()
   {
      if (isEmpty())
         return null;

      // deque is not empty, save element to be removed
      Object e = leftEnd.element;

      // remove from deque
      leftEnd = leftEnd.next;

      return e;
   }

   /** remove an element from the right end of the deque
     * @return removed element
     * @return null if the deque is empty */
   public Object removeFromRight()
   {
      if (isEmpty())
         return null;

      // deque is not empty, save element to be removed
      Object e = rightEnd.element;

      // remove from deque
      if (leftEnd == rightEnd)
         // deque becomes empty
         leftEnd = null;
      else
      {// deque is not empty after removal of e
         // find element that precedes right most element
         ChainNode newRightEnd = leftEnd;
         while (newRightEnd.next != rightEnd)
            newRightEnd = newRightEnd.next;
      
         // remove last node
         rightEnd = newRightEnd;
         rightEnd.next = null;
      }

      return e;
   }
}

---

(b)

The complexity of removeFromRight is O(size of deque). The complexity of the remaining methods is O(1).