Java实现具有迭代器的线性表(顺序表) - linux编程基础

1，先了解下JAVA类库中的迭代器：JAVA提供了两种基本类型的迭代器，分别用两个接口来表示：Iterator，ListIterator。其中，Iterator接口中只定义了三个方法：hasNext()、iterator()、next()，而ListIterator中，除了拥有前面所述的三种方法外，而另外拥有hasPrevious()、previous()、remove()、set()等其他方法（具体参考JDK文档）。

这说明：实现了Iterator接口的迭代器只能往一个方向遍历(正向)，而实现了ListIterator接口的迭代器即可以正向遍历又可以反向遍历（由hasPrevious()、previous()实现反向遍历），同时，它还可以对遍历的元素进行修改（由set()方法实现）、删除当前遍历的元素（由remove()实现）。

2，当前，在写程序时，最好能够使用JAVA类库中已经为我们定义好的迭代器，它为JAVA的集合类都定义了返回上述两种迭代器的方法。

如：ArrayList类的 iterator() 方法返回一个Iterator类型的只能对单一方向进行迭代的迭代器，而listIterator()方法返回一个ListIterator类型的迭代器，它不仅能双向迭代，而且修改、删除迭代的元素。

3，下面实例代码实现了一种ADT之顺序表（实质为数组），并且该数组拥有遍历器。该遍历器能对当前遍历的数组进行修改和删除。个人感觉要想同时保证迭代器具有修改和删除的功能，同时又要保证ADT基本操作的正确，对数组下标的合适定义真的很难。

4，首先定义了一个接口ListWithListIteratorInterface，该接口只有一个方法getIterator()，该方法负责生成一个迭代器并返回给调用者。然后，再让实现了数组的类SequenceListWithIterator implements ListWithListIteratorInterface.

为什么要这样做呢？为什么不用SequenceListWithIterator直接 implements ListIterator ?

因为，如果用SequenceListWithIterator直接 implements ListIterator，那么SequenceListWithIterator类的对象不仅是一个迭代器（因为它implements ListIterator）而且是一个顺序表（因为它实现了线性表中的各种基本操作，相当于implments ListInterface了）。这意味着，在我们的代码中，当创建了一个SequenceListWithIterator对象时，该对象不能在同一时刻对线性表进行多次迭代，因为它本身就是迭代器，只能对"自身"元素进行迭代了。

而采用SequenceListWithIterator implements ListWithListIteratorInterface，这样SequenceListWithIterator对象只是线性表，它不是迭代器。但是，由于它实现了ListWithListIteratorInterface，它(顺序表对象)就可以调用getIterator()方法获得一个迭代对象，让该迭代器对象对自己进行遍历，当然了，它就可以多次调用getIterator()方法获得多个迭代器对象，从而可以让多个迭代器同时对自己进行遍历。

接口ListWithListIteratorInterface具体代码如下：

import java.util.ListIterator;

public interface ListWithListIteratorInterface {
? ? public ListIterator getIterator();
}

实现了线性表的基本操作（说明它是一个顺序表）及拥有一个实现了ListIterator接口内部类（说明它拥有一个迭代器）的具体代码如下：

import java.util.Arrays;
import java.util.ListIterator;
import java.util.NoSuchElementException;

public class SequenceListWithIterator implements
? ? ? ? ListWithListIteratorInterface {
? ? private final int DEFAULT_SIZE = 16;// final实例变量显示指定初始值，且不再变化。

? ? private Object[] elementData;// 该数组用来保存顺序表中的元素
? ? private int capacity;// 保存数组的长度
? ? private int size;// 保存顺序表中当前元素的个数

? ? private enum Move {
? ? ? ? NEXT, PREVIOUS
? ? };

? ? private class IteratorForSequenceList implements ListIterator {
? ? ? ? private int nextIndex;// 标记迭代器指针的位置
? ? ? ? private boolean isRemoveOrSetLegal;// 标记 remove() 或 set() 操作是否合法
? ? ? ? private Move lastMove;// 当进行了一次移动操作后，lastMove指示这是前移而是后移

? ? ? ? private IteratorForSequenceList() {
? ? ? ? ? ? nextIndex = 0;
? ? ? ? ? ? isRemoveOrSetLegal = false;//初始值为false，当调用了next()或previous()时被设置为true
? ? ? ? ? ? lastMove = null;
? ? ? ? }

? ? ? ? public boolean hasNext() {
? ? ? ? ? ? return nextIndex < size - 1;
? ? ? ? }

? ? ? ? public T next() {
? ? ? ? ? ? if (hasNext()) {
? ? ? ? ? ? ? ? lastMove = Move.NEXT;// 进行的是后移操作
? ? ? ? ? ? ? ? isRemoveOrSetLegal = true;// 当next()调用了之后，才可以调用remove()或set()
? ? ? ? ? ? ? ? return (T) elementData[nextIndex++];// 注意nextIndex的自增顺序
? ? ? ? ? ? } else
? ? ? ? ? ? ? ? throw new NoSuchElementException("Illegal call to next(),"
? ? ? ? ? ? ? ? ? ? ? ? + "迭代器位于表的最后端");
? ? ? ? }

? ? ? ? public boolean hasPrevious() {
? ? ? ? ? ? return (nextIndex > 0) && (nextIndex <= size);
? ? ? ? }

? ? ? ? public T previous() {
? ? ? ? ? ? if (hasPrevious()) {
? ? ? ? ? ? ? ? lastMove = Move.PREVIOUS;// 进行的是前移操作
? ? ? ? ? ? ? ? isRemoveOrSetLegal = true;
? ? ? ? ? ? ? ? return (T) elementData[--nextIndex];// 注意nextIndex的自减顺序
? ? ? ? ? ? } else
? ? ? ? ? ? ? ? t

Java实现具有迭代器的线性表(顺序表)(一)