8

我有一个大学作业，要求我实现一个实现迭代器接口的内部类。迭代器适用于单链表超类。

目前我的内部类是这样的：

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。其他一切似乎都有效。我可能在某个地方忽略了一个逻辑缺陷，但我自己找不到。

4

4 回答 4

5

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

用你的hasNext()方法做这一切。请记住，如果 next() 为hasNext()false，则可以抛出异常 - 因此您需要确保这是它唯一会抛出异常的时间。

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

于 2013-03-12T15:24:55.130 回答
5

更改了您的实现以反映迭代器合约的需求。您需要记住，您需要能够遍历集合的所有元素，即，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;
    }

}
于 2013-03-12T15:45:23.660 回答
2

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

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

根据您的代码，似乎

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

可以解决问题（如果header.getNext()==null是空列表）。

于 2013-03-12T15:25:57.270 回答
2

减少一些代码，使其更具可读性

  • 重命名temp为next,
  • 使用快捷符号，
  • 可能应该有一些current节点的概念，

这使得更新看起来像：

private Node next;
private Node current;    //track deletion

@Override
public boolean hasNext() {
    return next != null;
}

public Node getNext() {
  if (hasNext()) {
    current = next;
    next = next.getNextNode();
  }
  return current;
}

删除可以将 current 设置为 null。我们不需要标志（假设如果有人在调用 first 之前删除，我们可以什么都不做getNext()。哎呀，如果我们真的想争取金牌，请remove()抛出IllegalStateExceptionif current == null。

于 2013-03-12T15:59:43.640 回答