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

Discussion in 'Java' started by George, Sep 25, 2008.

  1. George

    George Guest

    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);
    }
     
    George, Sep 25, 2008
    #1
    1. Advertising

  2. George <> wrote:
    > 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, Sep 25, 2008
    #2
    1. Advertising

  3. Lew <> wrote:
    >> for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
    >> {....; list.add(x);
    >> }

    > 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".

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

    > 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, Sep 25, 2008
    #3
  4. Andreas Leitgeb <> wrote:
    > George <> wrote:
    >> for (x:list){
    >> ....; list.add(x);
    >> }

    > 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.)
     
    Andreas Leitgeb, Sep 25, 2008
    #4
  5. George

    Tom Anderson Guest

    On Thu, 25 Sep 2008, Andreas Leitgeb wrote:

    > 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

    --
    The revolution is here. Get against the wall, sunshine. -- Mike Froggatt
     
    Tom Anderson, Sep 25, 2008
    #5
  6. George

    George Guest

    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

    On Sep 25, 2:54 am, George <> wrote:
    > 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);
    >
    > }
    >
    >
     
    George, Sep 25, 2008
    #6
  7. George

    Lew Guest

    On Sep 25, 12:30 pm, George <> wrote:
    > 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.

    --
    Lew
     
    Lew, Sep 25, 2008
    #7
  8. George <> wrote:
    > 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)
     
    Andreas Leitgeb, Sep 25, 2008
    #8
  9. George

    George Guest

    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

    On Sep 25, 12:20 pm, Lew <> wrote:
    > On Sep 25, 12:30 pm, George <> wrote:
    >
    > > 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.
    >
    > --
    > Lew
     
    George, Sep 25, 2008
    #9
  10. 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?

    Patricia
     
    Patricia Shanahan, Sep 25, 2008
    #10
  11. George

    Tom Anderson Guest

    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
     
    Tom Anderson, Sep 25, 2008
    #11
  12. George

    George Guest

    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.

    On Sep 25, 2:01 pm, Tom Anderson <> wrote:
    > 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
     
    George, Sep 25, 2008
    #12
  13. George

    George Guest

    On Sep 25, 7:03 pm, Lew <> wrote:
    >
    > 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.
     
    George, Sep 26, 2008
    #13
  14. George <> wrote:
    > 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?
     
    Andreas Leitgeb, Sep 26, 2008
    #14
  15. George

    George Guest

    On Sep 26, 3:12 am, Andreas Leitgeb <>
    wrote:

    > 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.
     
    George, Sep 26, 2008
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendrik Maryns
    Replies:
    18
    Views:
    1,452
  2. greg
    Replies:
    6
    Views:
    475
    Dietmar Kuehl
    Jul 17, 2003
  3. Replies:
    6
    Views:
    681
    Jim Langston
    Oct 30, 2005
  4. David Bilsby
    Replies:
    5
    Views:
    2,078
    David Bilsby
    Oct 9, 2007
  5. Replies:
    4
    Views:
    197
    Christophe Grandsire
    Oct 28, 2005
Loading...

Share This Page