迭代器模式

清峰大约 9 分钟

迭代器模式

什么是迭代器模式

迭代器模式（Iterator Pattern）是一种行为型设计模式，它提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露该对象的内部表示。迭代器模式将数据的遍历和数据的存储分离开来，使得遍历算法可以独立于数据结构。

迭代器模式的核心思想是：

提供一种统一的方式来访问聚合对象中的元素
不暴露聚合对象的内部结构
支持多种遍历方式（正向、反向等）
为不同的聚合结构提供统一的接口

为什么需要迭代器模式

在实际开发中，我们经常需要遍历各种集合对象，如数组、列表、树、图等。如果没有迭代器模式，客户端代码就需要了解每种集合的内部结构才能进行遍历，这会导致代码耦合度高，难以维护和扩展。迭代器模式通过提供统一的遍历接口，使得客户端代码可以以相同的方式遍历不同的集合对象。

迭代器模式的结构

迭代器模式包含以下几个角色：

迭代器（Iterator）：定义访问和遍历元素的接口
具体迭代器（ConcreteIterator）：实现迭代器接口，完成对聚合对象的遍历
聚合（Aggregate）：定义创建相应迭代器对象的接口
具体聚合（ConcreteAggregate）：实现创建相应迭代器的接口，返回一个合适的迭代器实例

迭代器模式的实现

基本实现

// 迭代器接口
interface Iterator<T> {
    boolean hasNext();
    T next();
    void remove();
}

// 聚合接口
interface Aggregate<T> {
    Iterator<T> createIterator();
}

// 具体聚合 - 自定义列表
class MyList<T> implements Aggregate<T> {
    private List<T> items = new ArrayList<>();
    
    public void add(T item) {
        items.add(item);
    }
    
    public T get(int index) {
        return items.get(index);
    }
    
    public int size() {
        return items.size();
    }
    
    @Override
    public Iterator<T> createIterator() {
        return new ListIterator();
    }
    
    // 具体迭代器
    private class ListIterator implements Iterator<T> {
        private int currentIndex = 0;
        
        @Override
        public boolean hasNext() {
            return currentIndex < items.size();
        }
        
        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return items.get(currentIndex++);
        }
        
        @Override
        public void remove() {
            if (currentIndex <= 0) {
                throw new IllegalStateException();
            }
            items.remove(--currentIndex);
        }
    }
}

// 使用示例
public class IteratorDemo {
    public static void main(String[] args) {
        // 创建聚合对象
        MyList<String> list = new MyList<>();
        list.add("第一个元素");
        list.add("第二个元素");
        list.add("第三个元素");
        list.add("第四个元素");
        
        // 获取迭代器
        Iterator<String> iterator = list.createIterator();
        
        // 使用迭代器遍历
        System.out.println("=== 使用迭代器遍历 ===");
        while (iterator.hasNext()) {
            String item = iterator.next();
            System.out.println(item);
        }
        
        // 再次遍历
        System.out.println("\n=== 再次遍历 ===");
        Iterator<String> iterator2 = list.createIterator();
        while (iterator2.hasNext()) {
            String item = iterator2.next();
            System.out.println(item);
        }
    }
}

反向迭代器实现

// 反向迭代器
class ReverseIterator<T> implements Iterator<T> {
    private MyList<T> list;
    private int currentIndex;
    
    public ReverseIterator(MyList<T> list) {
        this.list = list;
        this.currentIndex = list.size() - 1;
    }
    
    @Override
    public boolean hasNext() {
        return currentIndex >= 0;
    }
    
    @Override
    public T next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        return list.get(currentIndex--);
    }
    
    @Override
    public void remove() {
        throw new UnsupportedOperationException("反向迭代器不支持删除操作");
    }
}

// 扩展聚合接口，支持反向迭代
interface ExtendedAggregate<T> extends Aggregate<T> {
    Iterator<T> createReverseIterator();
}

// 扩展具体聚合
class ExtendedMyList<T> implements ExtendedAggregate<T> {
    private List<T> items = new ArrayList<>();
    
    public void add(T item) {
        items.add(item);
    }
    
    public T get(int index) {
        return items.get(index);
    }
    
