By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,925 Members | 1,164 Online
Bytes IT Community
+ Ask a Question
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
Share this Question
Share on Google+
8 Replies


P: n/a
"Chinmoy Mukherjee" <a1****@motorola.com> 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" <a1****@motorola.com> 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

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

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

This discussion thread is closed

Replies have been disabled for this discussion.