问题描述
我试图为我的循环单链表创建一个迭代器,但我不承诺如何实现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;
}
}
1楼
你的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
逻辑,如果这不起作用只是确保你的其他功能是正确的。
如果有任何问题,请告诉我。
2楼
是的,您的迭代器中存在问题。
它忽略了最后一项(头部)。
例如,假设您的列表中只有一个元素。
所以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。