Re: what happen in for (x:List) and iterator when adding to List
On Thu, 25 Sep 2008, Patricia Shanahan wrote:
George wrote:
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?
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
--
The revolution is here. Get against the wall, sunshine. -- Mike Froggatt