迭代器接口

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

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

如果您的链表实现使用头节点，那么构造函数总是收到fo=null和hasNext将返回true，即使列表为空。您应该在实现中考虑这一事实。

根据你的代码，似乎

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

可能会成功（如果header.getNext（）==null为空列表）。

Answer 2

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

在您的hasNext（）方法中执行所有这些操作。请记住，如果hasNext（）为false，则让next（）引发异常是可以的，因此您需要确保这是它引发异常的唯一时间。

由于我不知道列表的底层数据结构，我无法告诉您哪一个更好。

Answer 3

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

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

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;
    }

}