循环单链表迭代器的问题_java

我试图为我的循环单链表创建一个迭代器，但我不承诺如何实现next（）和hasNext（）方法。 我怀疑我需要1）在链表类或迭代器类中有其他字段，或2）引用其他东西而不是'head'和'tail'？ 我的代码如下：

public class CircularSinglyLinkedList2<E> implements Iterable<E> {

private Node head;
private Node tail;

public CircularSinglyLinkedList2() {
    head = null;
    tail = null;
}

class Node {
    E data;
    Node next;

    private Node(E data) {
        this.data = data;
    }
}

private boolean isEmpty() {
    return head == null;
}

private int size() {
    int count = 0;
    if(isEmpty()) {
        return 0;
    }
    Node p = head;
    count++;
    p = p.next;
    while(p != head) {
        count++;
        p = p.next;
    }
    return count;
}

public void insert(E data) {
    Node node = new Node(data);
    if(isEmpty()) {
        node.next = node;
        head = node;
        tail = node;
    } else {
        node.next = head;
        head = node;
        tail.next = head;
    }
}

public void delete(E data) {
    if(isEmpty()) {
        return;
    }
    if(head == tail) {
        if(head.data == data) {
            head = null;
            tail = null;
        }
        return;
    }
    Node p = head.next, q = head;
    while(p != head) {
        if(p.data == data) {
            q.next = p.next;
            return;
        }
        q = p;
        p = p.next;
    }
}

public Node search(E data) {
    if(isEmpty()) {
        return null;
    }
    Node p = head;
    if(p.data == data) {
        return p;
    }
    p = p.next;
    while(p != head) {
        if(p.data == data) {
            return p;
        }
        p = p.next;
    }
    return null;
}

public boolean contains(E data) {
    return search(data) != null;
}

public Iterator<E> iterator() {
    return new SLLIterator();
}


private class SLLIterator implements Iterator<E> {

    private Node p;
    private Node q;

    public SLLIterator() {
        if(!isEmpty()) {
            p = head.next;
            q = head;
        }
    }

    @Override
    public boolean hasNext() { doesnt't work
        if(p == q || p == head) {
            return false;
        }
        return true;
    }

    @Override
    public E next() { //doesn't work
        E data = q.data;
        q = p;
        p = p.next;
        return data;
    }

}

你的hasNext()不完全正确。 由于您的p == head条件，您将始终错过打印最后一个元素。 所以检查p将无助于决定hasNext() 。

理想情况下你要检查的是q == head ，这是当你完成所有元素的迭代并返回到起始元素并且你的hasNext()应该返回false ，但如果你只是检查q == head ，那么它不是开始工作，因为你的起始元素本身就会失败。 因此，请使用标记来确定您是回来还是第一次来访。

我建议你这样做：

使用visitingAgain flag。

boolean visitingAgain = false;

在你的hasNext()使用它，如下所示。

@Override
public boolean hasNext() { 
   if (p == q || (q == head && visitingAgain)){
      return false;
   }
   visitingAgain = true; // once you start iterating change this flag.
   return true;
}

注意我没有完全检查你的insert和delete逻辑，如果这不起作用只是确保你的其他功能是正确的。 如果有任何问题，请告诉我。

是的，您的迭代器中存在问题。 它忽略了最后一项（头部）。 例如，假设您的列表中只有一个元素。 所以head和tail指向它，以及head.next 。

现在，如果我们在这样的列表上的新迭代器上请求hasNext() ，我们应该得到一次true ，然后，在我们调用next() ，得到false。

但你的条件是：

   if(p == q || p == head) {
        return false;
    }

这意味着对于单元素列表，无论如何，您都将返回false 。

此外，即使我们假设我们有多个元素，也说：

2->1

然后用p = head.next和q = head初始化迭代器。 你的hasNext()将返回true，但你的next()做什么？

public E next() { //doesn't work
    E data = q.data;
    q = p;
    p = p.next;
    return data;
}

因此，它在开头返回2 ，并移动p和q 。 没关系，打印出2 。 但现在q在点1个p再次在点2 。 再次，你的hasNext()看到p == head并且说没有更多的元素！

因此，当前指向q的元素（实际的下一个元素）将被忽略。

你应该做的是有一种标志告诉你第二次击中头部而不是第一次。 并且实际上不需要两个指针。 这是我的迭代器版本：

private class SLLIterator implements Iterator<E> {

    private Node p;
    private boolean atStart;

    public SLLIterator() {
        if(!isEmpty()) {
            p = head;
            atStart = true;
        }
    }

    @Override
    public boolean hasNext() { 
        if(isEmpty() || p == head && ! atStart) {
            return false;
        }
        return true;
    }

    @Override
    public E next() {
        E data = p.data;
        atStart = false;
        p = p.next;
        return data;
    }

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

}

这个迭代器有一个atStart标志，开头为true 。 因此，当在单项列表上hasNext()时，它会看到p指向头部，但它也会看到这是第一次，所以它返回true 。

在这种情况下， next()方法将为您提供p指向的数据，这是头部中的数据。 此时， atStart更改为false，因此虽然p是高级并且atStart回来，并且再次是head ，但是下次我们调用hasNext() ，我们将不会再次返回true 。

如果您有一个更长的列表，如2->1 ，您将第一次获得2 ，并且p将提前到1并且atStart为false。

现在第二次， hasNext()看到p指向不是head的1 ，所以它返回true 。 next()我们返回1 ，并将p前进到头部。

再次调用hasNext()将停止，因为p返回头部，但atStart为false。

循环单链表迭代器的问题

问题描述

1楼

2楼