Deque implementation with array in Java

Question

I'm trying to implement a deque data structure with an iterator in Java using array. Please help to review and point out things that I can improve on.

public class Deque<Item> implements Iterable<Item> {


  private Item[] a; // the array.
  private int itemCount; // number of objects the array holds at any given point in time.
  private int head; //last filled position from Front
  private int tail; //last filled position from END
  private int size; // size of array.

   public Deque() {
      // construct an empty deque
      size = 2;
      a = (Item[])new Object[size];
      itemCount = 0;
      head = 0;
      tail = 0;
   }

   public boolean isEmpty()  {
                   // is the deque empty?
     return (itemCount == 0);
   }
   public int size()                        {
      // return the number of items on the deque
    return itemCount;
   }
   public void addFirst(Item item) {
     try {
       if (item == null) {
       throw new IllegalArgumentException("item cannot be null");
     }
   }
   catch (NullPointerException ex) {
     throw new IllegalArgumentException("item cannot be null");
   }
      if (isEmpty()) {
        addLast(item);
        //return;
      } else if (head == 0) {
        resize(size);
        head--;
        a[head] = item;
        itemCount++;
        //return;
      } else {
        head--;
        a[head] = item;
        itemCount++;
        //return;
      }
      return;
   }

   private void resize (int currentSize) {
     //resize array to squared of current size.
     int newSize = currentSize * currentSize;
     int newStart = (currentSize * (currentSize - 1))/2;
     int newHead = newStart;
     Item[] newA = (Item[]) new Object[newSize];
     for (int j = itemCount; j > 0; j--) {
       newA[newStart++] = a[head++];
     }
     head = newHead;
     tail = newStart - 1;
     size = newSize;
     a = newA;
     return;
   }

   public void addLast(Item item)   {


      if (isEmpty()) {
        tail++;
        a[tail] = item;
        head = tail;
        itemCount++;
        //return;
      }
      else if ( tail == (size -1)) {
        resize(size);
        tail++;
        a[tail] = item;
        itemCount++;
      }
      return;
   }
   public Item removeFirst()  {
      // remove and return the item from the front
      Item k;
      if (isEmpty()) throw new java.util.NoSuchElementException("Empty Deque");
      else {
        k = a[head];
        a[head] = null;
        head --;
        //start --;
        itemCount--;
      }
      return k;
   }
   public Item removeLast()  {
     // remove and return the item from the end
     Item k;
     if (isEmpty()) throw new java.util.NoSuchElementException("Empty Deque");
     else {
       k = a[tail];
       a[tail] = null;
       tail --;
       //end --;
       itemCount--;
     }
     return k;
   }
   public Iterator<Item> iterator() {
    // return an iterator over items in order from front to end
    return new DequeIterator();
   }
   private class DequeIterator implements Iterator<Item> {
     private int startpos;
     private int size;
     public DequeIterator () {
       startpos = head;
       size = itemCount;
     }
     public boolean hasNext() {
       return (size != 0);
     }
     public void remove() {
       throw new UnsupportedOperationException();
     }
     public Item next() {
       if (hasNext()) {
         size--;
         return a[startpos++];
       }
       throw new NoSuchElementException();
     }
   }
}

Answer 1

Pointless try ... catch:

 try {
   if (item == null) {
     throw new IllegalArgumentException("item cannot be null");
   }
 }
 catch (NullPointerException ex) {
   throw new IllegalArgumentException("item cannot be null");
 }

Nothing in the protected code can generate a NullPointerException. Perhaps something did at one point, but that code was removed, and the try ... catch was not removed?

---

Missing argument check:

addFirst() protects against adding null, but addLast() does not.

---

Resizing:

private void resize (int currentSize) {

This is not a static member function, so it has access to the current size of your deque. Why require the caller to pass in currentSize?

private void resize() {
  int currentSize = size;

... would be sufficient, and more friendly to the caller.

---

Resizing:

  int newSize = currentSize * currentSize;

You are squaring the current size??? Ok, going from 2 to 4 is fine, and 4 to 16 is within reason, and 16 to 256 could be justified, but 256 to 65536? I won't even contemplate the next step!

Doubling is a perfectly reasonable, and quite sane, resizing strategy.

---

Resizing:

  for (int j = itemCount; j > 0; j--) {
    newA[newStart++] = a[head++];
  }

Copying element by element is entirely correct, but you could let the JVM do the heavy lifting. There is a good chance it will be faster.

  System.arraycopy(a, head, newA, newStart, itemCount);

---

DequeIterator

You aren't protecting against any external modification to the deque while you are iterating over it. Consider a deque containing one item, and call the iter = iterator() method. Then, call removeLast(). At this point, iter.hasNext() will return true, and iter.next() will return a null!

A simple fix is to maintain a modification counter in the deque class, and on every modification, increase it by one. When you create an iterator, the iterator gets a copy of the modification counter's value. On any iterator operation, compare the deque's current modification counter with the copy; if they are different, throw a ConcurrentModificationException.

---

Wasted space:

If your deque has space for 256 items, but only contains 100 items, if the items are all stored at the start or end of the storage array, then a call to addFirst() or addLast() might resize the array, growing it to 65536 entires, 65436 which will be empty.

Two options:

1) If there is still plenty of available space in the storage array, just move the current contents back to the "centre" of the storage array. System.arraycopy() will do the heavy lifting here, avoiding any copy issue that may arise if the source and destination blocks overlap.

2) Use a circular array. When you increment past the end of the storage array, you reset the index back to 0; when you decrement past the start of the storage array, you reset the index to the last element. itemCount == size() becomes the trigger condition to resize the storage array. Take care to ensure you copy data from the src array to the destination array properly; you'll need to do it in two arraycopy() calls.

---

(Optional, Advanced) Type safety:

Your Item[] a array is not actually an Item[] array. It is a Object[] array masquerading as an Item[] array, because it was cast to the desired type to force it into the desired member:

a = (Item[]) new Object[size];

This is fine, as long as the array never, ever leaks out of your Deque class. For instance, don't ever add a toArray() method.

You can make a correctly typed storage array, as long as you are willing to pass the real item's class to the constructor.

public Deque(Class<Item> item_class) {
  size = 2;
  a = (Item[]) Array.newInstance(item_class, size);
  ...

You'd need this item_class in your resize() code as well, so store it as a member.