8

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.

3
  • 1
    next method supposed not only to return value, but somehow move iterator into the next position. Your implementation just stores a flag. Mar 12, 2013 at 15:23
  • Shouldn't the value of temp be changed in your next() method? Mar 12, 2013 at 15:25
  • On a side note, there's already an interface named ListIterator in the same package as Iterator... so you might want to choose a different name.
    – Powerlord
    Mar 12, 2013 at 15:26

4 Answers 4

5

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

}
5

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.

2

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

2

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.

6
  • 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.
    – Jason K.
    Mar 21, 2017 at 13:08
  • @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?
    – Edwin Buck
    Mar 22, 2017 at 2:48
  • Can "private Node current" be declared in the beginning of the getNext() function, or is it used by any other functions?
    – Jason K.
    Mar 24, 2017 at 14:30
  • @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.
    – Edwin Buck
    Mar 24, 2017 at 20:46
  • 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.
    – Jason K.
    Mar 24, 2017 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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