11.2. Iterators¶
11.2.1. Objectives¶
Upon completion of this module, students will be able to:
Describe the purpose and use of an Iterator
Implement Iterators using the Iterator and Iterable Interfaces
Design and develop algorithms that use Iterators and Iterator methods
11.2.1.1. Suggested Reading¶
Java Interlude 5 Iterators from Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry
11.2.5. Iterator Design Decisions¶
11.2.5.1. [8:21] Iterator Design Decisions Video¶
Clarification: Iterators that are nested class inside the linked structure (not subclasses) are more efficient than Iterators that are independent classes.
11.2.6. Inner Iterator for CS2-ExLinkedList¶
As discussed throughout this section there are various design approaches for iterators. Below is one example of how an inner Iterator class could be implemented for CS2-ExLinkedList.
Include a public method to make the iterator object available:
/**
* Iterator method creates Iterator object
*
* @return new Iterator object
*/
public Iterator<T> iterator()
{
return new LListIterator<T>();
}
Include an inner Iterator class. This version does not provide remove functionality as it is complicated with a singly linked list to keep track of the previous nodes in order to remove the current node.
private class LListIterator<A> implements Iterator<T>
{
private Node next;
private boolean newCurr;
/**
* Creates a new DLListIterator
*/
public LListIterator()
{
next = firstNode;
newCurr = false;
}
/**
* Checks if there are more elements in the list
*
* @return true if there are more elements in the list
*/
@Override
public boolean hasNext()
{
return (next != null);
}
/**
* Gets the next value in the list
*
* @return the next value
* @throws NoSuchElementException
* if there are no nodes left in the list
*/
@Override
public T next()
{
if (next == null)
{
throw new NoSuchElementException("No nodes left in the list.");
}
T value = next.data;
next = next.getNext();
newCurr = true;
return value;
}
}
A version of an inner Iterator class which does provide remove functionality. It is best to only provide remove functionality through either the data structure or the iterator in order to avoid unintended side effects.
private class LListIterator<A> implements Iterator<T>
{
private Node prev;
private Node curr;
private Node next;
private boolean newCurr;
/**
* Creates a new DLListIterator
*/
public LListIterator()
{
prev = null;
curr = null;
next = firstNode;
newCurr = false;
}
/**
* Checks if there are more elements in the list
*
* @return true if there are more elements in the list
*/
@Override
public boolean hasNext()
{
return (next != null);
}
/**
* Gets the next value in the list
*
* @return the next value
* @throws NoSuchElementException
* if there are no nodes left in the list
*/
@Override
public T next()
{
prev = curr;
curr = next;
next = next.getNext();
if (curr == null)
{
throw new NoSuchElementException("No nodes left in the list.");
}
newCurr = true;
return curr.data;
}
/**
* Removes the last object returned with next() from the list
*
* @throws IllegalStateException
* if next has not been called yet
* and if the element has already been removed
*/
@Override
public void remove()
{
if (next == firstNode)
{
throw new IllegalStateException(
"Next has not been called yet.");
}
else if (!newCurr)
{
throw new IllegalStateException(
"The Element has already been removed.");
}
else if (curr == firstNode) {
firstNode = next;
curr = null;
} else {
prev.setNext(curr.getNext());
curr = prev;
//this code that updates prev is not necessary
//because next() must be called before another remove()
//and that will update prev, saving this O(n) operation
//prev = firstNode;
//while ((prev != null) && (prev.getNext() != curr)){
// prev = prev.getNext();
//}
}
numberOfEntries--;
newCurr = false;
}
}
