[simple] Deep copy of a linked list
Apr 12, 2012 at 7:31pm UTC
I'm trying to perform a deep copy of a linked list and print out the length and sum of the copied linked list, however, there is some kind of problem and I can't pinpoint it.
Can someone figure out what is wrong?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
#include <iostream>
using namespace std;
struct listrec
{
int value;
listrec *next;
};
int listsize(listrec *top)
{
listrec *pt; // creates pointer
pt = top;
int i = 0;
while (pt != NULL)
{
i += 1;
pt = pt->next;
}
return i;
}
int listsum(listrec *top)
{
listrec *pt; // creates pointer
pt = top;
int sum = 0;
while (pt != NULL)
{
sum += pt->value;
pt = pt->next;
}
return sum;
}
void deepCopy(listrec* x, listrec* ©)
{
while (x != NULL)
{
{
listrec* copy = new listrec;
copy->value = x->value;
copy->next = x->next;
x = x->next;
}
}
}
int main()
{
listrec *ptr, *head, *head2; // create 2 pointers (ptr, head)
int a = 4, b = 5, c = 3; // definitions
head = new listrec; // creates new node
head->value = a;
head->next = new listrec; // creates new node
ptr = head; // sets up a linked list location
ptr = ptr->next;
ptr->value = b;
ptr->next = new listrec; // creates new node
ptr = ptr->next;
ptr->value = c;
ptr->next = NULL;
cout << listsize(head) << endl; // prints the size of linked list
cout << listsum(head) << endl; // prints the sum of all values in linked list
deepCopy(head, head2);
cout << listsize(head2) << endl;
cout << listsum(head2) << endl;
system("PAUSE" );
return 0;
}
Apr 12, 2012 at 8:31pm UTC
The problem with deepCopy is that it points the next pointer of the new nodes to the nodes in the old list.
Apr 12, 2012 at 8:59pm UTC
I would do it like this:
1 2 3 4 5 6 7 8 9 10 11 12
listrec* deepCopy(const listrec*©)
{
listrec* result = new listrec (*copy),
*copyiterator = result;
for (listrec* iterator = copy->next; listrec != nullptr ; listrec = listrec->next)
{
copyiterator->next = new listrec (*iterator);
copyiterator = copyiterator->next;
}
copyiterator->next = nullptr ;
return result;
}
the line:
new listrec (*copy)
creates an exact copy of the copy argument, however, the ->next member of this copy is still the same as the original copy member's ->next, so we need to iterate through all the items in the linked list creating copies, which is what we are doing with the:
1 2 3 4 5
for (listrec* iterator = copy->next; listrec != nullptr ; listrec = listrec->next)
{
copyiterator->next = new listrec (*iterator);
copyiterator = copyiterator->next;
}
NOTE: you should probably replace nullptr with NULL in that function seeing as you are using NULL, nullptr means null pointer but its not the same as NULL
Last edited on Apr 12, 2012 at 9:04pm UTC
Topic archived. No new replies allowed.