Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I implemented a generic Deque<T> data structure.

Please, review this implementation.

Deque.java:

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

class Deque<T> implements Iterable<T> {
  private class Node<T> {
    public Node<T> 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<T> other) {
      this.right = other;
      other.left = this;
    }
  }

  private class DequeIterator implements Iterator<T> {

    private Node<T> 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<T> head, tail;
  private int size;

  public Iterator<T> 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<T> prevHead = head;
    Node<T> newHead = new Node<T>(item);
    if (prevHead != null) {
      newHead.connectRight(prevHead);
    } else {
      tail = newHead;
    }
    head = newHead;
    size++;
    checkInvariants();
  }

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

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

  public T removeLast() {
    if (isEmpty()) {
      throw new java.util.NoSuchElementException();
    }
    size--;
    Node<T> prevTail = tail;
    tail = prevTail.left;
    prevTail.left = null;
    if (tail != null) tail.right = null;
    checkInvariants();
    return prevTail.item;
  }
}

DequeTest.java:

import org.junit.Test;
import static org.junit.Assert.*;
import java.util.Iterator;

public class DequeTest {

  @Test
  public void testDeque() {
    Deque<Double> d = new Deque<Double>();
    assertTrue(d.isEmpty());
    d.addFirst(2.0);
    assertFalse(d.isEmpty());
    assertEquals(1, d.size());
  }

  @Test
  public void testAddFirstRemoveAndRepeat() {
    Deque<Double> d = new Deque<Double>();
    d.addFirst(1.0);
    assertEquals(Double.valueOf(1.0),d.removeFirst());
    d.addLast(2.0);
    assertEquals(Double.valueOf(2.0),d.removeLast());

    d.addFirst(3.0);
    assertEquals(Double.valueOf(3.0),d.removeLast());
    d.addLast(4.0);
    assertEquals(Double.valueOf(4.0),d.removeFirst());
  }


  @Test
  public void testIterator() {
    Deque<Double> d = new Deque<Double>();
    for (Double i = 0d; i < 10; i++) {
      d.addLast(i);
    }
    int i = 0;
    for(Double cur: d) {
      System.out.println(i);
      assertEquals(Double.valueOf(i), Double.valueOf(cur));
      i++;
    }
    assertEquals(Double.valueOf(i), Double.valueOf(10));
  }


  @Test(expected=java.util.NoSuchElementException.class)
  public void testRemoveFirstOnEmpty() {
    Deque<Double> q = new Deque<Double>();
    q.removeFirst();
  }

  @Test(expected=java.util.NoSuchElementException.class)
  public void testRemeveLastOnEmpty() {
    Deque<Double> d = new Deque<Double>();
    d.removeLast();
  }

  @Test(expected=java.util.NoSuchElementException.class)
  public void testIteratorNextOnEmpty() {
    Deque<Double> d = new Deque<Double>();
    Iterator<Double> i = d.iterator();
    assertFalse(i.hasNext());
    i.next();

  }

  @Test(expected=NullPointerException.class)
  public void testAddFirstWithNull() {
    Deque<Double> d = new Deque<Double>();
    d.addFirst(null);
  }

  @Test(expected=NullPointerException.class)
  public void testAddLastWithNull() {
    Deque<Double> d = new Deque<Double>();
    d.addLast(null);
  }
}
share|improve this question

3 Answers 3

up vote 11 down vote accepted

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<T> head = new Node<>(null);
  private final Node<T> 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<T> {

    private Node<T> 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<T> prevHead = head;
    Node<T> newHead = new Node<T>(item);
    if (prevHead != null) {
      newHead.connectRight(prevHead);
    } else {
      tail = newHead;
    }
    head = newHead;
    size++;
    checkInvariants();
  }