    public int size() {
        return items.size();
    }
    
    @Override
    public Iterator<T> createIterator() {
        return new ListIterator();
    }
    
    @Override
    public Iterator<T> createReverseIterator() {
        return new ReverseIterator<>(this);
    }
    
    // 正向迭代器
    private class ListIterator implements Iterator<T> {
        private int currentIndex = 0;
        
        @Override
        public boolean hasNext() {
            return currentIndex < items.size();
        }
        
        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return items.get(currentIndex++);
        }
        
        @Override
        public void remove() {
            if (currentIndex <= 0) {
                throw new IllegalStateException();
            }
            items.remove(--currentIndex);
        }
    }
}

// 使用示例
public class ReverseIteratorDemo {
    public static void main(String[] args) {
        // 创建聚合对象
        ExtendedMyList<String> list = new ExtendedMyList<>();
        list.add("第一个元素");
        list.add("第二个元素");
        list.add("第三个元素");
        list.add("第四个元素");
        
        // 正向遍历
        System.out.println("=== 正向遍历 ===");
        Iterator<String> iterator = list.createIterator();
        while (iterator.hasNext()) {
            String item = iterator.next();
            System.out.println(item);
        }
        
        // 反向遍历
        System.out.println("\n=== 反向遍历 ===");
        Iterator<String> reverseIterator = list.createReverseIterator();
        while (reverseIterator.hasNext()) {
            String item = reverseIterator.next();
            System.out.println(item);
        }
    }
}

迭代器模式的应用场景

集合遍历：Java集合框架中的Iterator就是迭代器模式的典型应用
树结构遍历：二叉树的前序、中序、后序遍历
图结构遍历：图的深度优先搜索、广度优先搜索
数据库查询结果遍历：ResultSet的遍历
文件系统遍历：目录和文件的遍历
XML/JSON解析：节点的遍历

迭代器模式的优缺点

优点

简化聚合类：聚合类不需要包含遍历算法，职责更加单一
支持多种遍历方式：可以同时定义多种遍历方式
易于扩展：增加新的聚合类和迭代器类都很方便
统一接口：为遍历不同的聚合结构提供统一的接口

缺点

增加类的数量：每增加一个聚合类都要增加一个迭代器类
增加系统复杂度：对于简单的遍历操作，使用迭代器模式可能显得过于复杂

迭代器模式与其他模式的比较

与组合模式的区别

迭代器模式：关注如何遍历聚合对象中的元素
组合模式：关注如何将对象组织成树形结构

与访问者模式的区别

迭代器模式：提供遍历聚合对象的方式
访问者模式：在不改变元素类的前提下为元素类增加新的操作

与工厂模式的区别

迭代器模式：关注遍历聚合对象
工厂模式：关注对象的创建

实际项目中的应用

// 二叉树遍历示例
// 二叉树节点
class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int value) {
        this.value = value;
    }
}

// 二叉树
class BinaryTree {
    private TreeNode root;
    
    public BinaryTree(TreeNode root) {
        this.root = root;
    }
    
    // 前序遍历迭代器
    public Iterator<Integer> createPreOrderIterator() {
        return new PreOrderIterator();
    }
    
    // 中序遍历迭代器
    public Iterator<Integer> createInOrderIterator() {
        return new InOrderIterator();
    }
    
    // 后序遍历迭代器
    public Iterator<Integer> createPostOrderIterator() {
        return new PostOrderIterator();
    }
    
    // 前序遍历迭代器实现
    private class PreOrderIterator implements Iterator<Integer> {
        private Stack<TreeNode> stack = new Stack<>();
        
        public PreOrderIterator() {
            if (root != null) {
                stack.push(root);
            }
        }
        
        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }
        
