Creating a copy constructor for a linked list

Question

This is homework

I'm working on implementing a linked list class for my C++ class, and the copy constructor has be very confusing for me.

The linked list is comprised of structs called Elems:

struct Elem      {         int pri;         data info;         Elem * next;     };     Elem * head; 

info is a separate, custom class that is stored in the Elem.

the signature for the copy constructor is:

linkedList::linkedList( const linkedList &v ) 

The issue I am having is mostly taking my logic and actually writing it as code.

My general idea is to:

1. Set head to v.head (head = v.head)
2. Set the Elem's values to v's (pri = v.pri , info = v.info , next = v.next)
3. Iterate through, repeating step 2.

Is this the general idea?

Any help would be great. Remember, this is homework, so no direct answers please!

Thank you for your time

====================================================================================================================================================================

Thanks for your time everybody!

I think I have it figured out:

//Copy Constructor LinkedList::LinkedList( const LinkedList &v ) { Elem * p1 = 0;//current Elem * p2 = 0;//next  if( v.head == 0 )     head = 0;  else {     head = new Elem;     head -> pri = v.head -> pri;     head -> info = v.head -> info;      p1 = head;     p2 = v.head -> next; }  while( p2 ) {     p1 -> next = new Elem;     p1 = p1 -> next;     p1 -> pri = p2 -> pri;     p1 -> info = p2 -> info;      p2 = p2 -> next; } p1 -> next = 0; } 

I'm pretty sure that works. I drew some logical pictures to help, and I didn't run into any issues.

Answer 1

You have to be careful with Step 1 and part of Step 2. Step 1 should allocate a new node and use that as the head. In Step 2, the part about next = v.next, unless your intention is to make a shallow copy, is incorrect.

When you copy a container such as a linked list, you probably want a deep copy, so new nodes need to be created and only the data copied over. The next and prior pointers in the nodes of the new list should refer to new nodes you create specifically for that list and not the nodes from the original list. These new nodes would have copies of the corresponding data from the original list, so that the new list can be considered a by value, or deep copy.

Here is a picture depicting the differences between shallow and deep copying:

Notice how in the Deep Copy portion of the diagram, none of the nodes point to nodes in the old list. For more information about the difference between shallow and deep copies, see the Wikipedia article on object copying.

Answer 2

1. You shouldn't set this->head = v.head. Because the head is simply a pointer. What you need to do is to create a new head and copy the values individually from v.head into your new head. Otherwise you'd have two pointers pointing to the same thing.

2. You then would have to create a temporary Elem pointer that starts with v.head and iterate through the list, copying its values to new Elem pointers into the new copy.

3. See above.