Problems with looping single list iterator
I'm trying to make an iterator for my circular single linked list, but I don't understand how to implement the next () and hasNext () methods. I suspect I need to either 1) have additional fields in the linked list or iterator class, or 2) have references to something else instead of "head" and "tail"? My code is below:
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;
}
}
source to share
Yours is hasNext()
not entirely correct. Due to your condition, p == head
you will always skip printing the last item. Therefore, checking p
will not help in choosing hasNext()
.
Ideally, what you want to check q == head
is when you finish iterating over all the elements and back to the original element and yours hasNext()
should return false
, but if you just check q == head
it won't work because for your start element it won't work. So use the flag to see if you are back or if you are visiting for the first time.
I suggest you do something like this:
use a flag visitingAgain
.
boolean visitingAgain = false;
Use it in hasNext()
as shown below.
@Override
public boolean hasNext() {
if (p == q || (q == head && visitingAgain)){
return false;
}
visitingAgain = true; // once you start iterating change this flag.
return true;
}
NOTE I haven't tested the logic completely insert
and delete
if that doesn't work just make sure your other functions are correct. Let me know if there are any problems.
source to share
Yes, there is a problem in your iterator. It ignores the last element (head). For example, imagine you only have one item in your list. Thus, both head
and tail
point to it as well head.next
.
Now, if we ask hasNext()
about a new iterator in such a list, we have to get true
once, and then, after we call next()
, get false.
But your condition:
if(p == q || p == head) {
return false;
}
This means that for a single element list, you will return false
no matter what.
Also, even if we assume we have multiple elements, let's say:
2->1
Then you initialize the iterator with p = head.next
and q = head
. Yours hasNext()
will return true, but what does yours next()
do?
public E next() { //doesn't work
E data = q.data;
q = p;
p = p.next;
return data;
}
So it returns 2
at the beginning and moves p
and q
. It's OK 2
. But now q
points to points 1
and p
again to 2
. And again yours hasNext()
sees that p == head
and says that there are no more elements!
So, the item currently pointed q
to by the valid next item is ignored.
What you need to do is have some kind of flag that tells you when you hit your head the second time, not the first. And no need for two pointers. Here is my iterator version:
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();
}
}
This iterator has a flag atStart
that starts like true
. So when hasNext()
called on a list with one item, it sees that it is p
pointing to the head, but it also sees that this is the first time it does, and so it returns true
.
And the method next()
in this case will give you the data it points to p
, which is the data in the head. At this point it atStart
changes to false, so although it p
advances and spins backwards and again head
, the next time we call hasNext()
, we won't return any more true
.
And if you have a longer list, for example 2->1
, you will get 2
the first time, and p
- in 1
and atStart
- false.
Now the second time hasNext()
sees what is p
pointing to 1
, which is not head
, so it returns true
. And in next()
we return 1
and advance p
to the head.
The call hasNext()
will stop again because it p
goes back to the head but atStart
is false.
source to share