        @Override
        public Integer next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            
            return node.value;
        }
        
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    
    // 中序遍历迭代器实现
    private class InOrderIterator implements Iterator<Integer> {
        private Stack<TreeNode> stack = new Stack<>();
        private TreeNode current;
        
        public InOrderIterator() {
            current = root;
            pushLeftNodes();
        }
        
        private void pushLeftNodes() {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
        }
        
        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }
        
        @Override
        public Integer next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            
            TreeNode node = stack.pop();
            current = node.right;
            pushLeftNodes();
            
            return node.value;
        }
        
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    
    // 后序遍历迭代器实现
    private class PostOrderIterator implements Iterator<Integer> {
        private Stack<TreeNode> stack1 = new Stack<>();
        private Stack<TreeNode> stack2 = new Stack<>();
        
        public PostOrderIterator() {
            if (root != null) {
                stack1.push(root);
                while (!stack1.isEmpty()) {
                    TreeNode node = stack1.pop();
                    stack2.push(node);
                    if (node.left != null) {
                        stack1.push(node.left);
                    }
                    if (node.right != null) {
                        stack1.push(node.right);
                    }
                }
            }
        }
        
        @Override
        public boolean hasNext() {
            return !stack2.isEmpty();
        }
        
        @Override
        public Integer next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return stack2.pop().value;
        }
        
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

// 使用示例
public class BinaryTreeIteratorDemo {
    public static void main(String[] args) {
        // 构建二叉树
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        
        BinaryTree tree = new BinaryTree(root);
        
        // 前序遍历
        System.out.println("=== 前序遍历 ===");
        Iterator<Integer> preOrderIterator = tree.createPreOrderIterator();
        while (preOrderIterator.hasNext()) {
            System.out.print(preOrderIterator.next() + " ");
        }
        System.out.println();
        
        // 中序遍历
        System.out.println("\n=== 中序遍历 ===");
        Iterator<Integer> inOrderIterator = tree.createInOrderIterator();
        while (inOrderIterator.hasNext()) {
            System.out.print(inOrderIterator.next() + " ");
        }
        System.out.println();
        
        // 后序遍历
        System.out.println("\n=== 后序遍历 ===");
        Iterator<Integer> postOrderIterator = tree.createPostOrderIterator();
        while (postOrderIterator.hasNext()) {
            System.out.print(postOrderIterator.next() + " ");
        }
        System.out.println();
    }
}

// 文件系统遍历示例
// 文件系统节点抽象类
abstract class FileSystemNode {
    protected String name;
    
    public FileSystemNode(String name) {
        this.name = name;
    }
    
    public String getName() {
        return name;
    }
    
    public abstract Iterator<FileSystemNode> createIterator();
}

// 文件类
class FileNode extends FileSystemNode {
    public FileNode(String name) {
        super(name);
    }
    
    @Override
    public Iterator<FileSystemNode> createIterator() {
        return new NullIterator();
    }
}

// 目录类
class DirectoryNode extends FileSystemNode {
    private List<FileSystemNode> children = new ArrayList<>();
    
    public DirectoryNode(String name) {
        super(name);
    }
    
    public void add(FileSystemNode node) {
        children.add(node);
    }
    
    public void remove(FileSystemNode node) {
        children.remove(node);
    }
    
    public List<FileSystemNode> getChildren() {
        return children;
    }
    
    @Override
    public Iterator<FileSystemNode> createIterator() {
        return new DirectoryIterator();
    }
    
    // 目录迭代器
    private class DirectoryIterator implements Iterator<FileSystemNode> {
        private int currentIndex = 0;
        
        @Override
        public boolean hasNext() {
            return currentIndex < children.size();
        }
        
        @Override
        public FileSystemNode next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return children.get(currentIndex++);
        }
        
        @Override
        public void remove() {
            if (currentIndex <= 0) {
                throw new IllegalStateException();
            }
            children.remove(--currentIndex);
        }
    }
}

// 空迭代器
class NullIterator implements Iterator<FileSystemNode> {
    @Override
    public boolean hasNext() {
        return false;
    }
    