and it becomes:

  public void addFirst(T item) {
    Node<T> toadd = new Node<T>(item);
    Node<T> 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<T> 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.

share|improve this answer
    
I added improved version of source code to question. Now it uses sentinel node. Thanks –  kharandziuk Jul 8 at 15:12

Deque

There is nothing wrong with throwing an exception in the constructor. However, I would suggest switching to IllegalArgumentException.


Put the helper classes at the end of the class, not the beginning. Node and Iterator are well defined terms. Someone reading your class can assume that they match those definition, then look at them later if they need to.

Similarly, it makes more sense for the constructor to be come before any other methods.


A user of your class never needs to call checkInvariants(), so it should not be public. You can also decide if you need the assertions to be completed at all in your code. If you are writing good tests, those checks become redundant.


Tests

This is the section you should focus on. The comments above are all minor points. The comments below are what needs to be stressed.

Naming:

Since you are using Junit4, you don't need to prefix your method names with test.

Your test names are not descriptive enough. What does testDeque() do? Is it testing the class as a whole? Is it testing the constructor? A good way to name tests is ThingBeingTested_Context_ExpectedResult(). This way, from just the failure line, you can have a good idea of where the issue is, what is causing the issue, and what should be happening.


Too many actions per test:

You should easily be able to break a test case into three sections: Arrange, Act, Assert.

  @Test
  public void addFirst_SomeValue_NotEmpty() {
    Deque<Double> d = new Deque<Double>();

    d.addFirst(2.0);

    assertFalse(d.isEmpty());
  }

Don't check multiple things in a single test. If the first assertion fails, the second one will never be executed. Splitting multiple assertions into different test cases will provide you more information when a failure occurs. Knowing that size() and isEmpty() give the wrong result or that size() gives the correct value but isEmpty() give the wrong result provides you with more information about the situation.

It is important to know that this does not mean you can only have one assert statement per test. When you are testing the sequence the iterator produces, it is fine to do the following:

@Test
  public void iterator_SomeValues_CorrectOrder() {
    //Arrange
    Deque<Double> d = new Deque<Double>();
    d.addFirst(1.0);
    d.addFirst(2.0);
    d.addFirst(3.0);
    Iterator<Double> it = d.iterator();

    //act
    double first = it.next();
    double second = it.next();
    double third = it.next();

    //assert
    assertEquals(Double.valueOf(1.0), first);
    assertEquals(Double.valueOf(2.0), second);
    assertEquals(Double.valueOf(3.0), third);
  }

Here, I call the methods of the iterator explicitly to keep the flow of the test case as simple as possible.


testAddFirstRemoveAndRepeat() is testing removeFirst() & removeLast() and uses addFirst() & addLast(). The name doesn't mention last at all.

The fact that you have repeat in that name is another clear give away that too much is being done in this test method. At first that made me think you were testing the same thing with multiple different inputs. If this was that case, you should use a Parameterized Test for that. However, that is not what is being done here.

What you are doing is checking that given a empty Deque:

  • the value passed to addFirst() is the value returned by removeFirst().
  • the value passed to addLast() is the value returned by removeLast().
  • the value passed to addFirst() is the value returned by removeLast().
  • the value passed to addLast() is the value returned by removeFirst().

Each of those are their own test. Lets assume that the remove methods return the correct value, but don't actually remove the item. With your implementation of the test, the first two assertions would pass, but when you try the third case, it would fail. However, it is not failing because removeLast() is returning the wrong value. It is failing because you assumed the Deque was empty before the call to addFirst() and it wasn't.

share|improve this answer
    
Thanks, you provided a really good topic. There are some cool notes about tests. I upvoted you answer but accepted @rolfl's one because he provided an idea of sentinel node. –  kharandziuk Jul 7 at 19:33
    
I provided improved version of source code to question. Now tests corresponds to your guidelines. Thanks! –  kharandziuk Jul 8 at 15:13
    
@kharandziuk: If you would like additional guidance on improved code, please post a new question with some context. This question has already been marked as answered and any comments on the improved code would be different from the current answers. Also, as a rule, we don't like to rely on third party sites to host the code to be reviewed. So post the code in the body of the question. –  unholysampler Jul 8 at 15:19
    
I think there is no reason to do that. I just want to mention that I followed to your guidelines. Thanks! –  kharandziuk Jul 8 at 15:25

Just one more thing, you should size-- just before the return statements in removeFirst() and removeLast()

share|improve this answer
    
But, why? Do you mean that it should be done as the very last thing, or should be done twice.... note that there already are size-- statements in each of those methods. –  rolfl Oct 24 at 20:57
    
I mean it should be the very last thing. It does not improve the correctness except in case of a runtime exception if the element has not been removed the size will not have been incorrectly decremented. Although we may argue that in such cases queue DS may be corrupt. –  Abhinav Dwivedi Oct 25 at 18:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.