java - 降序ListNode迭代器实现

Question

我在此方法中的目标是编写一个迭代器的实现，该迭代器按降序迭代 listNode 的元素。 (从后到前)我附上了升序迭代器的实现。任何正确方向的帮助将不胜感激。

 public MyDescendingDequeIterator(ListNode<E> back, ListNode<E> front) {                    
  frontOfList = front;
  nextToReturn = back;
   while (nextToReturn.next != null) {
    nextToReturn = nextToReturn.next;
}          
}


public boolean hasNext() {
 if (nextToReturn == null){
 return false;
 } else {
 ListNode<E> current = frontOfList;
 return true;
 }
}

public E next() {
ListNode<E> current = frontOfList;
while ( current.next != nextToReturn ) {
  current = current.next;
}
nextToReturn = current;

return nextToReturn.data;

}
public void remove() {
    throw new UnsupportedOperationException();
}

}

Answer 1

如果它是一个只有 next() 方法的常规 ListNode 实现，您需要实现 prev() 方法 - 在这种情况下的 hasNext 与您已经实现的非常相似。

另一种方法是保留列表的开头并每次迭代，直到下一个元素成为 nextToReturn(然后更新 nextToReturn)。这是不太理想的方法，因为您需要从长度为 m 的列表的结尾到开头迭代 O(m^2)；

更新:

好吧，首先你不需要元素的数量，因为它与迭代器的想法完全相反。

假设我们有

public MyDescendingDequeIterator(ListNode<E> back, ListNode<E> front) {                    
  frontOfList = front;
  nextToReturn = frontOfList;
  current = frontOfList;
}

下一步就是设置 nextToReturn = back (现在您根本不使用 back)。而且您实际上并不需要两个变量，因为 nextToReturn 是当前迭代器。

所以它转变为:

public MyDescendingDequeIterator(ListNode<E> back, ListNode<E> front) {                    
      frontOfList = front;
      nextToReturn = back;
    }

现在让我们看看 next() 方法

正如我所说，这里不需要索引 for，因为 frontOfList 具有 next 属性。

所以可能是:

public E next() {
    ListNode<E> current = frontOfList;
    while ( current.next != nextToReturn ) {
      current = current.next;
    }
    nextToReturn = current;

    return nextToReturn.data;

}

hasNext 实现从这里开始应该很简单。请注意，根据良好的编码标准，以 is 或 has 开头的方法很少会更改对象的状态。

请注意，我还省略了此处可能的空检查和其他可能的特定检查，这只是方向的示例。

更新2:

据我现在的想法，构造函数中也不需要第二个参数，只需这样:

public MyDescendingDequeIterator(ListNode<E> front) {                    
    frontOfList = front;      
    nextToReturn = front;

    // calculate back here instead of get it as param
    while ( nextToReturn.next != null) {
        nextToReturn = nextToReturn.next;
    }          
}

更新3:

看，仅仅开始编写一些代码并期望它能够工作是没有帮助的，你应该先坐下来，开始在纸上用箭头画出方框，然后尝试理解每个函数应该做什么。

正如我之前所说，您的 hasNext() 方法有一个错误，并且总体上是不正确的。为什么要检查null？你从后向前移动，前面的某个地方有空吗？您需要 current 对象做什么。它有什么作用？

next() 方法还应该检查您是否已经位于第一个元素。否则，它将(并且确实)在最后一个元素处导致 NullPointerException。

首先尝试调试，或者至少添加一些打印输出，这有助于了解错误所在。但首先您应该构建算法，然后才开始编码，而不是相反。