没有迭代器的线性表, 还能够叫线性表吗. 在现代的类库里, 类似线性表这样存放数据的集合, 如果不配上一个迭代器, 那几乎就没有人用了. 原因很简单, 不好用. 使用数据结构的人要花费额外的经历去按照顺序使用其中的元素.
迭代器就提供了这样一个便利的模式. 其实迭代器在之前看设计模式的时候已经学过了.
现在就给我们的线性表配上迭代器, 让它成为一个成熟的迭代器…
迭代器接口与可迭代接口
我们编写的迭代器实际上可以自行实现一个接口, 不过既然是在Java语言中使用, 为了能够与语言保持一致, 还是要看看Java的迭代器接口:
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while(this.hasNext()) {
action.accept(this.next());
}
}
}
这个接口有三个方法, 有一个方法默认是要抛异常, 实际上是是否允许你删除调用next之后最后返回的项, 一般都不允许通过迭代器进行删除, 实际就关注hasNext()和next()即可. 还有一个应用Consumer函数式接口的方法. 也就是对剩下的东西进行什么处理. 看来不错.一会也可以尝试一下.
我们的泛型是T的情况下, 就需要给我们的线性表添加一个功能, 让其返回一个Iterator接口类型的对象. 不过这个功能叫什么不用自己想,回想一下迭代器套路, 我们的线性表既然是可以可迭代对象, 就可以去实现java提供的Iterable接口就行了, 这个接口如下:
public interface Iterable<T> {
Iterator<T> iterator();
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
Iterator var2 = this.iterator();
while(var2.hasNext()) {
T t = var2.next();
action.accept(t);
}
}
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(this.iterator(), 0);
}
}
这里就一个核心方法, 也就是标红的方法. 另外还有一个也是对每个元素应用Consumer函数的方法, 还有一个拆分的. 现在只关注前两个.
这里很多人可能会发蒙, 怎么两个接口名字差不多,一个返回另一个. 实际上从名字就能看出来.Iterable表示你这个东西是可以迭代的. 要加在自行编写的类上. 实际的迭代工作, 则是由迭代器Iterator完成的. 接下来就改造一下两个线性表, 为其加上这个功能.
改造数组实现的线性表
改造的第一步不用说了, 肯定是先给其套上一个接口:
public class MyArrayList<T> implements ListInterface<T>, Iterable<T> {
然后其中只有一个方法要实现. 在实现这个方法的时候, 就要考虑了, 返回Iterator对象, 要如何编写呢.
思考我们的迭代器, 每个迭代器应该彼此独立, 比如针对一个数组创建了一个A迭代器, 用了5个数据, 创建了一个B迭代器,用了10个数据, 很显然, 两个迭代器彼此独立, 不能互相影响, 否则会出乱子.
所以我们需要来编写一个迭代器类, 每个迭代器都彼此独立来记住自己迭代到了哪个元素.
根据我们的需要, 迭代器只会被接口返回, 不能让外部程序直接创建, 所以我们依然把迭代器的实现写成内部类即可. 所以下一步就是先编写迭代器Iterator对象, 先搭起一个框架:
@Override
public Iterator<T> iterator() {
return new ArrayListIterator<>();
}
private class ArrayListIterator<T> implements Iterator<T> {
private int number;
private int index = 0;
private ArrayListIterator() {
this.number = numberOfEntries;
}
@Override
public boolean hasNext() {
return false;
}
@Override
public T next() {
return null;
}
}
这里在每次创建内部类对象的时候, 都会使用当前的外部类的元素数量作为一个计数. 由于我们内部是数组实现, 只需从0开始, 一直到索引位置为n-1的对象即可, 所以保存一个当前的位置和总共元素数量就可以了.
之后每一个next()方法, 返回索引上的元素, 然后增加index. 而hasNext()只需要判断当前索引与number-1的关系即可:
@Override
public boolean hasNext() {
return index <= number - 1;
}
@Override
@SuppressWarnings("unchecked")
public T next() {
T result = (T)list[index];
index++;
return result;
}
使用迭代器的标准操作, 就是获取迭代对象然后通过判断进行操作:
Iterator<String> iterator = list.iterator();
int count = 1;
while (iterator.hasNext() && count < 10) {
System.out.println(iterator.next() + " | " + count);
count++;
}
因为我们实现了Java提供的标准接口, 那么可以使用增强for循环, 这个语句内部就是上边的显式使用迭代器的原理:
for (String s : list ) {
System.out.println(s);
}
这里还可以来试验一下迭代器的另外一个方法, 就是对迭代器中每一个元素应用Consumer函数式对象, 这里我们想把线性表中每个字符串都拼接起来:
Iterator<String> iterator = list.iterator(); StringBuilder stringBuilder = new StringBuilder(); iterator.forEachRemaining(stringBuilder::append); System.out.println(stringBuilder.toString());
改造链表实现的线性表
改造链表实现的线性表, 我们要注意的是, 如果像数组那样仅仅保存总元素数量和当前索引, 那会导致迭代器的性能大幅下降, 因为每次都需要从头遍历节点, 导致迭代器性能大幅下降, 原来的线性表是O(n), 如果每一次next()也是O(n), 那合起来就是平方级别的复杂度,非常恐怖.
因此相比数组, 我们要保存的是当前指向的节点. 如果我们的线性表的逻辑没有错误的话, 甚至都不需要记录总元素数量. 因为线性表的结尾节点一定是null, 只要当前节点引用是null, 就说明再也没有下一个元素了.
当然你这里也可以引入冗余数据, 比如同时再记录当前索引和元素数量, 每次迭代一边往前移动节点引用, 一边比较索引和元素数量. 但确实有点冗余.
改造后的链表实现的线性表如下:
public class MyLinkedList<T> implements ListInterface<T>, Iterable<T> {
@Override
public Iterator<T> iterator() {
return new LinkedListIterator<>();
}
private class LinkedListIterator<T> implements Iterator<T> {
private Node currentNode;
private LinkedListIterator() {
this.currentNode = firstNode;
}
@Override
public boolean hasNext() {
return currentNode != null;
}
@Override
@SuppressWarnings("unchecked")
public T next() {
T result = (T) currentNode.data;
currentNode = currentNode.next;
return result;
}
}
......
}
ListIterator
由于最终我们还是会选择java提供的类库的成熟的线性表. 这些线性表都实现了Iterable接口, 可以放心使用.
这里还需要了解一下java.util包中的另外一个接口, 就是ListIterator, 老样子看看定义:
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove();
void set(E var1);
void add(E var1);
}
可以看到这个接口扩展了标准的迭代器Iterator<E>接口, 最开始的两个方法是Iterator<E>接口中的原版方法. 此外还加上了一堆东西.
从名字就可以看出, 除了一套hasNext()+next(), 这接口还有一套hasPrevious()+previous(), 很显然可以双向遍历, 是一个可以在线性表里前后走来走去的迭代器.
通过ListIterator官方文档可以看到,最后的remove和set方法, 是可以删除或者替换刚刚由next() or previous()返回的对象. add则可以向线性表中添加一个对象.
不过官方文档中没有提到这个接口的实现类. 实际上, List接口中定义了两个方法:
ListIterator<E> listIterator(); ListIterator<E> listIterator(int var1);
所以List的实现类都实现了这两个方法, 点开ArrayList的源码就可以看到, 其定义了一个内部类:
private class ListItr extends ArrayList<E>.Itr implements ListIterator<E> {
这个迭代器的实现也不复杂, 其本质还是记录当前的索引位置. 数组前后移动索引非常方便, 要删除, 修改和添加新元素, 都可以调用外部类的方法.
java的LinkedList中也是一样:
private class ListItr implements ListIterator<E> {
其中保存了两个指向上一个和下一个的节点. 所以本质上也很容易编写. 这里只需要了解, 除了标准的迭代器之外, 在使用ArrayList和LinkedList的时候, 还有更灵活的选择.
