介绍

提供一种方法访问一个容器对象中各个元素，而不需暴露该对象的内部细节

迭代器模式有两个角色，一个是容器，一个是迭代器
由迭代器实现容器的遍历方法，容器通过调用迭代器的封装好的方法进行遍历
迭代其中通常有以下方法：

  • boolean hashNext()：判断是否已经到达容器的边界。迭代器用游标来记录遍历节点数，通过与容器中的元素数量比较来避免越界
  • E next()：获取下一个元素值。

或者是

  • boolean hashNext()
  • void next()
  • E currentItem

这两种方式有什么区别？以链表举例好了，如果是单项链表，适合第二种方式，如果使用方式一，在实现安全删除时，会漏掉第一个元素；如果是双向链表则都可以，java 中的 LinkedList 使用的是方式一

使用场景

减少遍历复杂数据结构的难度

模板

类图

迭代器模式 - 图1

JDK中的迭代器问题

image.png
如果遍历的时候，容器删除了元素，会有以下几种情况

  • 删除的是当前游标之后的元素，无影响
  • 删除的是当前游标之前的元素，容器中元素的位置就会向前挪

自实现容器使用foreach循环

思路

JDK 有个 foreach 语法糖
image.png
它实际上是在编译阶段转为了这个样子
image.png
如何使用这个语法糖呢？只需要实现这个接口就可以了
image.png
但是这里只是实现语法糖，如果要完全实现上面的效果，还需实现 Iterator 接口，实现 next 与 hasNext 方法

实现

这里的代码是我这篇链表与哨兵中的无哨兵链表实现。实现功能

  • 增加
  • 删除
  • 查找
  • foreach 循环
  • 安全删除

抽象类

  1. package cn.zjm404.stu.algorithm.list;
  3. import java.util.Iterator;
  5. /**
  6.  * @author ZJM
  7.  */
  8. public abstract class MyLinkedList<T> implements Iterable<T> {
  10.     protected Node<T> head;
  11.     protected Node<T> tail;
  13.     @Override
  14.     public Iterator<T> iterator() {
  16.         return new MyLinkedIterator();
  17.     }
  20.     static class Node<T> {
  21.         T value;
  22.         Node<T> next;
  23.         Node<T> prev;
  25.         public Node(T t) {
  26.             value = t;
  27.         }
  28.     }
  30.     private class MyLinkedIterator implements Iterator<T> {
  33.         private Node<T> curNode;
  35.         private Node<T> lastReturn;
  37.         public MyLinkedIterator() {
  38.             curNode = head;
  39.         }
  41.         @Override
  42.         public boolean hasNext() {
  43.             return curNode != null;
  44.         }
  46.         @Override
  47.         public T next() {
  48.             lastReturn = curNode;
  49.             curNode = curNode.next;
  50.             return lastReturn.value;
  51.         }
  53.         public T currentItem(){
  54.             return curNode.value;
  55.         }
  57.         @Override
  58.         public void remove() {
  59.             if(lastReturn == null){
  60.                 throw new IllegalStateException();
  61.             }
  62.             //孤立被删除节点
  63.             Node<T> del = lastReturn;
  64.             Node<T> delPrev = lastReturn.prev;
  66.             //如果删除的节点为首节点
  67.             if(delPrev == null){
  68.                 head = curNode;
  69.                 curNode.prev = null;
  71.             }else{
  72.                 delPrev.next = del.next;
  73.                 del.next.prev = delPrev;
  74.             }
  75.             del.next = null;
  76.             del.prev = null;
  77.             lastReturn = null;
  78.         }
  79.     }
  81.     public abstract void add(T t);
  83.     public abstract void addFirst(T t);
  85.     public abstract boolean removeFirst();
  87.     public abstract boolean remove(T target);
  89.     public abstract boolean contain(T target);
  90. }

