what happen in for (x:List) and iterator when adding to List

[George]

Hi,

I need to do a breadth-first search on a graph. So I need to have a
list for element and iterator over it while keep adding element in the
end of the list. I am currently using ArrayList in java 5. I
remembered vaguely something about the iterator is unpredictable when
the collection changed. Is it true?

Can I use
List<E> list=new ArrayList<E>;
......
for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
{....; list.add(x);
}

or can I use

for (x:list){
.....; list.add(x);
}

 

[Andreas Leitgeb]

for (x:list){
....; list.add(x);
}

That will not work, but perhaps this will:

ArrayList auxList=new ArrayList();
do {
auxList.clear();
for (Object x:list) { ...; auxList.add(x); }
list.addAll(auxList);
} while (!auxList.empty());

I didn't test it, but hope for lack of typoes and thinkoes.

 

[Andreas Leitgeb]

Where does 'x' come from?

Probably it doesn't matter at all. It's just some element that's
to be added to end of the currently iterated list.
It doesn't work that way, of course. I understood the question not
so much as about the "why", but rather about "how else can I achieve
such an effect".

Wouldn't that make the List grow until it hits OutOfMemoryError (OOME)?
(Isn't that the point of Andreas' response?)

No that wasn't it. I (boldly) assumed, that the ".....;" contained
something like: "if (x.exhausted()) continue; x.exhaustGradually();"

Anyway, I meanwhile noticed, that my code is broken as well, because
I re-iterate also those elements that were originally in list...

 

[Andreas Leitgeb]

That will not work, but perhaps this will:

