Iterator接口

Question

我有一个大学分配，它要求我实现一个实现Iterator接口的内部类。迭代器在单个链表超类上工作。

目前我的内部类看起来像这样：

private class ListIterator implements Iterator<V>{

    Node temp;
    boolean nextCalled = false;

    ListIterator(Node fo){
        this.temp = fo;
    }

    @Override
    public boolean hasNext() {
        if(temp != null){
            return true;
        }
        return false;
    }

    @Override
    public V next() {
        nextCalled = true;
        return temp.getReprValue();
    }

    @Override
    public void remove() {
        if(nextCalled && hasNext()){
            nextCalled = false;
            removeElement(temp.getReprKey());
            temp = temp.getNext();
        }

    }

}

现在我的问题是，即使列表实际上是空的，hasNext()方法也会返回true。其他一切似乎都很好用。我可能忽略了某个地方的逻辑缺陷，但我自己找不到它。

Answer 1

更改您的实现以反映Iterator协定所需的内容。您需要记住，您需要能够迭代集合的所有元素，即next()应该从第一个元素开始，并且在每次调用之后，它必须将当前的下一个元素更改为列表中的下一个元素，或者如果没有元素，则抛出异常。

阅读Iterator interface doc以理解您需要实现它的方式并从那里开始是很好的。

private class ListIterator implements Iterator<V> {
    private Node next;
    private boolean alreadyDeleted = false;

    ListIterator(Node node){
        this.next = node;
    }

    @Override
    public boolean hasNext() {
        // because next is the current element. We need to iterate over all the elements
        // from the collection.
        return next != null;
    }

    @Override
    public V next() {
        if (next == null) {
           throw new NoSuchElementException();
        }

        Node current = next;

        this.next = current.getNext();
        this.alreadyDeleted = false; // it's better to try to elimate this state variable. You can try to do in another way, if yours removeElement returns something

        return current;
    }

    @Override
    public void remove() {
        if (alreadyDeleted || next == null) {
           throw new IllegalStateException();
        }
        removeElement(next.getReprKey());
        this.alreadyRemoved = true;
    }

}

Answer 2

您需要跟踪您在列表中的位置，实现一个cursor，或者如果您的链表中的节点知道它们的next，只需询问它们是否有下一个元素。当光标大于长度/您的节点没有next时，您将在hasNext()中返回false。

在您的hasNext()方法中完成所有这些操作。请记住，如果hasNext()为false，那么让next()抛出异常是可以的-所以您需要确保这是它抛出异常的唯一时间。

因为我不知道你的列表的底层数据结构，所以我不能告诉你哪一个更好。

Answer 3

如果当前节点(temp)不是null，则hasNext返回true。

如果您的链表实现使用header节点，则构造函数将始终接收fo!=null，并且即使列表为空，hasNext也将返回true。你应该在你的实现中考虑到这个事实。

根据您的代码，看起来

ListIterator(Node fo){
    this.temp = fo.getNext();
}

可以做到这一点(如果空列表为header.getNext()==null )。