Reverse a doubly linkedlist

Question

Reverse a doubly linkedlist. Looking for code review, optimizations and best practices.

public class ReverseDoublyLinkedList<T> implements Iterable<T> {
 private Node<T> first;
 private Node<T> last;
 private int size;
 public ReverseDoublyLinkedList() { };
 public ReverseDoublyLinkedList(List<T> c) {
 for (T item : c) {
 add(item);
 }
 };
 public void add (T t) {
 final Node<T> l = last;
 final Node<T> node = new Node<T>(null, t, null);
 last = node;
 if (first == null) {
 first = node;
 } else {
 l.right = node;
 node.left = l;
 }
 size++;
 }
 private static class Node<T> {
 Node<T> left;
 T item;
 Node<T> right;
 public Node(Node<T> left, T item, Node<T> right) {
 this.left = left;
 this.item = item;
 this.right = right;
 }
 }
 public void reverse() {
 if (first == null) {
 throw new IllegalArgumentException("The root cannot be null.");
 }
 Node<T> node = first;
 while (node != null) {
 Node<T> temp = node.left;
 node.left = node.right;
 node.right = temp;
 node = node.left;
 }
 Node<T> temp = last;
 last = first;
 first = temp;
 }
 @Override
 public Iterator<T> iterator() {
 return new ListItr();
 }
 private class ListItr implements Iterator<T> {
 private int count;
 private Node<T> currentNode;
 public ListItr() {
 this.currentNode = first;
 }
 @Override
 public boolean hasNext() {
 return count < size;
 }
 @Override
 public T next() {
 if (!hasNext()) {
 throw new NoSuchElementException();
 }
 T item = currentNode.item;
 currentNode = currentNode.right;
 count++;
 return item;
 }
 @Override
 public void remove() {
 currentNode.left.right = currentNode.right;
 currentNode.right.left = currentNode.left;
 }
 }
 public static void main(String[] args) {
 ReverseDoublyLinkedList<Integer> foo = new ReverseDoublyLinkedList<Integer>();
 foo.add(10);
 foo.add(20);
 foo.add(30);
 foo.reverse();
 Iterator<Integer> itr = foo.iterator();
 while (itr.hasNext()) {
 System.out.println(itr.next());
 }
 }
}

• Edward: A doubly-linked list, by definition, can be traversed in either direction. What purpose is served by swapping left and right that wouldn't be served better and more efficiently by simply having something like a direction flag that's used by the Iterator?

Answer 1

The name ReverseDoublyLinkedList is not so good. Just stick to DoublyLinkedList.

It would make more sense if the reverse method returned a new instance of the list. Actually, I would have defined a static method that takes a list and return a reversed list.

Answer 2

There are a number of things to comment on here. Mostly related to style, not functionality.

I don't see any obvious bugs, so that is good.

The ListItr Iterator is poorly named. It is too close to ListIterator, which is not what this is. I would recommend something simpler like NodeIterator.

Speaking of the ListItr, it bugs me that you use the size of the List as the limiting factor in the hasNext(). It should be a simple return currentNode != null;.

You have what looks like a working remove() implementation on the ListItr, but you don't seem to test it at all. I would recommend not implementing functionality you do not use, or do not test. A simple UnsupportedOperationException is appropriate.

Back to the reverse() call.

I am not fussed with the reverse() being 'in place'. I think that is fine. What I don't like is the poor support for the empty-list reverse(). Why is it OK to throw IllegalArgumentException when:

1. there is no argument to the method (so it should be IllegalStateException ?)
2. it is really simple to just return for an empty list, and have the right result.

Finally, the static inner class Node:

1. it should be declared at the top, before the add and other non-static methods (and constructors).

2. I have mentioned before that I prefer inner static classes to have getters and setters for the private members (even though it is a private nested class). You have chosen to ignore that, that's OK, but I should still point it out.

3. I have also suggested before that there is no need to have the left and right as part of the constructor. You never use them (when constructing), so it is redundant and confusing.