JAVA迭代器学习--在JAVA中实现线性表的迭代器

1，迭代器是能够对数据结构如集合（ADT的实现）进行遍历的对象。在遍历过程中，可以查看、修改、添加以及删除元素，这是它与一般的采用循环来遍历集合中的元素不同的地方。因为，通常用循环进行的遍历操作一般是逐个输出元素，而用迭代器不仅仅只是查看元素，还可以改变元素（若迭代器支持remove()）。

2，在JAVA类库中定义了两个常用的迭代器接口：Iterator和ListIterator，它们为迭代器指定了方法。给某个具体的ADT实现（如，单链表）添加迭代器功能时有以下两种方式：（以链表为例）

①将迭代器方法添加到ADT线性表的操作中

②将迭代器定义为一个与ADT线性表相互作用的单独的类。

②又分两种情况：将该类定义在ADT线性表之外和将该类作为线性表的内部类（具体地说，将该类定义在实现线性表ADT接口的类的内部）

3，ADT线性表的display操作(见博文：http://www.cnblogs.com/hapjin/p/4549492.html）执行了一次迭代，但是它仅仅是显示线性表，若还想在遍历的同时对线性表进行其它的操作呢？显然，我们不希望每次需要遍历ADT中的元素时，就构建循环，而是应将线性表的遍历封装起来。--此处可参考设计模式之迭代器模式

4，Iterator接口中只定义了三个方法

hasNext() :当迭代到最后一个元素时，再调用hasNext()将会抛出NoSuchElementException异常

next() :返回当前被迭代过的元素，刚刚被迭代器指针跳跃过的元素

remove() :该方法根据实际的需要来实现该方法，如：客户不需要remove操作时，可以在实现remove()方法时抛出UnsupportedOperationException

注意：在JAVA中，迭代器位置不是在某个元素上，而是在集合的第一个元素之前、两个元素之间或最后一个元素之后。

5，如何给ADT线性表添加迭代器功能呢？正如在第2点中提到的，可以有三种方式来实现

❶在自己的类中实现迭代器方法，该类是公共类，与实现ADT的类分开了。这种迭代器实例为独立类迭代器

❷将遍历操作定义为ADT操作，如：ListInterface 接口扩展了 Iterator，那么线性表对象就同时具有迭代器方法和线性表方法了。

❸在自己的类中实现迭代器方法，该类是内部类，定义在实现ADT的类的内部，该类作为实现ADT类的一个私有内部类。称之为内部类迭代器。

6，按方式❶中进行迭代器的实现：

定义SeparateIterator类，implements Iterator<T>接口，在SeparateIterator类中实现对线性表的迭代。那么，如何让迭代器去遍历线性表呢？这就需要将迭代器与线性表联系起来。联系的方式如下：在SeparateIterator类中定义ListInterface类型的引用，然后构造函数中用实现了线性表接口的类的对象来实例化ListInterface引用，这样，就可以在SeparateIterator中完成具体的对线性表的遍历了。用户程序只需要一个生成迭代器对象的方法，用户程序通过调用该方法，得到一个迭代器对象，通过该迭代器对象来调用 hasNext方法、next方法来对线性表进行遍历。按这种方式实现的迭代器，对于线性表而言，它可以有多个迭代器同时在遍历它。

具体代码如下：

import java.util.Iterator;
import java.util.NoSuchElementException;

public class SeparateIterator<T> implements Iterator<T>{

    //迭代器迭代器的对象是谁？它就是实现ListInterface接口的类的对象
    private ListInterface<T> list;//用来将迭代器与线性表联系起来
    private int nextPosition;//指示当前正在遍历的元素
    //执行remove时需要先调用next
    private boolean wasNextCalled;//用来标记next是否被调用了
    
    /*
     * 构造器方法，用来初始化迭代器
     * 参数类型为ListInterface，这样，任何实现了该接口的类的对象
     * 都可以作为参数传递给构造器，这是JAVA中的多态的性质
     */
    public SeparateIterator(ListInterface<T> aList) {
        list = aList;
        nextPosition = 0;
        wasNextCalled = false;
    }
    
    @Override
    public boolean hasNext() {
        return nextPosition < list.getLength();
    }

    @Override
    public T next() {
        if(hasNext()){
            wasNextCalled = true;
            nextPosition++;
            return list.getEntry(nextPosition);//调用线性表的方法getEntry来进行实际的遍历
        }
        else
            throw new NoSuchElementException("Illegal call to next(); " + "iterator is after end of list");
    }

    @Override
    public void remove() {
        if(wasNextCalled){
            list.remove(nextPosition);
            nextPosition--;
            wasNextCalled = false;
        }
        else
            throw new IllegalStateException("Illegal call to remove(); " + "next() was not called.");
    }
}

方式❷和方式❸中对迭代器的实现基本上相同。方式❷就是：ListInterface 接口扩展了 Iterator，这样具体实现ListInterface接口的类除了需要实现基本的线性表的方法（如，getEntry、add、clear、replace……）还需要实现Iterator中定义的三个方法。

这样当 new 一个实现了ListInterface接口的类的对象时，该对象就具有两种性质：第一种性质是线性表，第二种性质是迭代器。说白了，即实现了ListInterface接口的类的对象它既是线性表又是迭代器。因为它即可以调用线性表的各种方法，又可以调用hasNext方法、next方法进行迭代。

对方式❸而言，它是在实现ListInterface接口的类的内部定义一个实现Iterator接口的类（如，实现ListInterface接口的类为LList，则是在LList类的内部定义一个类，这个类 implements Iterator<T>）

这样做的好处是什么呢？内部类可以直接访问其外部类中的数据，因此，以内部类的方式实现迭代器就天然地将需要迭代的对象（线性表）与迭代器联系起来了。相比于方式❶而言，方式❸更高效，因为方式❸是直接遍历线性表，而方式❶是通过调用线性表的方法来遍历线性表。

方式❸的具体实现代码如下：由于迭代器由内部类实现，因此这里贴出了整个类（包括外部类）的代码：

  1 package linklist;
  2 
  3 import java.util.Iterator;
  4 import java.util.NoSuchElementException;
  5 
  6 public class LList<T> implements ListInterface<T>{
  7 
  8     private Node firstNode;//指向第一个结点的指针，该链表是不带头结点的单链表
  9     private int length;//表示单链表的长度
 10     
 11     //Node类中不需要定义访问属性的get方法以及set方法，因为Node是内部类，内部类的属性可以直接在外部类中被访问
 12     class Node{
 13         //Node是内部类，其外部类中已经定义了T，故可以在这里使用通配符T
 14         private T data;//结点的数据部分
 15         private Node next;//结点的指针部分，指向下一个结点
 16         //Node类中不需要默认构造器
 17         public Node(T dataPortion){
 18             data = dataPortion;
 19         }
 20         public Node(T dataPortion, Node nextNode){
 21             data = dataPortion;
 22             next = nextNode;
 23         }
 24     }
 25     
 26     /*
 27      * 需要在外部类(LList.java)中添加getIterator方法，该方法用来获得迭代器对象
 28      * 这样，外部类对象调用getIterator()得到迭代器对象，该迭代器对象调用next进行线性表的迭代
 29      * 
 30      */
 31     public Iterator<T> getIterator(){
 32         return  new IteratorForLinkList();
 33     }
 34     
 35     private class IteratorForLinkList implements Iterator<T>{
 36         private Node nextNode;//标记当前正在遍历的元素
 37         private IteratorForLinkList(){
 38             nextNode = firstNode;//在内部类中直接访问外部类中的firstNode数据域
 39         }
 40         @Override
 41         public boolean hasNext() {
 42             return nextNode != null;
 43         }
 44         @Override
 45         public T next() {
 46             if(hasNext()){
 47                 Node returnNode = nextNode;
 48                 nextNode = nextNode.next;
 49                 return returnNode.data;
 50             }
 51             else//已经遍历到线性表末尾或线性表为空
 52                 throw new NoSuchElementException("Illegal call to next()" + "iterator is after end of list.");
 53         }
 54         @Override
 55         public void remove() {//该迭代器不支持remove()方法
 56             throw new UnsupportedOperationException("remove() is not supported by this iterator");
 57         }
 58     }
 59     
 60     public LList(){
 61         clear();
 62     }
 63     //获取链表中指定位置处的结点
 64     private Node getNodeAt(int givenPosition){
 65         assert (!isEmpty() && ((1 <= givenPosition) && (givenPosition <= length)));
 66         Node currentNode = firstNode;
 67         for(int counter = 1; counter < givenPosition; counter++){
 68             currentNode = currentNode.next;
 69         }
 70         assert currentNode != null;
 71         return currentNode;
 72     }
 73     
 74     @Override
 75     public boolean add(T newEntry) {
 76         // 将每个新结点插入到链表的末尾，通过getNodeAt()方法来获得最后一个元素的地址
 77         Node newNode = new Node(newEntry);
 78         if(isEmpty()){//插入第一个结点
 79             firstNode = newNode;
 80         }
 81         else{//在其它位置插入结点
 82             Node lastNode = getNodeAt(length);//这里每插入一个元素都需要遍历一次链表，代价较大
 83             lastNode.next = newNode;
 84         }
 85         length++;
 86         return true;
 87     }
 88 
 89     @Override
 90     public boolean add(int givenPosition, T newEntry){//在指定位置处插入结点
 91         boolean isSuccessful = true;
 92         if(givenPosition >= 1 && givenPosition <= length + 1){
 93             Node newNode = new Node(newEntry);
 94             if(isEmpty() || givenPosition == 1){//在第一个位置处插入结点
 95                 newNode.next = firstNode;
 96                 firstNode = newNode;
 97             }
 98             else{//在其它位置插入结点
 99                 Node nodeBefore = getNodeAt(givenPosition - 1);
100                 Node nodeAfter = nodeBefore.next;
101                 nodeBefore.next = newNode;
102                 newNode.next = nodeAfter;
103             }
104             length++;
105         }
106         else
107             isSuccessful = false;
108         return isSuccessful;
109     }
110 
111     @Override
112     public final void clear() {//clear()在构造器中被调用了，所以此外用final修饰符
113         firstNode = null;
114         length = 0;
115     }
116 
117     @Override
118     public T remove(int givenPosition) {//删除指定位置处的结点
119         T result = null;
120         if((!isEmpty()) && ((givenPosition >= 1) && (givenPosition <= length))){
121             if(givenPosition == 1){//删除第一个位置处的结点
122                 result = firstNode.data;
123                 firstNode = firstNode.next;
124             }
125             else//删除表中其它位置结点
126             {
127                 Node nodeBefore = getNodeAt(givenPosition - 1);
128                 Node nodeToRemove = nodeBefore.next;
129                 Node nodeAfter = nodeToRemove.next;
130                 nodeBefore.next = nodeAfter;
131                 result = nodeToRemove.data;
132             }
133             length--;
134         }
135         return result;
136     }
137 
138     @Override
139     public boolean replace(int givenPosition, T newEntry) {//替换指定位置处结点的值
140         boolean isSuccessful = true;
141         if((!isEmpty()) && ((givenPosition >= 1) && (givenPosition <= length))){
142             Node desireNode = getNodeAt(givenPosition);
143             desireNode.data = newEntry;
144         }
145         else
146             isSuccessful = false;
147         return isSuccessful;
148     }
149 
150     @Override
151     public T getEntry(int givenPosition) {//获取指定位置的结点的值
152         T result = null;
153         if((!isEmpty()) && ((givenPosition >= 1) && (givenPosition <= length))){
154             result = getNodeAt(givenPosition).data;
155         }
156         return result;
157     }
158 
159     @Override
160     public boolean contains(T anEntry) {//判断链表中的结点是否包含某个值
161         boolean found = false;
162         Node currentNode = firstNode;
163         while(!found && currentNode != null){
164             if(currentNode.data.equals(anEntry)){
165                 found = true;
166                 break;
167             }
168             currentNode = currentNode.next;
169         }
170         return found;
171     }
172 
173     @Override
174     public int getLength() {//获取链表的长度
175         return length;
176     }
177 
178     @Override
179     public boolean isEmpty() {//判断链表是否为空
180         boolean result;
181         if(length == 0){
182             assert firstNode == null;
183             result = true;
184         }
185         else{
186             assert firstNode != null;
187             result = false;
188         }
189         return result;
190     }
191 
192     @Override
193     public void display() {//遍历链表，显示链表中的每个结点的值
194         Node currentNode = firstNode;
195         while(currentNode != null){
196             System.out.println(currentNode.data);
197             currentNode = currentNode.next;
198         }
199     }
200 }

可以将该LList.java 与 http://www.cnblogs.com/hapjin/p/4549492.html 博客中的LList.java 比较。（注意新增的第26--58行代码，内部类迭代器的具体实现代码）

前者是带有迭代器的线性表实现，后者是不带迭代器的线性表实现。