Iterator interface

Question

I have a university assignment that requires me to implement an inner class that implements the Iterator interface. An iterator is working on a simply connected superclass.

Currently, my inner class is as follows:

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 if the list is actually empty. Everything else seems to work. I probably forgot a logical flaw somewhere, but I can't find it myself.

Answer 1

Your implementation has been modified to reflect what the Iterator contract requires. You must remember that you need to be able to iterate over all elements of the collection, i.e. next() should start with the first element, and after each call, it should change the current next element to the next element in the list or throw an exception if it is absent.

It's good to read the Iterator interface doc to determine how you need to implement it and start from now on.

 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 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 on your list, implement cursor , or if your nodes in the linked list know about their next , just ask them if they have the next element. When the cursor is longer, the length / of your node does not have next , you return false in hasNext ().

Do all this in your hasNext() method. Remember that it is normal if next () throws an exception, if hasNext() would be false, so you need to make sure the only time it throws an exception.

Since I do not know the basic data structure of your list, I cannot tell you which one will be better.

Answer 3

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

If the implementation of the linked list uses the node header, the constructor always gets fo!=null , and hasNext returns true , although the list is empty. You must consider this fact in your implementation.

Based on your code, it seems like

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

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

Answer 4

To reduce some code and make it more readable

• rename temp to next ,
• use shortcut
• probably should have some notion of current node,

what makes the update look like this:

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

delete can set the current to null. We do not need a flag (provided that we are fine, doing nothing if the person removes before calling the first getNext() . If we really want to go for gold, remove() throw an IllegalStateException if current == null .