On review (and after Lew's comment): no it didn't, either.
Follows next attempt:

ArrayList auxList=new ArrayList( list );
do {
ArrayList newList=new ArrayList();
for (Object x:auxList) { ...; newList.add(x); }
list.addAll(newList); auxList=newList;
} while (!auxList.empty());

As long as the inner loop produces new elements, the outer
list will take care of adding them to the original list
(which is not iterated itself, so it's ok) and of preparing
for next run of the inner loop.

I didn't test it, but hope for lack of typoes and thinkoes.

Same again.

PS: maybe the ArrayDeque would be more appropriate for your task
(and you wouldn't iterate() it, but poll() the first element, and
eventually offer() one to the far end of the queue.)

 

[Tom Anderson]

PS: maybe the ArrayDeque would be more appropriate for your task
(and you wouldn't iterate() it, but poll() the first element, and
eventually offer() one to the far end of the queue.)

Yes, i think what the OP really wants is a queue - certainly, if he's
doing breadth-first search in the normal way, that's exactly what he
needs. It doesn't need to be a deque, but ArrayDeque is the best
all-round implementation of Queue. So:

void breadthFirstVisit(Node root, NodeVisitor visitor) {
Queue<Node> toVisit = new ArrayDeque<Node>() ;
toVisit.add(root) ;
while (!toVisit.isEmpty()) {
Node n = toVisit.remove() ;
for (Node child: n.getChildren()) toVisit.add(child) ;
visitor.visit(n) ;
}
}

tom

 

[George]

Thank you all.

Thanks for the remind about javadoc. I should have read about it.

What I am trying to do is the build-up the breadth-first tree
traverse from a node in a graph if you are familiar with data
structure. This can be accomplished by a "link-list" or array in the
traditional data structure sense. I have one node at first. Then I
add all the connected NEW nodes of the current node to the end while
going through the link-list. I just figure it might be quicker and
safer to use something ready in java rather than building my own. But
there seems to be no mechanism in collection framework. The two for
coupling should work, but it would be inefficient because it checks
the connection of those nodes that I have already checked. I am using
java 5. So I cannot use Deque.

Any suggestion?

Sincerely
Zhu, Guojun

 

[Lew]

Thank you all.

Please do not top-post.

I just figure it might be quicker and
safer to use something ready in java rather than building my own.  But
there seems to be no mechanism in collection framework.  The two for
coupling should work, but it would be inefficient because it checks
the connection of those nodes that I have already checked.  I am using
java 5.  So I cannot use Deque.

No, but Queue is available in 1.5, and that's what you need.

<http://java.sun.com/javase/6/docs/api/java/util/Queue.html>
<http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html>

Once again, the Javadocs rescue you. You should've looked up "Queue"
the minute it was mentioned.

 

[Andreas Leitgeb]

I am using java 5. So I cannot use Deque.
Any suggestion?

Now that you know the javadocs, hinting you towards
Queue and LinkedList (as a standard class implementing
Queue) should get you further. (these two do exist in 1.5)

 

[George]

Thanks. The queue can do that but seems not very efficient since I do
need the full list instead of the working one. I am end up using a
bare array to implement it. I just make an array with the size of the
graph nodes and use the primitive int i as iterator. Sometimes, one
probably needs to fall back to the basic things.

Sincerely
Zhu, Guojun

 

[Patricia Shanahan]

Thanks. The queue can do that but seems not very efficient since I do
need the full list instead of the working one. I am end up using a
bare array to implement it. I just make an array with the size of the
graph nodes and use the primitive int i as iterator. Sometimes, one
probably needs to fall back to the basic things.

....

As a matter of curiosity, did you measure the queue based method?

Patricia

 

[Tom Anderson]

...

As a matter of curiosity, did you measure the queue based method?

If by "I do need the full list instead of the working one" he means that
he needs to keep the entire list of nodes traversed, in breadth-first
order, then that's actually a real pain to implement with a LinkedList:
you can't use an Iterator to walk through the list, because it'll fail
fast when you append newly encountered nodes (won't it?). You'd have to
track the index and do get(). Whilst i haven't got benchmarked this, that
makes the whole traversal O(n^2), which doesn't sound good.

He could split the job into two lists, and use a LinkedList for the
to-visit queue and then a separate list, either linked or array, for nodes
visited, which will end up being the complete list. But i don't see an
advantage over just using an ArrayList (to which addition is O(1)) to
track nodes encountered, whether visited or not, and keeping a finger in
it for the next node to visit.

tom

 

[George]

That is what I thought about queue methods mostly. I need a breadth-
first search list. I thought about two-queue solution as well. I feel
that gives me not much advantages, but make things somehow complicated
just for the sake of using collections. Furthermore, I feel a simple
array might be faster than LinkList. Am I correct?

I use a Set to test whether it is new or not instead of the ArrayList
approach.

 

[George]

What is what you thought?  The top-posting mangled the referent, so we have no
idea what you meant.  Was it, "The revolution is here. Get against the wall,
sunshine"?

~~~~~~~~~~~~~~~~~
I mean the Tom Anderson's reply about the ineffective of one link-list
in the breath-first search.

"Might be" is the operative term.

Or you might find that the coding effort to handle an array is so much larger
than with a Queue that it isn't worth the piddling speedup you might get.  Or
might not.  You'll need to benchmark your program to be certain.

~~~~~~~~~~~~~~~~~~~~~~~~~~
It is actually not complicated at all to use array. I just need two
int variables as the scroll pointer and the tail pointer.

Here is another guess: Can I put two iterators on a LinkList? one for
scroll and the other tail for insert. When I add in the tail, will
the scroll iterator change or break down? Thanks.

 

[Andreas Leitgeb]

It is actually not complicated at all to use array. I just need two
int variables as the scroll pointer and the tail pointer.

If you do it that way, you'll find it hard to "grow" the queue
lateron, especially if the writing pointer has already wrapped
around. I don't say it's impossible, but not exactly trivial.

Here is another guess: Can I put two iterators on a LinkList? one for
scroll and the other tail for insert. When I add in the tail, will
the scroll iterator change or break down? Thanks.

It will break :-(

It will, however work, if you do *not* use an iterator for
scanning the list, but use the Queue-methods on the LinkedList.

And if you want to leave old elements in the list, then find my
(updated) algorithm in another subthread.

PS:
I wonder, how complicated it would be to create a "non-fail-at-all"-
iterator for LinkedLists (by re-implementing them). I wouldn't consider
it impossible. Perhaps such a thing even exists?

 

[George]

If you do it that way, you'll find it hard to "grow" the queue
lateron, especially if the writing pointer has already wrapped
around.  I don't say it's impossible, but not exactly trivial.

~~~~~~~~~~~~~~~~~
Thanks for the comment. It is probably all right in the breadth-first
search since the list size is more or less in the same order as the
total number of the nodes. But I will keep it in mind and I can fall
back to this in case the graph becomes very disconnected.

I am just a bit surprised to the difference of the link-list in data
structure and the LinkList in java collection framework. My
requirement seems quite basic for a link-list and yet it is not
provided. Maybe there is some intrinsic problem in the generic
implementation. Or maybe it can be added in some time later.