Copy constructor for very simple singly linked list (C++)?

Question

I am having quite a bit of difficulty understanding how to implement a copy constructor for a singly linked list in C++. Heres is the code I have for the implementation:

--------------------------------------…
struct node {
string value;
node * next;
};

class strSet {

private:
node * first //points to the first node of the object;

public:
...
strSet (const strSet& copy);
...
};
--------------------------------------…

I am having difficulty implementing this copy constructor. Can anyone shed some light? I'm not sure what to put in the body.

strSet (const strSet& copy) {

Answer 1

I find copy constructors for trees and hand-crafted lists such as these to be easier done if each Node is able to deep-copy itself. You could have a one-liner copy-constructor like



     strSet::strSet(const strSet& copy)

         : first(copy.first ? new node(*copy.first) : NULL)

     {

     }



which simply copy-constructs the node pointed-to by copy.first, if it exists.



Given that node has a copy-constructor too, such as



     node::node(const node& copy)

         : value(copy.value)

         , next(copy.next ? new node(*copy.next) : NULL)

     {

     }



it will in turn copy-construct the node pointed-to by copy.next if it exists, and so on, recursively.



In practice, if I ever had to hand-craft a linked list, I would use C++ pointers (auto_ptr/unique_ptr/etc) to provide exception safety and get rid of destructors.

Answer 2

If you want to construct new object from the old one that was passed as a parameter

there are 3 steps involved:

1) create new empty list

2) while there is next element of old list

3) get the next element of old list

4) create new element for new list (with the values from old list element) and insert it in the new list

5) iterate to 2)



Step 4) relies on CORRECT implementation of add(Node n) method in your list class.

Answer 3

First, let's do this one step at a time: strSet(const strSet ©) { ...first = copy.first; // Copy the pointer to their node, for a starter ...struct node **next = &first; // Show that we're working on the First pointer ...while (**next) { // Proceed while we need to clone nodes ......struct node *newNode = malloc(sizeof(struct node); // Allocate a node ......*newNode = **next; // Fill it ......*next = newNode; // Have the pointer we're working on point at the new storage ......next = &newNode->next; // Advance to work on the next pointer ...} } This collapses to: strSet(const strSet ©) { ...first = copy.first; ...for (struct node **next=&first; **next; next=&newNode->next) { ......struct node *newNode = malloc(sizeof(struct node); ......*newNode = **next; ......*next = newNode; ...} }