1.4 迭代器(iterator)

如果我们想遍历数组，这很容易，因为可以用数组的下标跟踪所在的位置，然而在链表中，节点没有这样的下标，怎样才能提供给链表用户类似于数组下标的东西呢？这就是迭代器(iterator)的作用。

我们知道添加到链表中的数据(data)，都会包装成一个节点(node)，节点之间通过引用保存了先后关系(pre、next)。但是由于在获取数据时(如getFirst)，返回的直接是数据(data)，数据本身没有其之后数据的引用，因此无法遍历。

但是node存在这样的引用，如果我们直接把node返回给用户，让用户自己从node获取数据，不就可以实现遍历了吗？我们可以提供一个getFirstNode()方法，然后按照类似以下代码片段进行遍历：

Node node=linkedList.getFirstNode();
while(node!=null){
     Object data=node.getData();
     //. . . 操作数据
    node=node.getNext();//获取下一个node
}

上述这样的方式，的确是可以遍历链表中的所有元素，但是却不是一个好的设计方式，因为我们把链表的基础数据结构Node直接暴露给用户了，普遍的做法就是利用迭代器(iterator)来实现链表的迭代功能。

我们以上一节编写的SingleLinkList为例进行讲解，为其提供一个迭代所有元素的迭代器

关于迭代器，Java中已经相关的接口定义java.util.Iterator，其定义了一个迭代器最基本要实现的功能，虽然实现这个接口不是必要的，但是这里打算实现这个接口

public interface Iterator<E> {
    /** 是否还有更多的元素可以迭代*/
    boolean hasNext();
    /** 返回下一个元素*/
    E next();
    /** 将迭代器当前迭代的元素，从链表中移除*/
    void remove();
}

1、在SingleLinkList中定义一个内部类NodeIterator，实现Iterator接口

private  class NodeIterator<T> implements Iterator<T>{
    private Node node;
    public NodeIterator(Node current) {
        this.node = current;
    }

    @Override
    public boolean hasNext() {
        return node!=null;
    }

    @Override
    public T next() {
        Object data = node.getData();
        node=node.getNext();
        return (T)data ;
    }

    @Override
    public void remove() {
        T t = (T) node.getData();
        SingleLinkList.this.remove(t);
    }
}

2、修改SingleLinkList，新增一个返回迭代器的方法

关于返回迭代器方法的名称，是任意的，不过最好还是符合某种规范，java.lang.Iterable接口，定义了这样一个放回迭代器的方法

public interface Iterable<T> {
    Iterator<T> iterator();
}

其返回类型就是Iterator，现在你可能知道我们让NodeIterator实现Iterator接口的原因了，因为这样，我们就可以将自己写的迭代器通过Java的标准接口返回

现在我们让SingleLinkList实现.Iterable接口，实现这个方法

public class SingleLinkList<T> implements Iterable<T>{
...
    @Override
    public Iterator<T> iterator() {//可以看到，我们构建的时候，是把链表的第一个元素当做构造参数传递给了NodeIterator
        return new NodeIterator<T>(firstNode);
    }
...
}

现在所有的工作已经完成，剩下的就是测试了

@Test
public void testIterator(){
    SingleLinkList<Integer> linkList=new SingleLinkList<Integer>();
    for (int i = 0; i < 10; i++) {
        linkList.addFirst(i);
    }
    System.out.println("链表中元素：");
    linkList.display();
    System.out.println("\n开始迭代：");
    Iterator<Integer> iterator = linkList.iterator();
    while (iterator.hasNext()){
        Integer next = iterator.next();
        System.out.println(next);
    }
}

运行程序，输出：

可以看到我们的迭代器已经正常工作

特别的，由于我们的迭代器实现了Java的标准接口，所以我们可以使用java的增强for循环来进行迭代，如果没有实现这些接口，是无法使用增强for循环的

@Test
public void testIterator(){
    SingleLinkList<Integer> linkList=new SingleLinkList<Integer>();
    for (int i = 0; i < 10; i++) {
        linkList.addFirst(i);
    }
    System.out.println("链表中元素：");
    linkList.display();
    System.out.println("\n开始迭代：");
    //使用增强for循环进行迭代
    for (Integer data : linkList) {
        System.out.println(data);
    }
}