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.

Solution 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;
    }

}

Solution 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.

Solution 3

To reduce some code, and make it a touch more readable

• rename temp to next,
• use shortcut notation,
• probably should have some concept of the current node,

which makes the update look like:

private Node next;
private Node current;    //track deletion

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

public Node getNext() {
  if (hasNext()) {
    current = next;
    next = next.getNextNode();
  }
  return current;
}

the delete could set current to null. We don't need a flag (assuming that we're fine with doing nothing if a person deletes prior to calling the first getNext(). Heck, if we really want to go for the gold, have remove() throw an IllegalStateException if current == null.

Solution 4

hasNext returns true if the current node (temp) is not null.

If your linked list implementation uses a header node, then the constructor always receives fo!=null and hasNext will return true even though the list is empty. You should consider this fact in your implementation.

Based on your code, it seem that

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

may do the trick (if header.getNext()==null for an empty list).

View more solutions

Comments

[Jason K.]

it looks to me like this answer has confused the calling (main) function with the node, it's not clear why you would name a Node current then set it to next unless you were shifting nodes backwards in the structure? (which is not what getNext should be doing) btw I do like the shortcut suggestion, that's not really part of the question tho.

[Edwin Buck]

@JasonK. I must admit, I'm a bit confused. I am not sure how the (main) function is being called, there isn't a public static void main(String[] args) in any of the examples, and this answer was good enough for the asker, way back when I answered it four years ago. Perhaps you could elaborate?

[Jason K.]

Can "private Node current" be declared in the beginning of the getNext() function, or is it used by any other functions?

[Edwin Buck]

@JasonK. If you declare Node current in the beginning of the getNext() function, then you would have to set it each time the getNext() function is called (or it will be null). What you set it from, assuming you have an Iterator that can get the second element in a collection, will have to be declared outside of the getNext() method. That way the third call to getNext() can return something "after" the second call, etc. In my example, the current holds what you have, and the next holds the next current. This simplifies logic for iterators on empty lists.

[Jason K.]

thanks i've been writing my own structures for many years but I'm still learning what I don't know about iterators. is getNext() the same as next()? if you could edit your answer a bit that would help too, otherwise it looks like i can try to do that myself as well.

[Edwin Buck]

@JasonK. getNext() is similar to next() (and for some styles of iterator design, the same). The get portion indicates that it advances the iterator (which effectively is the object holding the conceptual index of the thing being transversed) AND returns the value at the index you transversed into. Some iterators use next() without returning, and some use next() in an identical manner to getNext() as I describe it above. There is precious little standardization between technologies.