Reputation: 4320
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:
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.
Upvotes: 24
Views: 82070
Reputation: 1
You forgot the line
return;
after
if( v.head == 0 )
head = 0;
You need to get out, right?
Upvotes: 0
Reputation: 74470
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.
Upvotes: 28
Reputation: 7164
So here is my answer (don't know if that fits to your homework or not - instructors tend to have their own ideas sometimes ;):
Generally a copy constructor should "copy" your object. I.e. say you have linkedList l1, and do a linkedList l2 = l1 (which calls linkedList::linkedList(l1)), then l1 and l2 are totally separate objects in the sense that modification of l1 doesn't affect l2 and vice versa.
When you just assign pointers you won't get a real copy, as dereferencing and modifying either of them would affect both objects.
You rather want to make a real deep copy of every element in your source list (or do a copy-on-demand only, if you want to be fancy).
Upvotes: 0
Reputation: 54584
What should your copy constructor copy? It should copy pri
- easy. It should copy info
- easy as well. And if next
is not null, it should copy it, too. How can you copy next
? Think recursive: Well, next
is an Elem *
, and Elem
has a copy constructor: Just use it to copy the referenced Elem
and refer to it.
You can solve this iteratively, too, but the recursive solution is much more intuitive.
Upvotes: 2
Reputation: 5204
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.
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.
See above.
Upvotes: 4