无哨兵链表

  1. package cn.zjm404.stu.algorithm.list;
  4. public class NoSentryLinkedList<T> extends MyLinkedList<T>{
  6.     @Override
  7.     public void add(T t){
  8.         if(head == null){
  9.             tail = head = new Node<T>(t);
  10.             return;
  11.         }
  12.         Node<T> newNode = new Node<T>(t);
  13.         //建立联系
  14.         newNode.prev = tail;
  15.         tail.next = newNode;
  16.         //挪动尾结点
  17.         tail = newNode;
  19.     }
  20.     @Override
  21.     public void addFirst(T t){
  22.         if(head == null){
  23.             tail = head = new Node<T>(t);
  24.             return;
  25.         }
  26.         Node n = new Node(t);
  27.         n.next = head;
  28.         head.prev = n;
  29.         head = n;
  30.     }
  31.     @Override
  32.     public boolean removeFirst(){
  33.         if(head == null){
  34.             throw new NullPointerException("空链表异常！");
  35.         }
  36.         //如果链表中只有一个节点
  37.         if(head == tail){
  38.             head = tail = null;
  39.             return true;
  40.         }
  41.         Node<T> del = head;
  42.         //孤立节点
  43.         if(del.next != null){
  44.             del.next.prev = null;
  45.         }
  46.         head = del.next;
  47.         //删除节点
  48.         del.prev = null;
  49.         del.next = null;
  51.         return true;
  53.     }
  54.     @Override
  55.     public boolean remove(T target){
  56.         //如果为空链表，则直接返回
  57.         if(head == null){
  58.             return false;
  59.         }
  60.         //如果删除节点为头节点
  61.         if(head.value.equals(target)){
  62.             return removeFirst();
  63.         }
  64.         //遍历链表，找到后继节点为target的节点
  65.         for(Node<T> n = head;n.next != null;n = n.next){
  66.             if(n.next.value.equals(target)){
  68.                 //删除目标节点
  69.                 Node<T> del = n.next;
  70.                 //孤立节点
  71.                 n.next = del.next;
  72.                 if(del.next != null){
  73.                     del.next.prev = n;
  74.                 }
  75.                 //删除节点
  76.                 del.next = null;
  77.                 del.prev = null;
  79.                 //如果删除的节点为尾节点
  80.                 if(tail == del){
  81.                     tail = n.next;
  82.                 }
  83.                 return true;
  84.             }
  85.         }
  87.         return false;
  88.     }
  89.     @Override
  90.     public boolean contain(T target){
  91.         for (Node<T> n = head; n != null; n = n.next){
  92.             if(n.value.equals(target)){
  93.                 return true;
  94.             }
  95.         }
  96.         return false;
  97.     }
  98. }

测试

  1. package cn.zjm404.stu.algorithm.list;
  3. public class Client {
  4.     public static void main(String[] args) {
  5.         NoSentryLinkedList<String> nl = new NoSentryLinkedList<>();
  6.         System.out.println("-------插入节点 测试---------------------");
  7.         nl.add("hello");
  8.         nl.add("world");
  9.         nl.addFirst("WORLD");
  10.         nl.addFirst("HELLO");
  12.         for (String s : nl) {
  13.             System.out.println(s);
  14.         }
  15.         System.out.println("-------删除 首节点 测试---------------------");
  16.         nl.removeFirst();
  17.         for (String s : nl) {
  18.             System.out.println(s);
  19.         }
  21.         System.out.println("-------遍历删除 WORLD 测试---------------------");
  22.         Iterator<String> iterator = nl.iterator();
  23.         while(iterator.hasNext()){
  24.             String cur = iterator.next();
  25.             if(cur.equals("WORLD")){
  26.                 iterator.remove();
  27.                 continue;
  28.             }
  29.             System.out.println(cur);
  30.         }
  31.         System.out.println("-------当前状态---------------------");
  32.         for (String s : nl) {
  33.             System.out.println(s);
  34.         }
  36.         System.out.println("-------删除 world 测试---------------------");
  37.         nl.remove("world");
  38.         for (String s : nl) {
  39.             System.out.println(s);
  40.         }
  41.         System.out.println("-------删除 最后一个节点 hello 测试---------------------");
  42.         System.out.println("删除 hello 是否成功:"+nl.remove("hello"));
  43.         System.out.println("查找 hello 是否存在:"+nl.contain("hello"));
  45.     }
  46. }