454,925 Members | 1,164 Online
Need help? Post your question and get tips & solutions from a community of 454,925 IT Pros & Developers. It's quick & easy.

# How to copy a link list

 P: n/a when the node structure is like struct node { node *next; node *rand; (// random is supposed to point to another node int value; } Jul 25 '05 #1
8 Replies

 P: n/a "Chinmoy Mukherjee" wrote in message news:42***************@motorola.com... 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) Jul 25 '05 #2

 P: n/a 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. Jul 25 '05 #3

 P: n/a 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 '05 #4

 P: n/a * 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? Jul 25 '05 #5

 P: n/a 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; } Jul 25 '05 #6

 P: n/a 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:42***************@motorola.com... 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) Jul 26 '05 #7