11.3. 迭代器¶
11.3.1. 目标¶
完成本模块后，学生将能够：
描述迭代器的目的与用途
使用迭代器和可迭代接口实现迭代器
设计并开发使用迭代器及其方法的算法
11.3.1.1. 建议阅读¶
Java 插曲 5（迭代器），节选自 Frank M. Carrano 与 Timothy Henry 所著《Data Structures and Abstractions with Java》（第 4 版） 。
11.3.2. 迭代器简介 [13:14]¶
Follow Along and Engage
下载与视频对应的幻灯片。观看视频时，在幻灯片上做笔记，并亲自练习绘制图表！
Video Slides 11.3.2.1-IntroToIterators.pdf
11.3.3. 检查点 1¶
11.3.4. 使用 Iterable 接口进行编程 [4:36]¶
11.3.5. 检查点 2¶
11.3.6. 使用迭代器进行编程 [18:02]¶
Follow Along and Engage
下载与视频对应的幻灯片。观看视频时，在幻灯片上做笔记，并练习自己绘制图表！
Video Slides 11.3.4.1-ProgrammingWithIterators.pdf
11.3.7. 检查点¶
11.3.8. 迭代器设计决策 [8:21]¶
Follow Along and Engage
下载与视频对应的幻灯片。观看视频时，在幻灯片上做笔记，并练习自己绘制图表！
Video Slides 11.3.5.1-IteratorsDesignConsiderations.pdf
Clarification
嵌套在链表结构内部的迭代器（而非子类）比独立的迭代器类效率更高。
11.3.9. 内层迭代器用于例 11.3-迭代器¶
如本节所述，存在多种迭代器设计方案。以下是为 ex11.3-Iterator 实现内部 Iterator 类的一个示例。
包含一个公共方法以提供迭代器对象：
/**
* Iterator method creates Iterator object
*
* @return new Iterator object
*/
public Iterator<T> iterator()
{
return new LListIterator<T>();
}
包含一个内部 Iterator 类。此版本不提供 remove 功能，因为使用单链表跟踪前一个节点以删除当前节点会很复杂。
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;
}
}
这是一个提供移除功能的内部 Iterator 类版本。最好仅通过数据结构或迭代器提供移除功能，以避免意外副作用。
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;
}
}
