Self-made linked list iterator

Question

I recently made a linked list for myself, the code of which was posted here, if anyone would be interested. Now, as the next task, I had to make an Iterator for my list, which is working properly.

public Iterator<T> iterator() {
    final MyLinkedList<T> list = this;
    return new Iterator<T>() {
        final Node<T> firstNode = list.firstNode;
        Node<T> currentNode = null;
        @Override
        public boolean hasNext() {
            if (list.isEmpty()) {
                return false;
            } else if (currentNode == null){
                return true;
            } else if (currentNode == list.lastNode){
                return false;
            }
            return true;
        }
        @Override
        public T next() {
            if (list.isEmpty()){
                throw new NoSuchElementException();
            } else if (currentNode == null){
                this.currentNode = firstNode;
                return currentNode.data;
            } else if (currentNode.nextNode == null) {
                throw new NoSuchElementException();
            }
            this.currentNode = currentNode.nextNode;
            return currentNode.data;
        }
    };
}

Here are the variables of the LinkedList class:

private Node<T> lastNode;
private Node<T> firstNode;
private int size;

This is a Node<U>:

private static class Node<U>{
    private Node<U> nextNode = null;
    private Node<U> previousNode = null;
    private int index;
    private U data;

    private Node(U data){
        this.data = data;
    }
}

And this is how I add a new Node:

public boolean add(T data) {
    if (data == null) {
        return false;
    }

    Node<T> currentNode = new Node<T>(data);

    if (this.isEmpty()){
        currentNode.previousNode = null;
        currentNode.index = 0;
        this.firstNode = currentNode;
    } else {
        currentNode.previousNode = lastNode;
        lastNode.nextNode = currentNode;
        currentNode.index = lastNode.index + 1;
    }
    this.lastNode = currentNode;
    this.size++;
    return true;
}

Could this be made significantly faster? Does the code comply with the Java coding conventions?

Answer 1

Does the code comply with the Java coding conventions?

I think it does comply quite well. A tiny thing is that it would be better to put a space between ){, for example in if (list.isEmpty()){. More importantly, it can be simplified.

---

There is no need for the inner list variable pointing to this. The inner (non-static) class has direct access to the containing class' fields and methods: it can access firstNode directly from the containing list. So in this code:

final MyLinkedList<T> list = this;
return new Iterator<T>() {
    final Node<T> firstNode = list.firstNode;

You can drop both the list variable and the firstNode variable.

---

It's a minor thing, but currentNode can be private.

---

The hasNext method can be simplified by a lot:

@Override
public boolean hasNext() {
    if (list.isEmpty()) {
        return false;
    } else if (currentNode == null){
        return true;
    } else if (currentNode == list.lastNode){
        return false;
    }
    return true;
}

This is equivalent:

@Override
public boolean hasNext() {
    return !isEmpty() && currentNode != lastNode;
}

---

Could this be made significantly faster?

Slightly. Notice that the isEmpty() check is pointless to perform for every iteration of a non-empty list. So as a minor optimization, you could check for emptiness once, in the beginning, and then omit all the isEmpty() checks from the rest of the code.

Suggested implementation

Putting it all together:

public Iterator<T> iterator() {
    if (isEmpty()) {
        return Collections.<T>emptyList().iterator();
    }
    return new Iterator<T>() {
        private Node<T> currentNode = null;

        @Override
        public boolean hasNext() {
            return currentNode != lastNode;
        }

        @Override
        public T next() {
            if (currentNode == null) {
                currentNode = firstNode;
                return currentNode.data;
            }
            if (currentNode.nextNode == null) {
                throw new NoSuchElementException();
            }
            currentNode = currentNode.nextNode;
            return currentNode.data;
        }
    };
}

Unit testing

I didn't just refactor aggressively. I wrote unit tests first to know that I'm not breaking anything. After that I could go ahead and refactor aggressively:

@Test
public void testEmpty() {
    MyLinkedList<Integer> list = new MyLinkedList<>();
    assertFalse(list.iterator().hasNext());
}

@Test(expected = NoSuchElementException.class)
public void throwIfNextOnEmpty() {
    MyLinkedList<Integer> list = new MyLinkedList<>();
    list.iterator().next();
}

@Test(expected = NoSuchElementException.class)
public void throwIfIterateBeyond() {
    MyLinkedList<Integer> list = new MyLinkedList<>();
    list.add(1);
    list.add(2);
    Iterator<Integer> iter = list.iterator();
    iter.next();
    iter.next();
    iter.next();
}

@Test
public void testStandardIteration() {
    MyLinkedList<Integer> list = new MyLinkedList<>();
    Integer[] items = { 12, 3, 4 };
    for (int i : items) {
        list.add(i);
    }
    Iterator<Integer> iter = list.iterator();
    for (Integer item : items) {
        assertTrue(iter.hasNext());
        assertEquals(item, iter.next());
    }
    assertFalse(iter.hasNext());
}

These may not be perfect, and might not cover all corner cases, but I hope they are enough to get you started.

Answer 2

There's a trick with Iterator implementations that can make the logic much simpler, if you caan get your head around the slightly back-to-front implementation.

In your code, you have implemented a system where it checks the state of the list before iterating, but, if you think of an iterator as being a cycle of:

1. check if there's another member
2. advance to the next member
3. return the member
4. go to 1.

then, what you are doing, is having your 'mindset' anchored at the spot just before step 1. Step 1 is what you consider to be the 'base' state of the cycle.

But, there's no reason for that, you can actually anchor the cycle at the spot just in between step 2 and step 3.

The way this works, is easier to explain with code, rather than words....

... as an aside, there's no need to have the final MyLinkedList list = this because you can reference MyLinkedList.this.firstNode, etc.

public Iterator<T> iterator() {

    return new Iterator<T>() {

        private Node<T> followingNode = firstNode;

        @Override
        public boolean hasNext() {
            return followingNode != null;
        }

        @Override
        public T next() {
            if (followingNode == null) {
                throw new NoSuchElementException();
            }
            T toReturn = followingNode.data;
            followingNode = followingNode.nextNode;
            return toReturn;
        }
    };
}

Notice how the 'state' of the iterator is 'ready' to return the next() value. Because the iterator is set up that way, the check to see hasNext() is really easy... all you have to do is see if the current state is valid. Also, in the next() method the state check is also very easy, and we harvest the return value from the known-valid state, and then we advance to the next state before returning the value. We don't need to check if the next state is valid because that will happen on the next-go-around.

While I was putting that together, I noticed some other things too. In your code you have:

        if (list.isEmpty()){
            throw new NoSuchElementException();
        } else if (currentNode == null){
            this.currentNode = firstNode;
            return currentNode.data;
        } else if (currentNode.nextNode == null) {
            throw new NoSuchElementException();
        }

Those else-if blocks are not necessary. Each block exits the function (either through a throw or a return. You should write blocks like that as:

        if (list.isEmpty()){
            throw new NoSuchElementException();
        }
        if (currentNode == null){
            this.currentNode = firstNode;
            return currentNode.data;
        }
        if (currentNode.nextNode == null) {
            throw new NoSuchElementException();
        }