Generic deque implementation

I implemented a generic Deque data structure.

Please, review this implementation.

Deque.java:

```
import java.util.Iterator;
import java.util.NoSuchElementException;

class Deque implements Iterable {
private class Node {
public Node left, right;
private final T item;

public Node(T item) {
// FIXME: maybe it's a bad practice to throw exception in constructor
if (item == null) { throw new NullPointerException(); }
this.item = item;
}

public void connectRight(Node other) {
this.right = other;
other.left = this;
}
}

private class DequeIterator implements Iterator {

private Node curr = head;

public boolean hasNext() {
return curr != null;
}
public void remove() {
throw new UnsupportedOperationException();
}
public T next() {
if (!hasNext()) { throw new NoSuchElementException(); }
T item = curr.item;
curr = curr.right;
return item;
}
}

private Node head, tail;
private int size;

public Iterator iterator() {
return new DequeIterator();
}

public Deque() {
}

public int size() {
return size;
}

public boolean isEmpty() {
return size() == 0;
}

public void checkInvariants() {
assert size >= 0;
assert size > 0 || (head == null && tail == null);
assert (head == null && tail == null) || (head != null && tail != null);
}

public void addFirst(T item) {
Node prevHead = head;
Node newHead = new Node(item);
if (prevHead != null) {
newHead.connectRight(prevHead);
} else {
tail = newHead;
}
head = newHead;
size++;
checkInvariants();
}

public void addLast(T item) {
Node newTail = new Node(item);
Node prevTail = tail;
if (prevTail != null) {
prevTail.connectRight(newTail);
} else {
head = newTail;
}
tail = newTail;
size++;
checkInvariants();
}

public T removeFirst() {
if (isEmpty()) {
throw new

This class looks reasonably complete, and fully usable. There are some issues I see that may affect the experience though, and also some suggestions about a better way to do it...
Issues:

-
Why do you reject null values? Your implementation works well even if the item is null, so why exclude it?

-
The NullPointerException in the constructor is not a problem, in itself. In this case the problem is that a null item makes sense, and there should be no exception at all. If the item did not make sense as null, then throwing the NPE would be fine. It is normal, when throwing an NPE though, to indicate which value is null. This makes it easier to debug.

-
You provide an iterator, and this implementation looks right. But, why provide an interator that can get all the items from your Deque, yet you have not get(*) methods. I think the Iterator is unnecessary...... and the Deque does not need to implement Iterable. If you provide read-access to the entire list through an iterator, then you should probably also just implement the get(int index) methods as well.... if you can iterate, you should also be able to get(...).

-
checkInvariants() is unnecessary if you have the appropriate tests for your code. Certainly, even if you have it, it should not be public.

Other Notes

The generics looks simple, and fine. No problem.

I prefer 4-space indent, but your 2-space is consistent, and otherwise fine. I know that some standards recommend 2-space, you're forgiven ;-)

You have some one-liners that are a problem:

if (!hasNext()) { throw new NoSuchElementException(); }

The above should be:

if (!hasNext()) {
   throw new NoSuchElementException();
 }

although I do appreciate having the braces....

Finally, even though the Node class is internal, I prefer having getters/setters for the right/left values. It makes spotting scope problems easier.
Recommendation

There are two basic styles of Linked node implementations. The one style starts with null values for the head and tail instances. The other style starts with constant 'dummy' nodes.

In this case, the code would be much simpler if you implemented dummy-based head and tail. Let me illustrate:

private final Node head = new Node<>(null);
  private final Node tail = new Node<>(null);
  private int size = 0;

  public Deque() {
    head.right = tail;
    tail.left  = head;
  }

Then, every operation knows the head and tail is not null, and becomes an insert/delete.

The certainty this gives is useful. For example, your iterator becomes:

private class DequeIterator implements Iterator {

    private Node curr = head.right; // note, start from next()

    public boolean hasNext() {
      return curr != tail;
    }

    public void remove() {
      throw new UnsupportedOperationException();
    }

    public T next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      T item = curr.item;
      curr = curr.right;
      return item;
    }
  }

And your addFirst becomes (first, your current implementation):

public void addFirst(T item) {
    Node prevHead = head;
    Node newHead = new Node(item);
    if (prevHead != null) {
      newHead.connectRight(prevHead);
    } else {
      tail = newHead;
    }
    head = newHead;
    size++;
    checkInvariants();
  }

and it becomes:

public void addFirst(T item) {
    Node toadd = new Node(item);
    Node before = head.right;
    head.right = toadd;
    toadd.left = head;
    before.left = toadd;
    toadd.right = before;
    size++;
    checkInvariants();
  }

The removeFirst() would be:

public T removeFirst() {
    if (isEmpty()) {
      throw new java.util.NoSuchElementException();
    }
    size--;
    Node togo = head.right;
    head.right = togo.right;
    head.right.left = head;
    togo.left = null;
    togo.right = null;
    checkInvariants();
    return togo.item;
  }

By having a permanent head and tail, you can avoid almost all the conditional exection in your add/remove methods.

StackExchange Code Review Q#56361, answer score: 12