前阵子有个朋友问了我一个问题他写了一个自定义的树形结构想用 for 循环直接遍历结果折腾了半天要么是把内部节点暴露得乱七八糟要么就是遍历逻辑和数据结构死死绑在一起换个遍历方式就得重写一遍。我跟他说你缺的其实是迭代器模式。这个东西听起来特别理论但说人话就是——像翻书一样遍历数据书签一夹翻到哪页算哪页至于书是纸质书、电子书还是连环画翻书的人根本不关心。这篇文章我结合迭代器模式的理论、手写实现以及链表遍历、二叉树前中后序遍历、层序遍历这些常见场景把遍历这件事讲透。适合刚学设计模式的人也适合那些天天用 for 循环但没想过底层原理的人看完你至少能明白两件事迭代器到底解决了什么问题以及怎么在项目里把它用出价值。1. 迭代器模式的设计逻辑为什么非要绕一圈1.1 遍历本来是个简单事复杂在哪先看一个最朴素的场景遍历一个数组。这简单下标从 0 到 length - 1一个 for 循环就完了。但换个数据结构呢链表你不能用下标二叉树你根本不知道下一个节点是谁图就更别提了。这时候你会发现“遍历”这件事本身并不简单它取决于数据结构内部长什么样。传统的做法是让调用方直接操作数据结构内部。比如为了遍历链表你得自己从 head 开始每次拿 node.next为了遍历二叉树你得自己维护一个栈或者队列。这就产生了一个实际问题调用方被迫知道数据结构的每一个内部细节而数据结构一旦变化所有调用方的代码都得跟着改。我在实际项目里见过最典型的例子系统里有个自定义的菜单树一开始用递归遍历后来需求改成按层级输出结果所有调用递归的代码全部要改因为“怎么遍历”这个逻辑散落在各个业务方。这就是紧耦合的代价。迭代器模式的核心就是把“怎么走”这个逻辑从数据结构里抽出来封装成一个独立的对象让调用方只依赖一个统一的遍历接口。1.2 迭代器模式到底解了什么耦迭代器模式的定义其实只有一句话提供一个对象按顺序访问聚合对象中的各个元素而不暴露其内部表示。这句话信息量很大我拆成两层来理解。第一层调用方和数据结构解耦。调用方只跟迭代器打交道调用 next() 拿下一个元素调用 hasNext() 判断有没有下一个至于背后是数组还是链表还是树根本不重要。这就好比你去图书馆找书你只需要顺着书架一排一排看过去至于图书馆内部怎么分架、怎么编号那是图书馆的事。第二层遍历算法和数据存储解耦。同一个数据结构今天想正序遍历明天想倒序遍历后天想隔一个取一个怎么办不用改数据结构本身只要换一个迭代器就行。这就把“数据怎么存”和“数据怎么读”彻底分开了。我用翻书来类比一下数据集合是一本书迭代器是夹在书里的书签它记录了你当前读到哪一页游标位置同时还知道怎么翻到下一页推进规则。你作为读者只需要做两个动作——看当前页当前元素翻页调用 next()。至于这本书是三百页还是三百万页是正文通读还是只看插画都不重要因为你手里有书签按部就班翻就完了。1.3 统一遍历接口带来的隐藏收益解耦只是第一层好处。第二层好处是因为所有迭代器都实现了统一的接口你就可以写一套通用的算法拿到任何数据结构上复用。举个例子。你写了一个过滤函数它接收一个“可以迭代的东西”内部只是反复调用 hasNext() 和 next()不需要知道这东西具体是 List 还是 Set 还是自定义的树。这时候突然来一个需求要用同样的过滤逻辑处理一个自定义的图结构你只需要给这个图写一个迭代器然后把它传给过滤函数一切搞定。这个思路在 Python 里体现得最为明显。Python 的 for 循环根本不关心你迭代的是什么对象只要你实现了iter() 返回一个迭代器或者直接实现了next()它就能 for 起来。这种“面向迭代协议编程”的设计让 Python 的自定义数据结构接入语言生态变得极其简单。Java 的 Iterable 接口同样如此for-each 循环本质上就是编译器帮你把迭代器调用翻译好了而已。2. 迭代器模式的组成结构与核心细节2.1 四个核心角色一个都不能少迭代器模式在 GoF 书里的结构是四个角色我按实际编码的逻辑给你拆开讲。第一个是 Iterator迭代器接口。它通常定义三个方法hasNext() 判断是否还有元素next() 返回当前元素并推进游标有些实现还会加一个 remove() 用来安全删除当前元素。在 Python 里接口不是显式的只要你的类实现了iter() 和next() 就可以被当作迭代器使用。第二个是 ConcreteIterator具体迭代器。这个类内部持有两个东西一是被遍历的聚合对象的引用二是当前游标的位置。游标是什么取决于数据结构。对数组来说游标是下标 index对链表来说游标是当前节点的引用对树来说游标可能是一个栈或者队列里面保存着接下来要访问的节点。第三个是 Aggregate聚合对象接口。它一般只定义一个方法createIterator()返回一个迭代器。在 Java 里对应 Iterable 接口的 iterator() 方法在 Python 里对应iter() 方法。第四个是 ConcreteAggregate具体聚合对象。这就是你真正的数据结构比如 LinkedList、BinaryTree、自定义的菜单树。它负责实现 createIterator()把合适的迭代器返回给调用方。这四个角色里最容易忽略的是最后一个。很多人在设计数据结构时直接在数据结构内部写一个 inorderTraversal() 之类的遍历方法这不叫迭代器模式这只是把遍历方法塞进了数据结构。真正的迭代器模式要求遍历状态游标存放在迭代器对象里而不是存放在数据结构里。这样做的直接好处是你可以在同一个数据结构上同时存在多个迭代器互不干扰。2.2 游标位置的设计决定了迭代器的质量写过迭代器的人都知道最阴险的细节是“hasNext() 和 next() 的配合”。最常见的错误是把游标初始化为 0hasNext() 判断 index sizenext() 返回 list.get(index) 然后 index。看起来没问题但这里有个隐患如果调用方连续调用两次 next() 而不检查 hasNext()就会越界。Java 里 Iterator 接口的设计经验是next() 在游标越界时抛出 NoSuchElementException而 hasNext() 只是预判不改变状态。这样设计的好处是调用方有两种使用方式一是安全遍历先 hasNext 再 next二是快速失败直接 next越界时抛异常。两种场景都覆盖了。还有一个我踩过坑的地方游标的初始位置。如果你让游标初始指向“第一个元素”那么 hasNext() 的判断就变成了“游标是否不为空”而 next() 要先保存当前元素、再推进游标、再返回保存的元素。这种设计会让 next() 和 hasNext() 的逻辑稍微绕一点但好处是它天然支持“当前元素”这个概念。有些迭代器会提供 current() 方法来获取当前元素这时候游标初始指向第一个元素就更自然。2.3 生成器迭代器的“懒加载”形态聊迭代器就绕不开 Python 的生成器这是迭代器模式一个极其漂亮的实现形态。用 yield 关键字写出来的函数调用时不会执行函数体而是返回一个生成器对象这个生成器对象就是一个迭代器。我举个实际例子。你有一个超级大的文件几 GB 那种你不能一次性读进内存但你又想逐行处理。这时候如果手动写迭代器类会很繁琐而用生成器只要三行def read_large_file(file_path): with open(file_path, r, encodingutf-8) as f: for line in f: yield line.strip()这个生成器内部自动维护了游标每次 next() 只读一行到内存整个文件的遍历过程内存占用几乎为常数。这就是懒加载的威力迭代器不一定非要等所有数据准备好才能开始遍历它可以边走边产数据。这个特性和流式处理、管道处理天然契合。我用翻书来类比普通集合的迭代器像一本已经印好的书页数固定生成器的迭代器像边写边出版的连载小说你每翻一页出版社才把那页的内容写完。读者体验是一样的——一页一页翻——但内存和节奏完全不同。3. 实操从链表到二叉树的遍历实战3.1 五分钟手写一个链表迭代器光讲理论没意思我直接带大家写代码。先写一个最简单的单向链表再给它配上迭代器。你不用去 IDE 里新建工程我这里的代码足够清晰你直接照着敲就能跑通。class Node: def __init__(self, data): self.data data self.next None class LinkedList: def __init__(self): self._head None def append(self, data): if self._head is None: self._head Node(data) return cur self._head while cur.next is not None: cur cur.next cur.next Node(data) def __iter__(self): return LinkedListIterator(self._head) class LinkedListIterator: def __init__(self, head): self._current head def __iter__(self): return self def __next__(self): if self._current is None: raise StopIteration data self._current.data self._current self._current.next return data用起来就是普通的 for 循环ll LinkedList() ll.append(1) ll.append(2) ll.append(3) for value in ll: print(value)这段代码的核心在于 LinkedListIterator 内部持有 LinkedList 的头节点游标就是 _current。每次 next() 先保存当前节点数据再把游标推进到 next 节点。当 _current 为 None 时抛出 StopIteration告诉 for 循环遍历结束。这个实现里有一个细节值得琢磨为什么 LinkedListIterator 自己也要实现iter() 并返回 self因为 Python 的 for 循环会先调用 iter(obj) 获取迭代器而 iter() 对迭代器本身调用时要求它返回自身。这保证了同一个迭代器对象可以被 for 循环直接使用也可以在嵌套场景中保持一致性。Java 版本的思路完全一样区别只是语法上要显式实现 Iterable 和 Iterator 两个接口。注意 Java 的 Iterator 接口位于 java.util 包LinkedList 需要实现 Iterable 内部通过匿名内部类或者独立类来创建自己的 Iterator。3.2 二叉树的前中后序遍历迭代器怎么玩二叉树的遍历比链表复杂一个量级因为游标不再是简单的 next 指针。前序、中序、后序遍历的迭代器实现本质上是把递归遍历时的隐式调用栈变成一个显式的栈对象。先回顾一下递归写法。前序遍历就是“先访问根再递归左子树再递归右子树”中序是“先递归左子树访问根再递归右子树”后序是“先递归左子树再递归右子树最后访问根”。递归之所以能实现这种复杂的访问顺序是因为系统帮我们维护了一个函数调用栈。迭代器要干的事就是自己维护这个栈。写一个二叉树中序遍历的迭代器class InOrderIterator: def __init__(self, root): self._stack [] self._push_left(root) def _push_left(self, node): while node is not None: self._stack.append(node) node node.left def __iter__(self): return self def __next__(self): if not self._stack: raise StopIteration node self._stack.pop() self._push_left(node.right) return node.data这段代码需要好好解释一下。中序迭代器的核心思想是先把根节点的所有左子树依次压栈这样栈顶就是整棵树“最左侧”的节点它就是中序要访问的第一个节点。每次访问完栈顶节点后把它的右子节点的所有左子树再压栈这样就保持了中序“左-根-右”的顺序。用 _push_left 这个名字是有讲究的它封装了一个循环逻辑也是这个迭代器的核心。如果你把这段逻辑直接塞进next里代码会很难读而且容易在状态维护上出 bug。封装成私有方法之后迭代器的推进逻辑就变得非常清晰。前序遍历的迭代器相对简单。访问顺序是根、左、右也就是每弹出一个节点立刻访问它然后把右子树和左子树依次压栈注意先压右再压左因为栈是后进先出。class PreOrderIterator: def __init__(self, root): self._stack [root] def __next__(self): if not self._stack: raise StopIteration node self._stack.pop() if node.right is not None: self._stack.append(node.right) if node.left is not None: self._stack.append(node.left) return node.data后序遍历的迭代器实现就绕一点一个常见的技巧是用两个栈或者用一个栈保存“访问标记”。我先说双栈法。第一个栈用来做“根右左”的遍历把访问顺序压到第二个栈里最后从第二个栈弹出来就是“左右根”的后序顺序。思路不复杂但代码量明显增加。还有一个更取巧的方式既然后序是“左右根”那能不能先走访根右左再反转结果这种思路和双栈法本质一样但如果你只是为了输出序列确实可以先把结果收集到列表里再反转。不过作为迭代器双栈法才是正统因为它保持了“懒”的特性——不需要一次性遍历完整棵树才能开始返回第一个结果。3.3 层序遍历迭代器和队列的强强联手层序遍历也叫广度优先遍历跟前面的前中后序都不同它不走“先深入再回溯”的路子而是逐层从左到右扫描。实现的关键是队列不是栈。具体做法先把根节点入队。只要队列不为空就出队一个节点访问它然后把它的左孩子和右孩子依次入队。这样下一轮访问时自然就是下一层的节点了。用翻书来类比前序中序后序像你把一本书从中间某页读进去然后顺着引用关系跳来跳去而层序遍历像逐页通读每翻完一页就把这一页提到的所有页码记到一个待办列表里按顺序一个个去读。手动实现一个层序遍历迭代器from collections import deque class LevelOrderIterator: def __init__(self, root): self._queue deque() if root is not None: self._queue.append(root) def __iter__(self): return self def __next__(self): if not self._queue: raise StopIteration node self._queue.popleft() if node.left is not None: self._queue.append(node.left) if node.right is not None: self._queue.append(node.right) return node.data这里用 deque 而不是 list是因为 list 的 pop(0) 操作是 O(n) 的而 deque 的 popleft() 是 O(1)。在遍历大数据量的树时这个性能差异是实打实的。如果你用 list 写层序遍历数据量一上来就会明显变慢。层序遍历和迭代器模式的适配度很高。迭代器的接口就是 next() / hasNext()而层序遍历的推进逻辑正好是“出队一个节点 入队它的孩子”。这个模式你甚至可以推广到图的广度优先遍历上只要在入队时加一个 visited 集合防止重复访问就行。迭代器封装这个逻辑之后外部调用方完全感觉不到“队列”的存在这就是模式的意义。3.4 遍历中删除元素的经典坑我知道很多人看到“遍历”这个词第一个想到的问题是在遍历的同时删除/修改元素到底怎么处理才安全。这个坑我踩过相信大家也都踩过。先说一个最常见的错误操作Python 里 for 循环遍历 list 的同时删除元素arr [1, 2, 3, 4, 5] for x in arr: if x 3: arr.remove(x)这代码看起来没什么问题但实际上是 bug。因为 for 循环的迭代器内部维护了一个下标remove 之后后面的元素会往前移一位导致迭代器跳过了一个本该被访问的元素。结果就是改完之后数组内容变了但遍历过程可能漏元素甚至逻辑混乱。更典型的场景是在循环里删除多个元素。比如你想把 [1, 2, 3, 4, 5] 里所有偶数都删掉如果直接在遍历中删你会发现删不干净。原因是删除元素导致索引偏移每次删除后有一个元素被跳过了。解决方案有几个第一倒序遍历。从数组末尾往前遍历删除元素时前面的元素下标不变不会发生偏移问题。Python 里可以用for i in range(len(arr) - 1, -1, -1)。第二建立新列表。用列表推导式或 filter 生成一个新列表而不是在原列表上删。这是最 Pythonic 的做法也是我比较推荐的做法。第三使用迭代器自带的 remove() 方法。Java 的 Iterator 接口自带 remove()它内部保证了删除当前元素不会破坏遍历状态。但注意这个 remove() 必须在 next() 之后紧挨着调用否则会抛 IllegalStateException。坑这个东西踩过一次就有记忆。我的建议是默认用“建新列表”的思路因为它语义清晰、不会出错、性能也不差只有确实需要原地修改内存对象时才考虑迭代器的 remove()。4. 常见问题与排查技巧实录4.1 fail-fast 机制为什么迭代器越遍历越报错Java 的集合类里有一个著名的异常叫 ConcurrentModificationException。我当年第一次遇到时完全懵了我只是在 for-each 循环里删了一个元素怎么就抛异常了这背后的机制叫 fail-fast。简单说ArrayList 内部有一个 modCount 字段每次结构性修改add、remove都会让 modCount 加一。ArrayList 的迭代器里保存了一个 expectedModCount 快照每次调用 next() 都会比较两者是否一致不一致就抛异常。这个设计的初衷是好的防止在遍历过程中集合被修改导致迭代状态不可预测。如果你在遍历的同时删元素迭代器的游标可能会指向错误位置甚至出现元素遗漏或重复访问。fail-fast 就是要把这种不确定性问题提前暴露出来宁可抛异常也不能静默产生错误结果。但这里有个非常容易误伤的场景多线程环境下一个线程遍历、另一个线程删元素即使删的元素跟遍历完全无关迭代器也会检测到 modCount 变化并抛异常。所以 fail-fast 并不能保证多线程并发安全它只是一种“快速失败”的防御机制。真正要并发安全请用 ConcurrentHashMap 或者 CopyOnWriteArrayList。我从实操角度给大家一个排查建议看到 ConcurrentModificationException先检查是不是同一个线程里边遍历边修改如果不是检查是不是多线程共享同一个集合且有人写操作。不要在 for-each 里做任何结构性修改要么用迭代器的 remove()要么收集到一个待删列表里遍历结束后统一删除。4.2 树形结构递归遍历的风险为什么大树会崩用递归做树的遍历代码确实简洁优雅。中序遍历递归写法def inorder_traversal(node): if node is None: return inorder_traversal(node.left) print(node.data) inorder_traversal(node.right)三行代码就把事情说完了。但递归有一个致命的问题函数调用栈的深度是有限制的。Python 默认的递归深度是 1000 层左右Java 的默认栈大小也就几百 KB 到 1MB 不等。当二叉树的深度超过这个限制递归就会栈溢出。在项目实施里树的高度往往深得离谱。比如一个 1000 万条记录的层级分类表你很难保证树的深度只有几十层。所以我一直有一个原则递归写起来爽但上线前要想清楚最坏的树深度。如果树可能很深就用迭代器 显式栈来替代递归。我前面写的 InOrderIterator 就是这样一个替代方案。它把递归时的隐式调用栈换成了显式的 list 当栈内存消耗是可以预估的不会因为递归深度而崩溃。同样的代码逻辑改用迭代器之后一个 for 循环就能完成整棵树的遍历。很多人的误区是觉得迭代器写法绕但实际写过之后你会发现它和递归只是“一个左一个右”的差异。递归的每次函数调用相当于往隐式栈里压入一个状态迭代器的每次 next()相当于从显式栈里弹出一个节点、再压入它的子节点。栈的操作是互相对应的熟了之后根本不绕。4.3 迭代器状态共享的隐蔽问题再分享一个很容易踩的隐蔽坑多个迭代器之间的状态隔离问题。迭代器模式的一个设计要点就是“每次调用 createIterator() 返回一个新的迭代器对象”。如果你误用了同一个迭代器对象就会出现非常诡异的 bug。比如你有两个嵌套循环想遍历同一个 LinkedListfor x in linked_list: for y in linked_list: ...如果 LinkedList 的iter() 每次都返回同一个迭代器实例那么内层循环会消耗外层循环的游标位置。结果就是外层循环只执行了一次内层循环第一次就把所有元素遍历完了。这个问题在 C 里曾经是一个非常经典的误用场景Java 和 Python 由于语言约束很少出现所以迭代器是廉价的、可丢弃的一次性对象。它的生命周期应该很短随用随建用完就扔。数据结构的iter() 或 iterator() 方法每次都要创建全新实例绝不能把迭代器状态存在数据结构内部。4.4 遍历相关错误排查速查表我把遍历中常见的报错和现象整理成一张表方便大家在项目里快速定位。现象原因解决方案for 循环中删除元素后结果不对索引偏移跳过了部分元素倒序遍历、建新列表、使用迭代器 removeJava 抛 ConcurrentModificationException遍历中修改了集合结构使用 CopyOnWriteArrayList、收集待删元素统一删除Python 抛 StopIteration 但 for 循环正常手动调用 next() 越界在循环体中用 try/except 捕获或先检查 hasNext树形结构递归遍历时栈溢出树的深度超过递归极限用迭代器 显式栈替代递归嵌套循环遍历同一个集合但外层提前结束多个迭代器共享了状态确保 createIterator() 每次返回新迭代器对象自定义迭代器 for 循环不执行未实现iter() 或next()检查协议方法签名和返回值排查顺序建议从上往下先确认是不是结构性修改的问题再确认是不是递归深度的问题最后检查迭代器对象是否被共享。大多数遍历相关的疑难杂症都逃不出这几类。5. 从迭代器出发看遍历的全局思路5.1 一个思路打通所有遍历都是“游标 推进规则”写到这儿我想停下来做个贯穿性的总结因为这是我在反复写迭代器过程中最大的体会。你去看链表遍历、二叉树前中后序、层序遍历甚至目录树的遍历、JSON 嵌套对象的递归处理它们本性里都是一回事一个游标表达你当前在哪里一条推进规则告诉你下一步怎么走。链表的游标是当前节点推进规则是 current current.next。二叉树中序的游标是“当前节点 栈里的祖先”推进规则是“如果有右子树就去右子树的最左否则弹栈”。层序的游标是整个队列推进规则是“出队一个、入队它的孩子”。一旦你拥有这种视角写任何遍历代码都变成了一件机械的事先想清楚游标是什么再想清楚推进规则是什么。游标和规则定了代码只是把它们翻译成语言语法而已。这就是为什么我强烈建议每个人都手写一次迭代器——不是为了在项目里用而是为了建立这种“遍历思维”。5.2 什么时候该手写迭代器什么时候别折腾迭代器模式是好东西但也不是所有场景都值得用。我总结了一套自己的取舍标准。如果你的数据结构只是一个普通数组或者哈希表直接用语言内置的 for 循环就够了别脱裤子放屁手写迭代器。当以下情况出现时才考虑自定义迭代器第一遍历逻辑复杂度高。比如二叉树遍历、图遍历、层级结构遍历这类数据结构的遍历规则涉及栈或队列维护写迭代器可以把复杂逻辑从业务代码中隔离出去。第二需要多种遍历方式。同一套数据既要正序又要倒序既要深度又要广度。这时候为每种遍历方式实现一个迭代器类互不干扰可插拔比在数据结构里塞一堆 traversal 方法优雅得多。第三希望统一处理异构数据。不同数据结构相同遍历接口让上层算法通用化。这种情况下迭代器模式几乎是必须的因为只有这样才能把集合和算法彻底解耦。第四数据是懒加载的。比如从数据库游标、网络流、大文件中读取数据用迭代器包装一层可以让调用方以统一方式消费数据而不用担心数据量大小。在项目里我做选择时还有一个很实际的角度团队里其他人能不能快速理解。如果只是自己写个小工具怎么炫怎么来都行但如果是多人协作的公共模块我会倾向用最简单、最显式的写法让后来接手的人看一眼就明白逻辑。迭代器模式的封装很优雅但如果调用方普遍不太熟悉反而可能变成维护负担。5.3 翻书哲学游标式设计与分页思想标题说“像翻书一样遍历数据”这个比喻背后其实还藏着一种很实用的设计思想游标式数据访问。在分页查询、流式处理这些场景下它的意义远大于普通的 for 循环。我举个例子。数据库里有几百万行数据你不可能一次性全查出来加载到内存。正常的做法是分页。但传统分页有个问题按页码跳转时如果期间有新数据插入用户看到的列表顺序可能会打乱。此时更稳的方案是基于游标的分页记录当前页最后一条数据的位置下一页从该位置之后继续取。这种游标分页的思路和迭代器模式里的游标如出一辙。迭代器维护“当前走到哪了”推进时基于当前位置计算下一步而不是从头开始数。区别在于迭代器的游标通常是一个对象引用或数组下标而游标分页的游标可能是一个自增 ID、时间戳或者加密的字符串 token。但底层逻辑是共通的不要把整个遍历过程的状态分散在各处而是封装成一个独立的、可传递的游标对象。再说说文件读取。用 open() 读文件时文件句柄本身就是一个游标readline() 每次读一行并推进游标。Python 的 for line in file 之所以能工作正是因为文件对象实现了迭代器协议它的next() 负责从磁盘读取下一行。这就是迭代器模式融入语言底层的典型例子。所以你会发现迭代器模式并不是一个生硬的设计模式概念它其实是很多系统设计里朴素思想的理论化总结。翻书是遍历分页是遍历读文件也是遍历。人天生就在和“遍历集合”打交道迭代器只是把这个动作规范化、通用化了。6. 核心代码实战整合一个完整示例6.1 从集合到迭代器的完整 Java 示例前面 Python 代码写得比较细这里用一个完整的 Java 示例来展示迭代器模式的经典结构。场景自定义一个可以存储任意数量元素的集合类支持通过迭代器遍历。import java.util.Iterator; import java.util.NoSuchElementException; public class SimpleListT implements IterableT { private Object[] elements; private int size; public SimpleList(int capacity) { elements new Object[capacity]; size 0; } public void add(T item) { if (size elements.length) { // 扩容 Object[] newElements new Object[elements.length * 2]; System.arraycopy(elements, 0, newElements, 0, elements.length); elements newElements; } elements[size] item; } Override public IteratorT iterator() { return new SimpleIterator(); } private class SimpleIterator implements IteratorT { private int cursor 0; Override public boolean hasNext() { return cursor size; } Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } return (T) elements[cursor]; } } }这个示例有几个关键设计。第一SimpleList 实现了 Iterable 也就是说它可以通过 for-each 循环遍历。第二内部类 SimpleIterator 直接访问外部类的 elements 数组和 size 字段Java 的内部类机制让迭代器可以很方便地访问聚合对象的内部状态。第三next() 中先判断 hasNext()没有元素时抛 NoSuchElementException这是 Java Iterator 接口的标准约定。使用的时候SimpleListString list new SimpleList(4); list.add(Java); list.add(Python); list.add(Go); for (String lang : list) { System.out.println(lang); }for-each 循环在编译时会转换成迭代器调用。这行代码背后发生的事情是编译器生成for (IteratorString it list.iterator(); it.hasNext(); )的等价代码。这个转换看起来很小但意义重大——它让所有实现 Iterable 接口的类都自动获得了 for-each 的能力。库的提供者只需要实现一个迭代器所有使用者立刻获得统一的遍历语法。6.2 把迭代器思想扩展到更复杂的聚合结构前面的 SimpleList 是数组结构的迭代器实现相对简单。实际上迭代器模式的精华在复杂结构上才能体现得最充分。比如一个自定义的树节点想要支持多种遍历方式先定义树节点再分别实现前序迭代器、中序迭代器和层序迭代器。Node 类class TreeNode: def __init__(self, data): self.data data self.left None self.right None给 TreeNode 加一个方法返回不同策略的迭代器def iter_preorder(self): return PreOrderIterator(self) def iter_inorder(self): return InOrderIterator(self) def iter_levelorder(self): return LevelOrderIterator(self)调用方可以这样使用root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3) root.left.left TreeNode(4) root.left.right TreeNode(5) print(前序:, [n.data for n in list(root.iter_preorder())]) print(中序:, [n.data for n in list(root.iter_inorder())]) print(层序:, [n.data for n in list(root.iter_levelorder())])注意这里的每个 iter_xxx 方法都返回一个新的迭代器实例并且遍历逻辑封装在各个迭代器类里TreeNode 本身完全不需要知道自己该怎么被遍历。这正是迭代器模式的核心遍历的不是数据结构内部的事而是一个外部策略。这种设计在实际项目中的价值我用一个真实经历来说明。之前做一个规则引擎规则是用树形结构组织的。因为业务需要有时要深度优先执行规则有时要广度优先执行。最开始我把遍历逻辑写死在树的执行方法里结果每次需求变更都心惊胆战。后来把遍历逻辑抽成迭代器树结构只负责存节点三种遍历方式分别写成独立的迭代器类。之后接新需求只要由调用方指定用哪种迭代器树结构一行都不用改。这就是经验中的教训。6.3 迭代器的“幂等”与“安全”边界再补充一个容易被忽略的工程细节。有些迭代器是“一次性”的——遍历完就没用了有些迭代器可以支持 reset。这取决于你如何设计游标的初始化。一次性迭代器的游标在构造函数里初始化每次 next() 推进后不可回退。重置迭代器就是在迭代器类里加一个reset()方法把游标重置回初始位置。Java 的 Iterator 接口没有 reset 方法但你自己实现时完全可以加。我遇到一个场景需要对同一份数据反复遍历多次每次都从头开始。当时没有场景重建迭代器而是直接在迭代器上做了 reset少写了不少代码。不过迭代器还有一个安全边界需要强调迭代器创建之后如果聚合数据结构被大量修改增删元素迭代器的游标和数据结构的新状态之间就可能不一致。即使是不抛异常的迭代器比如 Python 的 list 迭代器也可能出现漏元素或重复访问。所以一个经验准则是迭代器一旦创建尽量在遍历期间不要修改数据结构的结构。如果确实需要同时修改和遍历务必先评估清楚你依赖的是哪种迭代器行为。7. 我在实际项目里对迭代器模式的一些体会写了这么多最后分享一点我个人的实际体会吧。迭代器这个模式看起来简单但真正理解它需要从“遍历”这个行为抽象到“游标”这个哲学概念。几年前我也是那个只会在 for 循环里写 i 的人直到自己手写了链表、二叉树、层序迭代器之后才开始真正理解什么叫“数据的读取与数据的存储分离”。如果你刚接触迭代器模式我的建议是不要只看文章一定要自己动手写一遍。先写一个链表的迭代器再写一个二叉树中序的迭代器最后写一个层序的迭代器。这三种结构的迭代器难度递增写完之后你会发现你对遍历的理解会上一个台阶。尤其是当你发现自己写的树迭代器能直接套进 for 循环里用的时候那种“原来设计模式是这样改善代码的”的感觉是看多少文章都换不来的。还有一个小技巧在复杂的数据结构设计阶段顺手就把迭代器规划进去。很多设计模式的问题出在使用阶段不如出现在设计阶段。如果你的数据结构定位是会被外部模块反复遍历的那么从一开始就给它设计好迭代器接口比后续再重构要省太多力气。我之前那个规则引擎的教训就是最好的例子。最后再聊一个实践细节。迭代器的命名和文档也很重要尤其是当一个数据结构支持多种遍历方式时。如果你不明确告诉使用者“这是按深度优先顺序的”“这是按层级顺序的”别人极有可能拿错迭代器输出看起来完全正确、实际语义不对的数据。所以我在写这类代码时不仅类名会精确到 PreOrder / InOrder / LevelOrder还会在文档注释里写清楚每种迭代器的遍历规则和典型用途。这是很多人忽略的地方但对团队协作的价值极大。像翻书一样遍历数据书签往前一移下一页就来了。这种简单而稳的抽象真的值得每个程序员把它吃透。
迭代器模式：像翻书一样遍历链表、二叉树与生成器数据
前阵子有个朋友问了我一个问题他写了一个自定义的树形结构想用 for 循环直接遍历结果折腾了半天要么是把内部节点暴露得乱七八糟要么就是遍历逻辑和数据结构死死绑在一起换个遍历方式就得重写一遍。我跟他说你缺的其实是迭代器模式。这个东西听起来特别理论但说人话就是——像翻书一样遍历数据书签一夹翻到哪页算哪页至于书是纸质书、电子书还是连环画翻书的人根本不关心。这篇文章我结合迭代器模式的理论、手写实现以及链表遍历、二叉树前中后序遍历、层序遍历这些常见场景把遍历这件事讲透。适合刚学设计模式的人也适合那些天天用 for 循环但没想过底层原理的人看完你至少能明白两件事迭代器到底解决了什么问题以及怎么在项目里把它用出价值。1. 迭代器模式的设计逻辑为什么非要绕一圈1.1 遍历本来是个简单事复杂在哪先看一个最朴素的场景遍历一个数组。这简单下标从 0 到 length - 1一个 for 循环就完了。但换个数据结构呢链表你不能用下标二叉树你根本不知道下一个节点是谁图就更别提了。这时候你会发现“遍历”这件事本身并不简单它取决于数据结构内部长什么样。传统的做法是让调用方直接操作数据结构内部。比如为了遍历链表你得自己从 head 开始每次拿 node.next为了遍历二叉树你得自己维护一个栈或者队列。这就产生了一个实际问题调用方被迫知道数据结构的每一个内部细节而数据结构一旦变化所有调用方的代码都得跟着改。我在实际项目里见过最典型的例子系统里有个自定义的菜单树一开始用递归遍历后来需求改成按层级输出结果所有调用递归的代码全部要改因为“怎么遍历”这个逻辑散落在各个业务方。这就是紧耦合的代价。迭代器模式的核心就是把“怎么走”这个逻辑从数据结构里抽出来封装成一个独立的对象让调用方只依赖一个统一的遍历接口。1.2 迭代器模式到底解了什么耦迭代器模式的定义其实只有一句话提供一个对象按顺序访问聚合对象中的各个元素而不暴露其内部表示。这句话信息量很大我拆成两层来理解。第一层调用方和数据结构解耦。调用方只跟迭代器打交道调用 next() 拿下一个元素调用 hasNext() 判断有没有下一个至于背后是数组还是链表还是树根本不重要。这就好比你去图书馆找书你只需要顺着书架一排一排看过去至于图书馆内部怎么分架、怎么编号那是图书馆的事。第二层遍历算法和数据存储解耦。同一个数据结构今天想正序遍历明天想倒序遍历后天想隔一个取一个怎么办不用改数据结构本身只要换一个迭代器就行。这就把“数据怎么存”和“数据怎么读”彻底分开了。我用翻书来类比一下数据集合是一本书迭代器是夹在书里的书签它记录了你当前读到哪一页游标位置同时还知道怎么翻到下一页推进规则。你作为读者只需要做两个动作——看当前页当前元素翻页调用 next()。至于这本书是三百页还是三百万页是正文通读还是只看插画都不重要因为你手里有书签按部就班翻就完了。1.3 统一遍历接口带来的隐藏收益解耦只是第一层好处。第二层好处是因为所有迭代器都实现了统一的接口你就可以写一套通用的算法拿到任何数据结构上复用。举个例子。你写了一个过滤函数它接收一个“可以迭代的东西”内部只是反复调用 hasNext() 和 next()不需要知道这东西具体是 List 还是 Set 还是自定义的树。这时候突然来一个需求要用同样的过滤逻辑处理一个自定义的图结构你只需要给这个图写一个迭代器然后把它传给过滤函数一切搞定。这个思路在 Python 里体现得最为明显。Python 的 for 循环根本不关心你迭代的是什么对象只要你实现了iter() 返回一个迭代器或者直接实现了next()它就能 for 起来。这种“面向迭代协议编程”的设计让 Python 的自定义数据结构接入语言生态变得极其简单。Java 的 Iterable 接口同样如此for-each 循环本质上就是编译器帮你把迭代器调用翻译好了而已。2. 迭代器模式的组成结构与核心细节2.1 四个核心角色一个都不能少迭代器模式在 GoF 书里的结构是四个角色我按实际编码的逻辑给你拆开讲。第一个是 Iterator迭代器接口。它通常定义三个方法hasNext() 判断是否还有元素next() 返回当前元素并推进游标有些实现还会加一个 remove() 用来安全删除当前元素。在 Python 里接口不是显式的只要你的类实现了iter() 和next() 就可以被当作迭代器使用。第二个是 ConcreteIterator具体迭代器。这个类内部持有两个东西一是被遍历的聚合对象的引用二是当前游标的位置。游标是什么取决于数据结构。对数组来说游标是下标 index对链表来说游标是当前节点的引用对树来说游标可能是一个栈或者队列里面保存着接下来要访问的节点。第三个是 Aggregate聚合对象接口。它一般只定义一个方法createIterator()返回一个迭代器。在 Java 里对应 Iterable 接口的 iterator() 方法在 Python 里对应iter() 方法。第四个是 ConcreteAggregate具体聚合对象。这就是你真正的数据结构比如 LinkedList、BinaryTree、自定义的菜单树。它负责实现 createIterator()把合适的迭代器返回给调用方。这四个角色里最容易忽略的是最后一个。很多人在设计数据结构时直接在数据结构内部写一个 inorderTraversal() 之类的遍历方法这不叫迭代器模式这只是把遍历方法塞进了数据结构。真正的迭代器模式要求遍历状态游标存放在迭代器对象里而不是存放在数据结构里。这样做的直接好处是你可以在同一个数据结构上同时存在多个迭代器互不干扰。2.2 游标位置的设计决定了迭代器的质量写过迭代器的人都知道最阴险的细节是“hasNext() 和 next() 的配合”。最常见的错误是把游标初始化为 0hasNext() 判断 index sizenext() 返回 list.get(index) 然后 index。看起来没问题但这里有个隐患如果调用方连续调用两次 next() 而不检查 hasNext()就会越界。Java 里 Iterator 接口的设计经验是next() 在游标越界时抛出 NoSuchElementException而 hasNext() 只是预判不改变状态。这样设计的好处是调用方有两种使用方式一是安全遍历先 hasNext 再 next二是快速失败直接 next越界时抛异常。两种场景都覆盖了。还有一个我踩过坑的地方游标的初始位置。如果你让游标初始指向“第一个元素”那么 hasNext() 的判断就变成了“游标是否不为空”而 next() 要先保存当前元素、再推进游标、再返回保存的元素。这种设计会让 next() 和 hasNext() 的逻辑稍微绕一点但好处是它天然支持“当前元素”这个概念。有些迭代器会提供 current() 方法来获取当前元素这时候游标初始指向第一个元素就更自然。2.3 生成器迭代器的“懒加载”形态聊迭代器就绕不开 Python 的生成器这是迭代器模式一个极其漂亮的实现形态。用 yield 关键字写出来的函数调用时不会执行函数体而是返回一个生成器对象这个生成器对象就是一个迭代器。我举个实际例子。你有一个超级大的文件几 GB 那种你不能一次性读进内存但你又想逐行处理。这时候如果手动写迭代器类会很繁琐而用生成器只要三行def read_large_file(file_path): with open(file_path, r, encodingutf-8) as f: for line in f: yield line.strip()这个生成器内部自动维护了游标每次 next() 只读一行到内存整个文件的遍历过程内存占用几乎为常数。这就是懒加载的威力迭代器不一定非要等所有数据准备好才能开始遍历它可以边走边产数据。这个特性和流式处理、管道处理天然契合。我用翻书来类比普通集合的迭代器像一本已经印好的书页数固定生成器的迭代器像边写边出版的连载小说你每翻一页出版社才把那页的内容写完。读者体验是一样的——一页一页翻——但内存和节奏完全不同。3. 实操从链表到二叉树的遍历实战3.1 五分钟手写一个链表迭代器光讲理论没意思我直接带大家写代码。先写一个最简单的单向链表再给它配上迭代器。你不用去 IDE 里新建工程我这里的代码足够清晰你直接照着敲就能跑通。class Node: def __init__(self, data): self.data data self.next None class LinkedList: def __init__(self): self._head None def append(self, data): if self._head is None: self._head Node(data) return cur self._head while cur.next is not None: cur cur.next cur.next Node(data) def __iter__(self): return LinkedListIterator(self._head) class LinkedListIterator: def __init__(self, head): self._current head def __iter__(self): return self def __next__(self): if self._current is None: raise StopIteration data self._current.data self._current self._current.next return data用起来就是普通的 for 循环ll LinkedList() ll.append(1) ll.append(2) ll.append(3) for value in ll: print(value)这段代码的核心在于 LinkedListIterator 内部持有 LinkedList 的头节点游标就是 _current。每次 next() 先保存当前节点数据再把游标推进到 next 节点。当 _current 为 None 时抛出 StopIteration告诉 for 循环遍历结束。这个实现里有一个细节值得琢磨为什么 LinkedListIterator 自己也要实现iter() 并返回 self因为 Python 的 for 循环会先调用 iter(obj) 获取迭代器而 iter() 对迭代器本身调用时要求它返回自身。这保证了同一个迭代器对象可以被 for 循环直接使用也可以在嵌套场景中保持一致性。Java 版本的思路完全一样区别只是语法上要显式实现 Iterable 和 Iterator 两个接口。注意 Java 的 Iterator 接口位于 java.util 包LinkedList 需要实现 Iterable 内部通过匿名内部类或者独立类来创建自己的 Iterator。3.2 二叉树的前中后序遍历迭代器怎么玩二叉树的遍历比链表复杂一个量级因为游标不再是简单的 next 指针。前序、中序、后序遍历的迭代器实现本质上是把递归遍历时的隐式调用栈变成一个显式的栈对象。先回顾一下递归写法。前序遍历就是“先访问根再递归左子树再递归右子树”中序是“先递归左子树访问根再递归右子树”后序是“先递归左子树再递归右子树最后访问根”。递归之所以能实现这种复杂的访问顺序是因为系统帮我们维护了一个函数调用栈。迭代器要干的事就是自己维护这个栈。写一个二叉树中序遍历的迭代器class InOrderIterator: def __init__(self, root): self._stack [] self._push_left(root) def _push_left(self, node): while node is not None: self._stack.append(node) node node.left def __iter__(self): return self def __next__(self): if not self._stack: raise StopIteration node self._stack.pop() self._push_left(node.right) return node.data这段代码需要好好解释一下。中序迭代器的核心思想是先把根节点的所有左子树依次压栈这样栈顶就是整棵树“最左侧”的节点它就是中序要访问的第一个节点。每次访问完栈顶节点后把它的右子节点的所有左子树再压栈这样就保持了中序“左-根-右”的顺序。用 _push_left 这个名字是有讲究的它封装了一个循环逻辑也是这个迭代器的核心。如果你把这段逻辑直接塞进next里代码会很难读而且容易在状态维护上出 bug。封装成私有方法之后迭代器的推进逻辑就变得非常清晰。前序遍历的迭代器相对简单。访问顺序是根、左、右也就是每弹出一个节点立刻访问它然后把右子树和左子树依次压栈注意先压右再压左因为栈是后进先出。class PreOrderIterator: def __init__(self, root): self._stack [root] def __next__(self): if not self._stack: raise StopIteration node self._stack.pop() if node.right is not None: self._stack.append(node.right) if node.left is not None: self._stack.append(node.left) return node.data后序遍历的迭代器实现就绕一点一个常见的技巧是用两个栈或者用一个栈保存“访问标记”。我先说双栈法。第一个栈用来做“根右左”的遍历把访问顺序压到第二个栈里最后从第二个栈弹出来就是“左右根”的后序顺序。思路不复杂但代码量明显增加。还有一个更取巧的方式既然后序是“左右根”那能不能先走访根右左再反转结果这种思路和双栈法本质一样但如果你只是为了输出序列确实可以先把结果收集到列表里再反转。不过作为迭代器双栈法才是正统因为它保持了“懒”的特性——不需要一次性遍历完整棵树才能开始返回第一个结果。3.3 层序遍历迭代器和队列的强强联手层序遍历也叫广度优先遍历跟前面的前中后序都不同它不走“先深入再回溯”的路子而是逐层从左到右扫描。实现的关键是队列不是栈。具体做法先把根节点入队。只要队列不为空就出队一个节点访问它然后把它的左孩子和右孩子依次入队。这样下一轮访问时自然就是下一层的节点了。用翻书来类比前序中序后序像你把一本书从中间某页读进去然后顺着引用关系跳来跳去而层序遍历像逐页通读每翻完一页就把这一页提到的所有页码记到一个待办列表里按顺序一个个去读。手动实现一个层序遍历迭代器from collections import deque class LevelOrderIterator: def __init__(self, root): self._queue deque() if root is not None: self._queue.append(root) def __iter__(self): return self def __next__(self): if not self._queue: raise StopIteration node self._queue.popleft() if node.left is not None: self._queue.append(node.left) if node.right is not None: self._queue.append(node.right) return node.data这里用 deque 而不是 list是因为 list 的 pop(0) 操作是 O(n) 的而 deque 的 popleft() 是 O(1)。在遍历大数据量的树时这个性能差异是实打实的。如果你用 list 写层序遍历数据量一上来就会明显变慢。层序遍历和迭代器模式的适配度很高。迭代器的接口就是 next() / hasNext()而层序遍历的推进逻辑正好是“出队一个节点 入队它的孩子”。这个模式你甚至可以推广到图的广度优先遍历上只要在入队时加一个 visited 集合防止重复访问就行。迭代器封装这个逻辑之后外部调用方完全感觉不到“队列”的存在这就是模式的意义。3.4 遍历中删除元素的经典坑我知道很多人看到“遍历”这个词第一个想到的问题是在遍历的同时删除/修改元素到底怎么处理才安全。这个坑我踩过相信大家也都踩过。先说一个最常见的错误操作Python 里 for 循环遍历 list 的同时删除元素arr [1, 2, 3, 4, 5] for x in arr: if x 3: arr.remove(x)这代码看起来没什么问题但实际上是 bug。因为 for 循环的迭代器内部维护了一个下标remove 之后后面的元素会往前移一位导致迭代器跳过了一个本该被访问的元素。结果就是改完之后数组内容变了但遍历过程可能漏元素甚至逻辑混乱。更典型的场景是在循环里删除多个元素。比如你想把 [1, 2, 3, 4, 5] 里所有偶数都删掉如果直接在遍历中删你会发现删不干净。原因是删除元素导致索引偏移每次删除后有一个元素被跳过了。解决方案有几个第一倒序遍历。从数组末尾往前遍历删除元素时前面的元素下标不变不会发生偏移问题。Python 里可以用for i in range(len(arr) - 1, -1, -1)。第二建立新列表。用列表推导式或 filter 生成一个新列表而不是在原列表上删。这是最 Pythonic 的做法也是我比较推荐的做法。第三使用迭代器自带的 remove() 方法。Java 的 Iterator 接口自带 remove()它内部保证了删除当前元素不会破坏遍历状态。但注意这个 remove() 必须在 next() 之后紧挨着调用否则会抛 IllegalStateException。坑这个东西踩过一次就有记忆。我的建议是默认用“建新列表”的思路因为它语义清晰、不会出错、性能也不差只有确实需要原地修改内存对象时才考虑迭代器的 remove()。4. 常见问题与排查技巧实录4.1 fail-fast 机制为什么迭代器越遍历越报错Java 的集合类里有一个著名的异常叫 ConcurrentModificationException。我当年第一次遇到时完全懵了我只是在 for-each 循环里删了一个元素怎么就抛异常了这背后的机制叫 fail-fast。简单说ArrayList 内部有一个 modCount 字段每次结构性修改add、remove都会让 modCount 加一。ArrayList 的迭代器里保存了一个 expectedModCount 快照每次调用 next() 都会比较两者是否一致不一致就抛异常。这个设计的初衷是好的防止在遍历过程中集合被修改导致迭代状态不可预测。如果你在遍历的同时删元素迭代器的游标可能会指向错误位置甚至出现元素遗漏或重复访问。fail-fast 就是要把这种不确定性问题提前暴露出来宁可抛异常也不能静默产生错误结果。但这里有个非常容易误伤的场景多线程环境下一个线程遍历、另一个线程删元素即使删的元素跟遍历完全无关迭代器也会检测到 modCount 变化并抛异常。所以 fail-fast 并不能保证多线程并发安全它只是一种“快速失败”的防御机制。真正要并发安全请用 ConcurrentHashMap 或者 CopyOnWriteArrayList。我从实操角度给大家一个排查建议看到 ConcurrentModificationException先检查是不是同一个线程里边遍历边修改如果不是检查是不是多线程共享同一个集合且有人写操作。不要在 for-each 里做任何结构性修改要么用迭代器的 remove()要么收集到一个待删列表里遍历结束后统一删除。4.2 树形结构递归遍历的风险为什么大树会崩用递归做树的遍历代码确实简洁优雅。中序遍历递归写法def inorder_traversal(node): if node is None: return inorder_traversal(node.left) print(node.data) inorder_traversal(node.right)三行代码就把事情说完了。但递归有一个致命的问题函数调用栈的深度是有限制的。Python 默认的递归深度是 1000 层左右Java 的默认栈大小也就几百 KB 到 1MB 不等。当二叉树的深度超过这个限制递归就会栈溢出。在项目实施里树的高度往往深得离谱。比如一个 1000 万条记录的层级分类表你很难保证树的深度只有几十层。所以我一直有一个原则递归写起来爽但上线前要想清楚最坏的树深度。如果树可能很深就用迭代器 显式栈来替代递归。我前面写的 InOrderIterator 就是这样一个替代方案。它把递归时的隐式调用栈换成了显式的 list 当栈内存消耗是可以预估的不会因为递归深度而崩溃。同样的代码逻辑改用迭代器之后一个 for 循环就能完成整棵树的遍历。很多人的误区是觉得迭代器写法绕但实际写过之后你会发现它和递归只是“一个左一个右”的差异。递归的每次函数调用相当于往隐式栈里压入一个状态迭代器的每次 next()相当于从显式栈里弹出一个节点、再压入它的子节点。栈的操作是互相对应的熟了之后根本不绕。4.3 迭代器状态共享的隐蔽问题再分享一个很容易踩的隐蔽坑多个迭代器之间的状态隔离问题。迭代器模式的一个设计要点就是“每次调用 createIterator() 返回一个新的迭代器对象”。如果你误用了同一个迭代器对象就会出现非常诡异的 bug。比如你有两个嵌套循环想遍历同一个 LinkedListfor x in linked_list: for y in linked_list: ...如果 LinkedList 的iter() 每次都返回同一个迭代器实例那么内层循环会消耗外层循环的游标位置。结果就是外层循环只执行了一次内层循环第一次就把所有元素遍历完了。这个问题在 C 里曾经是一个非常经典的误用场景Java 和 Python 由于语言约束很少出现所以迭代器是廉价的、可丢弃的一次性对象。它的生命周期应该很短随用随建用完就扔。数据结构的iter() 或 iterator() 方法每次都要创建全新实例绝不能把迭代器状态存在数据结构内部。4.4 遍历相关错误排查速查表我把遍历中常见的报错和现象整理成一张表方便大家在项目里快速定位。现象原因解决方案for 循环中删除元素后结果不对索引偏移跳过了部分元素倒序遍历、建新列表、使用迭代器 removeJava 抛 ConcurrentModificationException遍历中修改了集合结构使用 CopyOnWriteArrayList、收集待删元素统一删除Python 抛 StopIteration 但 for 循环正常手动调用 next() 越界在循环体中用 try/except 捕获或先检查 hasNext树形结构递归遍历时栈溢出树的深度超过递归极限用迭代器 显式栈替代递归嵌套循环遍历同一个集合但外层提前结束多个迭代器共享了状态确保 createIterator() 每次返回新迭代器对象自定义迭代器 for 循环不执行未实现iter() 或next()检查协议方法签名和返回值排查顺序建议从上往下先确认是不是结构性修改的问题再确认是不是递归深度的问题最后检查迭代器对象是否被共享。大多数遍历相关的疑难杂症都逃不出这几类。5. 从迭代器出发看遍历的全局思路5.1 一个思路打通所有遍历都是“游标 推进规则”写到这儿我想停下来做个贯穿性的总结因为这是我在反复写迭代器过程中最大的体会。你去看链表遍历、二叉树前中后序、层序遍历甚至目录树的遍历、JSON 嵌套对象的递归处理它们本性里都是一回事一个游标表达你当前在哪里一条推进规则告诉你下一步怎么走。链表的游标是当前节点推进规则是 current current.next。二叉树中序的游标是“当前节点 栈里的祖先”推进规则是“如果有右子树就去右子树的最左否则弹栈”。层序的游标是整个队列推进规则是“出队一个、入队它的孩子”。一旦你拥有这种视角写任何遍历代码都变成了一件机械的事先想清楚游标是什么再想清楚推进规则是什么。游标和规则定了代码只是把它们翻译成语言语法而已。这就是为什么我强烈建议每个人都手写一次迭代器——不是为了在项目里用而是为了建立这种“遍历思维”。5.2 什么时候该手写迭代器什么时候别折腾迭代器模式是好东西但也不是所有场景都值得用。我总结了一套自己的取舍标准。如果你的数据结构只是一个普通数组或者哈希表直接用语言内置的 for 循环就够了别脱裤子放屁手写迭代器。当以下情况出现时才考虑自定义迭代器第一遍历逻辑复杂度高。比如二叉树遍历、图遍历、层级结构遍历这类数据结构的遍历规则涉及栈或队列维护写迭代器可以把复杂逻辑从业务代码中隔离出去。第二需要多种遍历方式。同一套数据既要正序又要倒序既要深度又要广度。这时候为每种遍历方式实现一个迭代器类互不干扰可插拔比在数据结构里塞一堆 traversal 方法优雅得多。第三希望统一处理异构数据。不同数据结构相同遍历接口让上层算法通用化。这种情况下迭代器模式几乎是必须的因为只有这样才能把集合和算法彻底解耦。第四数据是懒加载的。比如从数据库游标、网络流、大文件中读取数据用迭代器包装一层可以让调用方以统一方式消费数据而不用担心数据量大小。在项目里我做选择时还有一个很实际的角度团队里其他人能不能快速理解。如果只是自己写个小工具怎么炫怎么来都行但如果是多人协作的公共模块我会倾向用最简单、最显式的写法让后来接手的人看一眼就明白逻辑。迭代器模式的封装很优雅但如果调用方普遍不太熟悉反而可能变成维护负担。5.3 翻书哲学游标式设计与分页思想标题说“像翻书一样遍历数据”这个比喻背后其实还藏着一种很实用的设计思想游标式数据访问。在分页查询、流式处理这些场景下它的意义远大于普通的 for 循环。我举个例子。数据库里有几百万行数据你不可能一次性全查出来加载到内存。正常的做法是分页。但传统分页有个问题按页码跳转时如果期间有新数据插入用户看到的列表顺序可能会打乱。此时更稳的方案是基于游标的分页记录当前页最后一条数据的位置下一页从该位置之后继续取。这种游标分页的思路和迭代器模式里的游标如出一辙。迭代器维护“当前走到哪了”推进时基于当前位置计算下一步而不是从头开始数。区别在于迭代器的游标通常是一个对象引用或数组下标而游标分页的游标可能是一个自增 ID、时间戳或者加密的字符串 token。但底层逻辑是共通的不要把整个遍历过程的状态分散在各处而是封装成一个独立的、可传递的游标对象。再说说文件读取。用 open() 读文件时文件句柄本身就是一个游标readline() 每次读一行并推进游标。Python 的 for line in file 之所以能工作正是因为文件对象实现了迭代器协议它的next() 负责从磁盘读取下一行。这就是迭代器模式融入语言底层的典型例子。所以你会发现迭代器模式并不是一个生硬的设计模式概念它其实是很多系统设计里朴素思想的理论化总结。翻书是遍历分页是遍历读文件也是遍历。人天生就在和“遍历集合”打交道迭代器只是把这个动作规范化、通用化了。6. 核心代码实战整合一个完整示例6.1 从集合到迭代器的完整 Java 示例前面 Python 代码写得比较细这里用一个完整的 Java 示例来展示迭代器模式的经典结构。场景自定义一个可以存储任意数量元素的集合类支持通过迭代器遍历。import java.util.Iterator; import java.util.NoSuchElementException; public class SimpleListT implements IterableT { private Object[] elements; private int size; public SimpleList(int capacity) { elements new Object[capacity]; size 0; } public void add(T item) { if (size elements.length) { // 扩容 Object[] newElements new Object[elements.length * 2]; System.arraycopy(elements, 0, newElements, 0, elements.length); elements newElements; } elements[size] item; } Override public IteratorT iterator() { return new SimpleIterator(); } private class SimpleIterator implements IteratorT { private int cursor 0; Override public boolean hasNext() { return cursor size; } Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } return (T) elements[cursor]; } } }这个示例有几个关键设计。第一SimpleList 实现了 Iterable 也就是说它可以通过 for-each 循环遍历。第二内部类 SimpleIterator 直接访问外部类的 elements 数组和 size 字段Java 的内部类机制让迭代器可以很方便地访问聚合对象的内部状态。第三next() 中先判断 hasNext()没有元素时抛 NoSuchElementException这是 Java Iterator 接口的标准约定。使用的时候SimpleListString list new SimpleList(4); list.add(Java); list.add(Python); list.add(Go); for (String lang : list) { System.out.println(lang); }for-each 循环在编译时会转换成迭代器调用。这行代码背后发生的事情是编译器生成for (IteratorString it list.iterator(); it.hasNext(); )的等价代码。这个转换看起来很小但意义重大——它让所有实现 Iterable 接口的类都自动获得了 for-each 的能力。库的提供者只需要实现一个迭代器所有使用者立刻获得统一的遍历语法。6.2 把迭代器思想扩展到更复杂的聚合结构前面的 SimpleList 是数组结构的迭代器实现相对简单。实际上迭代器模式的精华在复杂结构上才能体现得最充分。比如一个自定义的树节点想要支持多种遍历方式先定义树节点再分别实现前序迭代器、中序迭代器和层序迭代器。Node 类class TreeNode: def __init__(self, data): self.data data self.left None self.right None给 TreeNode 加一个方法返回不同策略的迭代器def iter_preorder(self): return PreOrderIterator(self) def iter_inorder(self): return InOrderIterator(self) def iter_levelorder(self): return LevelOrderIterator(self)调用方可以这样使用root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3) root.left.left TreeNode(4) root.left.right TreeNode(5) print(前序:, [n.data for n in list(root.iter_preorder())]) print(中序:, [n.data for n in list(root.iter_inorder())]) print(层序:, [n.data for n in list(root.iter_levelorder())])注意这里的每个 iter_xxx 方法都返回一个新的迭代器实例并且遍历逻辑封装在各个迭代器类里TreeNode 本身完全不需要知道自己该怎么被遍历。这正是迭代器模式的核心遍历的不是数据结构内部的事而是一个外部策略。这种设计在实际项目中的价值我用一个真实经历来说明。之前做一个规则引擎规则是用树形结构组织的。因为业务需要有时要深度优先执行规则有时要广度优先执行。最开始我把遍历逻辑写死在树的执行方法里结果每次需求变更都心惊胆战。后来把遍历逻辑抽成迭代器树结构只负责存节点三种遍历方式分别写成独立的迭代器类。之后接新需求只要由调用方指定用哪种迭代器树结构一行都不用改。这就是经验中的教训。6.3 迭代器的“幂等”与“安全”边界再补充一个容易被忽略的工程细节。有些迭代器是“一次性”的——遍历完就没用了有些迭代器可以支持 reset。这取决于你如何设计游标的初始化。一次性迭代器的游标在构造函数里初始化每次 next() 推进后不可回退。重置迭代器就是在迭代器类里加一个reset()方法把游标重置回初始位置。Java 的 Iterator 接口没有 reset 方法但你自己实现时完全可以加。我遇到一个场景需要对同一份数据反复遍历多次每次都从头开始。当时没有场景重建迭代器而是直接在迭代器上做了 reset少写了不少代码。不过迭代器还有一个安全边界需要强调迭代器创建之后如果聚合数据结构被大量修改增删元素迭代器的游标和数据结构的新状态之间就可能不一致。即使是不抛异常的迭代器比如 Python 的 list 迭代器也可能出现漏元素或重复访问。所以一个经验准则是迭代器一旦创建尽量在遍历期间不要修改数据结构的结构。如果确实需要同时修改和遍历务必先评估清楚你依赖的是哪种迭代器行为。7. 我在实际项目里对迭代器模式的一些体会写了这么多最后分享一点我个人的实际体会吧。迭代器这个模式看起来简单但真正理解它需要从“遍历”这个行为抽象到“游标”这个哲学概念。几年前我也是那个只会在 for 循环里写 i 的人直到自己手写了链表、二叉树、层序迭代器之后才开始真正理解什么叫“数据的读取与数据的存储分离”。如果你刚接触迭代器模式我的建议是不要只看文章一定要自己动手写一遍。先写一个链表的迭代器再写一个二叉树中序的迭代器最后写一个层序的迭代器。这三种结构的迭代器难度递增写完之后你会发现你对遍历的理解会上一个台阶。尤其是当你发现自己写的树迭代器能直接套进 for 循环里用的时候那种“原来设计模式是这样改善代码的”的感觉是看多少文章都换不来的。还有一个小技巧在复杂的数据结构设计阶段顺手就把迭代器规划进去。很多设计模式的问题出在使用阶段不如出现在设计阶段。如果你的数据结构定位是会被外部模块反复遍历的那么从一开始就给它设计好迭代器接口比后续再重构要省太多力气。我之前那个规则引擎的教训就是最好的例子。最后再聊一个实践细节。迭代器的命名和文档也很重要尤其是当一个数据结构支持多种遍历方式时。如果你不明确告诉使用者“这是按深度优先顺序的”“这是按层级顺序的”别人极有可能拿错迭代器输出看起来完全正确、实际语义不对的数据。所以我在写这类代码时不仅类名会精确到 PreOrder / InOrder / LevelOrder还会在文档注释里写清楚每种迭代器的遍历规则和典型用途。这是很多人忽略的地方但对团队协作的价值极大。像翻书一样遍历数据书签往前一移下一页就来了。这种简单而稳的抽象真的值得每个程序员把它吃透。