    @Override
    public FileSystemNode next() {
        throw new NoSuchElementException();
    }
    
    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

// 文件系统遍历器
class FileSystemTraverser {
    public void traverse(FileSystemNode node, int depth) {
        // 打印节点信息
        for (int i = 0; i < depth; i++) {
            System.out.print("  ");
        }
        System.out.println(node.getName());
        
        // 遍历子节点
        Iterator<FileSystemNode> iterator = node.createIterator();
        while (iterator.hasNext()) {
            FileSystemNode child = iterator.next();
            traverse(child, depth + 1);
        }
    }
}

// 使用示例
public class FileSystemIteratorDemo {
    public static void main(String[] args) {
        // 构建文件系统结构
        DirectoryNode root = new DirectoryNode("根目录");
        
        DirectoryNode documents = new DirectoryNode("文档");
        documents.add(new FileNode("简历.doc"));
        documents.add(new FileNode("报告.pdf"));
        
        DirectoryNode images = new DirectoryNode("图片");
        images.add(new FileNode("照片1.jpg"));
        images.add(new FileNode("照片2.png"));
        
        DirectoryNode projects = new DirectoryNode("项目");
        projects.add(new FileNode("项目计划.txt"));
        DirectoryNode javaProject = new DirectoryNode("Java项目");
        javaProject.add(new FileNode("Main.java"));
        javaProject.add(new FileNode("README.md"));
        projects.add(javaProject);
        
        root.add(documents);
        root.add(images);
        root.add(projects);
        root.add(new FileNode("说明.txt"));
        
        // 遍历文件系统
        System.out.println("=== 文件系统结构 ===");
        FileSystemTraverser traverser = new FileSystemTraverser();
        traverser.traverse(root, 0);
    }
}

Java集合框架中的迭代器

// Java集合框架中的迭代器使用示例
public class JavaCollectionIteratorDemo {
    public static void main(String[] args) {
        // List迭代器
        List<String> list = new ArrayList<>();
        list.add("元素1");
        list.add("元素2");
        list.add("元素3");
        
        System.out.println("=== List迭代器 ===");
        Iterator<String> listIterator = list.iterator();
        while (listIterator.hasNext()) {
            String item = listIterator.next();
            System.out.println(item);
            // 可以在遍历过程中删除元素
            if ("元素2".equals(item)) {
                listIterator.remove();
            }
        }
        
        System.out.println("删除元素2后: " + list);
        
        // Set迭代器
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        
        System.out.println("\n=== Set迭代器 ===");
        Iterator<Integer> setIterator = set.iterator();
        while (setIterator.hasNext()) {
            Integer item = setIterator.next();
            System.out.println(item);
        }
        
        // Map迭代器（通过entrySet）
        Map<String, Integer> map = new HashMap<>();
        map.put("键1", 100);
        map.put("键2", 200);
        map.put("键3", 300);
        
        System.out.println("\n=== Map迭代器 ===");
        Iterator<Map.Entry<String, Integer>> mapIterator = map.entrySet().iterator();
        while (mapIterator.hasNext()) {
            Map.Entry<String, Integer> entry = mapIterator.next();
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
        
        // ListIterator（支持双向遍历）
        List<String> list2 = new ArrayList<>();
        list2.add("A");
        list2.add("B");
        list2.add("C");
        
        System.out.println("\n=== ListIterator双向遍历 ===");
        ListIterator<String> listIterator2 = list2.listIterator();
        
        // 正向遍历
        System.out.println("正向遍历:");
        while (listIterator2.hasNext()) {
            int index = listIterator2.nextIndex();
            String item = listIterator2.next();
            System.out.println("索引 " + index + ": " + item);
        }
        
        // 反向遍历
        System.out.println("反向遍历:");
        while (listIterator2.hasPrevious()) {
            int index = listIterator2.previousIndex();
            String item = listIterator2.previous();
            System.out.println("索引 " + index + ": " + item);
        }
    }
}

总结

迭代器模式是一种非常实用的行为型设计模式，它提供了一种统一的方式来访问聚合对象中的元素，而不需要暴露聚合对象的内部结构。在Java集合框架中，迭代器模式得到了广泛应用，为我们提供了便利的集合遍历功能。

使用迭代器模式的关键点：

识别需要遍历的聚合对象
定义迭代器接口
实现具体迭代器类
在聚合类中提供创建迭代器的方法
客户端通过迭代器遍历聚合对象

迭代器模式的优点是简化了聚合类的设计，支持多种遍历方式，并且易于扩展。在实际开发中，当我们需要遍历复杂的数据结构时，迭代器模式是一个很好的选择。特别是在需要支持多种遍历方式或者需要在遍历过程中对集合进行修改时，迭代器模式的优势更加明显。