How to copy a link list

[Chinmoy Mukherjee]

when the node structure is like

struct node {
node *next;
node *rand; (// random is supposed to point to another
node
int value;
}

 

[Jakob Bieling]

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

 

[Tobias Blomkvist]

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

 

[velthuijsen]

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.

 

[Alf P. Steinbach]

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

 

[benben]

The cleanest way:
Provide iterators, use STL algorithms

Ben

 

[Chinmoy Mukherjee]

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

 

[Alf P. Steinbach]

* 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:

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?

 

[velthuijsen]

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.