The Iterator interface

Question

I have a University assignement that requires me to implement an inner class which implements the Iterator interface. The iterator works on a single-linked list superclass.

Currently my inner class looks like this:

private class ListIterator implements Iterator<V>{

    Node temp;
    boolean nextCalled = false;

    ListIterator(Node fo){
        this.temp = fo;
    }

    @Override
    public boolean hasNext() {
        if(temp != null){
            return true;
        }
        return false;
    }

    @Override
    public V next() {
        nextCalled = true;
        return temp.getReprValue();
    }

    @Override
    public void remove() {
        if(nextCalled && hasNext()){
            nextCalled = false;
            removeElement(temp.getReprKey());
            temp = temp.getNext();
        }

    }

}

Now my problem is that the hasNext() method returns true even when the list is actually empty. Everything else seems to work. I have probably overlooked a logic flaw somewhere, but I cannot find it myself.

Answer 1

Changed your implementation to reflect what the Iterator contract needs. You need to remember that you need to be able to iterate over all elements of the collection, i.e., next() should start from the first element and after every call it must change the current next element to the next element in the list or throw an exception if there's none.

It's good to read the Iterator interface doc to undestand the way you need to implement it and start from there.

private class ListIterator implements Iterator<V> {
    private Node next;
    private boolean alreadyDeleted = false;

    ListIterator(Node node){
        this.next = node;
    }

    @Override
    public boolean hasNext() {
        // because next is the current element. We need to iterate over all the elements
        // from the collection.
        return next != null;
    }

    @Override
    public V next() {
        if (next == null) {
           throw new NoSuchElementException();
        }

        Node current = next;

        this.next = current.getNext();
        this.alreadyDeleted = false; // it's better to try to elimate this state variable. You can try to do in another way, if yours removeElement returns something

        return current;
    }

    @Override
    public void remove() {
        if (alreadyDeleted || next == null) {
           throw new IllegalStateException();
        }
        removeElement(next.getReprKey());
        this.alreadyRemoved = true;
    }

}

Answer 2

You need to keep track of where you are in your list, implement a cursor, or if your nodes in the linked list are aware of their next, just ask them if they have a next element. When the cursor is bigger then the length / your node has no next you return false in hasNext().

Do all this in your hasNext() method. Remember, it's okay to have next() throw an exception if hasNext() would have been false - so you need to make sure that's the only time it will throw an exception.

As I don't know the underlying data structure of your list, I can't tell you which one of these will be better.