How to copy a link list

Discussion in 'C++' started by Chinmoy Mukherjee, Jul 25, 2005.

  1. when the node structure is like

    struct node {
    node *next;
    node *rand; (// random is supposed to point to another
    node
    int value;
    }
    Chinmoy Mukherjee, Jul 25, 2005
    #1
    1. Advertising

  2. "Chinmoy Mukherjee" <> wrote in message
    news:...
    > when the node structure is like
    >
    > struct node {
    > node *next;
    > node *rand; (// random is supposed to point to another
    > node
    > int value;
    > }



    Traverse list, create copy of each node, link nodes correctly
    together.

    hth
    --
    jb

    (reply address in rot13, unscramble first)
    Jakob Bieling, Jul 25, 2005
    #2
    1. Advertising

  3. Chinmoy Mukherjee sade:
    > when the node structure is like
    >
    > struct node {
    > node *next;
    > node *rand; (// random is supposed to point to another
    > node
    > int value;
    > }
    >


    node * node::copy()
    {
    COPY THIS TO TEMP
    IF NEXT THEN
    LINK TEMP TO CALL NEXT COPY
    ENDIF
    RETURN TEMP
    }

    Tobias
    --
    IMPORTANT: The contents of this email and attachments are confidential
    and may be subject to legal privilege and/or protected by copyright.
    Copying or communicating any part of it to others is prohibited and may
    be unlawful.
    Tobias Blomkvist, Jul 25, 2005
    #3
  4. Chinmoy Mukherjee

    Guest

    If that node *rand really points to a random other node you need to add
    in an unique identifier (uid) in each node for copying purposes.
    Then you a have two/three step copy process.
    First create the new nodes with value and uid copied & next containing
    a pointer to a new node.
    Then traverse the newly created list adding the rand values.
    pseudocode
    dummy = first copied node
    while dummy->uid != original node->rand->uid dummy =
    dummy->next;
    copied node->rand = dummy;

    Third step is optional, assigning unique uids to the copied nodes.
    , Jul 25, 2005
    #4
  5. * Chinmoy Mukherjee:
    > when the node structure is like
    >
    > struct node {
    > node *next;
    > node *rand; (// random is supposed to point to another node
    > int value;
    > }


    Nitpick: missing semicolon.

    Since this is not a C++ question but a general programming question I've
    cross-posted this to [comp.programming], with follow-up there.

    Assumption 1. What you have is presumably a singly linked list embedded in a
    general graph, where each node has at most two outgoing connections, and at
    most one node has zero outgoing connections.

    Assumption 2. Copying the singly linked list structure is also presumably
    easy for you, whereas the 'rand' connections are problematic.

    Assumption 3. And finally, the reason they're problematic is presumably that
    you have some constraints, like (3.1) you want this done in time O(n) or
    thereabouts, where n is the number of nodes, and (3.2) you can't add
    additional fields.

    With no limitations on the graph structure other than what's mentioned above
    it seems your only option is to use an associative container. Current
    standard C++ doesn't have hash tables in the standard library, but they're
    common in actual implementations. If you want to only use standard
    containers a std::map will do the job, but then with total time O(n log n)
    (cirka).

    One way is to first copy only the singly linked list structure, noting in
    the associative container, for each node copied, an association from the
    original's pointer value to the copy's pointer value; then traverse the
    original list and update the 'rand' pointers in the copy.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Jul 25, 2005
    #5
  6. Chinmoy Mukherjee

    benben Guest

    The cleanest way:
    Provide iterators, use STL algorithms

    Ben

    > when the node structure is like
    >
    > struct node {
    > node *next;
    > node *rand; (// random is supposed to point to another
    > node
    > int value;
    > }
    >
    benben, Jul 25, 2005
    #6
  7. Thanks Jakob.
    But how to I remember the rand poniters of each node
    the idea is to retain the strcuture

    For example, assume we create a link list of size 5

    now assign node0->rand = node4
    node1->rand = node0
    node2->rand = node3
    node3->rand = node2

    Now question is how do I copy the link list to
    another link list so that the overall structure is retained.
    Regards,
    Chinmoy

    Jakob Bieling wrote:

    > "Chinmoy Mukherjee" <> wrote in message
    > news:...
    > > when the node structure is like
    > >
    > > struct node {
    > > node *next;
    > > node *rand; (// random is supposed to point to another
    > > node
    > > int value;
    > > }

    >
    > Traverse list, create copy of each node, link nodes correctly
    > together.
    >
    > hth
    > --
    > jb
    >
    > (reply address in rot13, unscramble first)
    Chinmoy Mukherjee, Jul 26, 2005
    #7
  8. * Chinmoy Mukherjee:
    > [top-posting]
    > [extranous quoting]


    Please don't top-post in this group

    Please don't quote irrelevant material.

    Read the FAQ.


    * Chinmoy Mukherjee:
    > * Jakob Bieling:
    > > * Chinmoy Mukherjee:
    > > > when the node structure is like
    > > >
    > > > struct node {
    > > > node *next;
    > > > node *rand; (// random is supposed to point to another
    > > > node
    > > > int value;
    > > > }

    > >
    > > Traverse list, create copy of each node, link nodes correctly
    > > together.

    >
    > Thanks Jakob.
    > But how to I remember the rand poniters of each node
    > the idea is to retain the strcuture


    Already answered in this thread, why don't you read the answers?

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Jul 26, 2005
    #8
  9. Chinmoy Mukherjee

    Guest

    > Now question is how do I copy the link list to
    > another link list so that the overall structure is retained.
    > Regards,
    > Chinmoy


    Don't you read replies given to your question?
    I and Steinbach gave you a way to do that.
    , Jul 26, 2005
    #9
    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. Kevin Spencer

    Re: Link Link Link DANGER WILL ROBINSON!!!

    Kevin Spencer, May 17, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    795
    Kevin Spencer
    May 17, 2005
  2. Alex
    Replies:
    2
    Views:
    1,202
  3. Dan M
    Replies:
    5
    Views:
    411
  4. Replies:
    26
    Views:
    2,088
    Roland Pibinger
    Sep 1, 2006
  5. Wouter
    Replies:
    14
    Views:
    300
Loading...

Share This Page