why isnt deep copy working?

[catastrophe2]

hi

so i have to make a copy of a linked list i made last week and this time i just have to update it with a deep copy concept thus making a copy of that list i made. here is my code:

#include <iostream>
#include <string>

using namespace std;

struct listrec // one node of singly-linked list
{
    int value;
    listrec *next; // next is pointer variable that points to the next node in the list
};

void deepcopy(listrec *old_linked_list, listrec *&new_linked_list)
{
    // perform a deep copy from old_linked_list to new_linked list
    while (old_linked_list != NULL)
    {
        new_linked_list->value = old_linked_list->value;
        new_linked_list->next = old_linked_list->next;
        old_linked_list = old_linked_list->next;
        new_linked_list = new_linked_list->next;
    }
}

void main()
{
    listrec x1, x2, x3; // creating 3 nodes
    x1.value = 4; x2.value = 5; x3.value = 3;

    x1.next = &x2; // set up a link from x1 to x2
    x2.next = &x3; // set up a link from x2 to x3
    x3.next = NULL; // specify the end of the linked list

    // inserting a node
    listrec x4; x4.value = 6;
    x1.next = &x4;
    x4.next = &x2;

    listrec *head_old, *head_new = NULL;

    head_old = &x1; //*beginning memory address of the old linked list*/
    head_new = head_old;

    deepcopy(head_old, head_new);

    // Old list cout
    cout << "This is the x1, x4, x2, and x3 nodes linked list: ";
    while (head_old != NULL)
    {
        cout << head_old->value << " ";
        head_old = head_old->next;
    }

    cout << endl << endl;

    // print out the information in the linked list pointed by head_new; copied list cout
    cout << "Copied list: ";
    while (head_new != NULL)
    {
        cout << head_new->value << endl;
        head_new = head_new->next;
    }

    cout << endl << endl;

    system("pause");
}

when i run it, it runs fine, but only the old list is listed, the copied list has nothing cputed next to it. whats going on? i have a feeling its the x4 node that i passed next after x1 and before x2...if so, how do i go by fixing it? i know that its a very tiny mistake here, but what is it and how do i go about fixing it?

thnx!

[Moschops]

You've only got one list. You need to have TWO lists, and copy the data from one to the other.

[Schol-R-LEA]

Actually, it is not that minor a mistake: you never allocate any listrec nodes for the new list. What is surprising is that this doesn't cause a segfault, as you are writing to an area of memory you shouldn't have permissions for.

There also seems to be a conceptual disconnect on the idea of a linked list at work. Right now, you are creating local variables in main() for the list nodes; this defeats the purpose of a linked list, which is meant to be a dynamic data structure. While it is possible to have a linked list the way you've done it, it limits the size to what you have declared already. Instead, what usually would be done is to allocate the nodes at runtime, and free them after they are finished with:

node = new listrec();

// add the node to the list and use it

// then after you are done, free it
delete node;

I would recommend breaking your main() function up into two new functions: one for allocating a node and adding it to the list, and one for printing the list. I would also add a function for freeing the lists.

struct list
{
   listrec* head;
   listrec* tail;
}

listrec* makenode(int value)
{
    listrec* node = new listrec();

    if (node == 0)
    {
        throw "out of memory error";
    }
    else
    {
        node ->value = value;
        node ->next = 0;
    }
    return node;
}

// add the new value to the head of the list, stack-wise
list push(list lst, int value)
{
    listrec* node = makenode(value);

    if(lst ->head == 0) 
    {
        lst->tail = node;
    }
    node ->next = lst ->head;
    lst ->head = node;

    return lst;
}

// add the new value to the tail of the list, queue-wise
list enqueue(list lst, int value)
{
    listrec* node = makenode(value);

    if(lst ->head == 0) 
    {
        lst->head = node;
    }

    lst ->tail = node;

    return lst;
}

// add the new value to the list in order of value
list insert(list lst, int value)
{
    listrec* node = makenode(value);


    if(lst ->head == 0) 
    {
        lst->head = node;
        lst ->tail = node;
    }
    else
    {
        listrec* position = lst ->head;

        while (position != 0)
        {
            if (position ->value > value)
            {
                position = position ->next;
            }
            else
            {
                node ->next = position ->next;
                position ->next = node;
                break;
            }
        }
    }
    if (node ->next == 0)
    {
        lst ->tail = node; 
    }

    return lst;
}

Which you will want depends on what you need. Printing and freeing the list are left as an exercise.

If you know about classes and objects, it would be even better to re-write the list handing as a class. I don't know if you've gotten that far in your studies, however.

BTW, you should never declare main() as any type other than int. While the standard used to allow it, it was never portable; the provision for no return value was to make it less problematic for embedded systems. Most OSes do expect a return value (holding a success/failure indicator), and you ought to give it one.

[Moschops]

Actually, it is not that minor a mistake: you never allocate any listrec nodes for the new list. What is surprising is that this doesn't cause a segfault, as you are writing to an area of memory you shouldn't have permissions for.

The new linked list is the old one, thanks to line 41; the code copies data back into the same place it got it.

[catastrophe2]

so i am confused now. how do i make a new list and where do i put it? what do i change? i dont wanna just try to no avail. i did write the code but i am not a full expert because of that lol.

thnx for responding both of you!

[Moschops]

how do i make a new list and where do i put it?

A list is "just" some nodes, pointing to each other. Here is how you made the first list:

listrec x1, x2, x3; // creating 3 nodes
    x1.value = 4; x2.value = 5; x3.value = 3;

    x1.next = &x2; // set up a link from x1 to x2
    x2.next = &x3; // set up a link from x2 to x3
    x3.next = NULL; // specify the end of the linked list

Now make another one.

[catastrophe2]

whats the point? thats not deep copy lol. sry i am not quite an expert in c++, but this is illogical in a way. why would i make a new list? i can just cout that new list then, and pretend to my professor there is a copy. no?

[Moschops]

thats not deep copy lol.

Correct. It's how to make a new list. Since you were having so much trouble with "how to make a new list", you specifically asked " how do i make a new list" and I told you. You make a new list, and then you copy the data from the old list to the new one.

why would i make a new list?

This is just a failure of imagination on your part. Perhaps you want to allow the user to make changes to the list but give them the option to cancel all changes and go back to how it was at the start. Deep-copying the list allows you to do this. Perhaps the user wants to make a whole new list, with some changes, but instead of having to build the list slowly one node at a time, they wish to base their new list on an existing one (have you ever edited an image or a document, and then saved the new one under a different name?). Just because you can't think of a reason to do something doesn't mean it's useless. You're learning how to use the tools with simple examples designed to teach you methods without having to think about other things.

i can just cout that new list then, and pretend to my professor there is a copy. no?

Of course you can. If you choose not to learn, that's up to you. You could just output the original list and say it's the copy.

[catastrophe2]

how to make a new list

I meant like i thought its a line of code that somehow converts old list to the new one, like the lines i have in deep copy. actually, my professor said i have the lines in deep copy function wrong, he never said anything i have to make a new list like you tell me to. of course, my professor always has not very good suggestions (he complicates things when the problem is simpler than to be complicated) so thats why i am finding it hard to see why would i make a whole new list of new nodes (like x5, x6, x7.) do you mean like i leave them empty like that as though they are arrays that store the copied values in them in a way? if so, here is what i can come up with, and tell me if i have it in right location:

#include <iostream>
#include <string>
using namespace std;
struct listrec // one node of singly-linked list
{
    int value;
    listrec *next; // next is pointer variable that points to the next node in the list
};
void deepcopy(listrec *old_linked_list, listrec *&new_linked_list)
{
    // perform a deep copy from old_linked_list to new_linked list
    while (old_linked_list != NULL)
    {
        new_linked_list->value = old_linked_list->value;
        new_linked_list->next = old_linked_list->next;
        old_linked_list = old_linked_list->next;
        new_linked_list = new_linked_list->next;
    }
}
void main()
{
    listrec x1, x2, x3; // creating 3 nodes
    x1.value = 4; x2.value = 5; x3.value = 3;
    x1.next = &x2; // set up a link from x1 to x2
    x2.next = &x3; // set up a link from x2 to x3
    x3.next = NULL; // specify the end of the linked list

    // inserting a node
    listrec x4; x4.value = 6;
    x1.next = &x4;
    x4.next = &x2;

    // new list?
      listrec x5, x6, x7, x8; // creating 3 nodesfor new list
    x5.value = &x1; x6.value = &x4; x7.value = &x2; x8.value=&x3;

    x5.next = &x6; // set up a link from x5 to x6
    x6.next = &x7; // set up a link from x6 to x7
    x7.next = &x8;
    x8.next = NULL; // specify the end of the linked list

    //so is the above location and code for "new list" correct?

    listrec *head_old, *head_new = NULL;
    head_old = &x1; //*beginning memory address of the old linked list*/
    head_new = head_old;
    deepcopy(head_old, head_new);

    // Old list cout
    cout << "This is the x1, x4, x2, and x3 nodes linked list: ";
    while (head_old != NULL)
    {
        cout << head_old->value << " ";
        head_old = head_old->next;
    }
    cout << endl << endl;

    // print out the information in the linked list pointed by head_new; copied list cout
    cout << "Copied list: ";
    while (head_new != NULL)
    {
        cout << head_new->value << endl;
        head_new = head_new->next;
    }
    cout << endl << endl;
    system("pause");
}

[Moschops]

Perhaps I misunderstand what you mean by "copy". To me, when you say "copy", it means starting with one object, and making another one just like it; if you start with one list, and then you copy it, you finish up with your original list and another one just like it (which means it has the same data values, but it's a complete new list - all the nodes are new and none of them are also in the old list). Is this not what you mean by "copy"?

Anyway, your logic in deepcopy is wrong, if you are meant to be making another list just like the original.

Here is the logic to do a deepcopy of lists:

Look at data value in old list node.
Copy that data value into new list node's data value.
Look at data value in next old list node.
Copy that data value into next new list node's data value.
Look at data value in next old list node.
Copy that data value into next new list node's data value.
...
...
Keep going until end.

If you don't understand this logic, stop coding and do it on paper using boxes and arrows. This programming assignment is trivial to code, but if you don't understand what's meant by "copy" in this case, you'll never get anywhere.

Look at this line of code in your deepcopy function.
new_linked_list->next = old_linked_list->next;
You're making a node in the new list point at a node in the old list. This is not making a whole new list. This is making your "new" list out of parts of the old one.

Start by checking what you mean by "copy". If the aim is not to finish up with a new list that has the same data values (but NOT the same nodes) as the old list, then ignore what I've said.

[catastrophe2]

as someone who is still learning c++, deep copy revelas to me exactly as it suggest: copying same values of something else. so your aim is correct to me, but i just thought with the lines i have in deep copy function, SOMEHOW, the program understands by itself to do a copy without needs of nodes again. i understand the logic of what you listed, but i dont know how to code it. thats the problem i face, not logic. if you can show me just this in "code form"

Look at data value in old list node.
Copy that data value into new list node's data value.

then ill be able to understand you further and continue on this. i never thought this assignment is trivial because its only a 1st question of a simple supposed to be lab, and the assignment is actually a continuation of the week before it lab, where we had to make the linked list initially, and then the week after we just had to deep copy it, and it sounded simple to do because it shouldnt be that trivial. but you are revealing otherwise it seems...

[Moschops]

Do not copy the node; only the value IN the node.

// assume new list has same number of nodes as old list,
//  and that the last node has NULL as the value for its "next" pointer

do
{
      // copy the data from old node to new node  
       new_linked_list_node_to_copy_into->value = old_linked_list_node_to_copy_from->value;

      // move on to next node in new list 
       new_linked_list_node_to_copy_into = new_linked_list->next;

       // move on to next node in old list
       old_linked_list_node_to_copy_from = old_linked_list_node_to_copy_from->next;

} while(new_linked_list_to_copy_into->next != NULL)  // stop when there is no next node

[Schol-R-LEA]

While it does add an extra wrinkle to the process, I would argue that many of the conceptual problems you are having will be solved if, rather than having a fixed list which you create statically and then populate, you were to dynamically create the second list by allocating new nodes at runtime. It would make the fact that you are creating a whole new copy of the list rather than just copying the data values. It would also, as I stated previously, make the purpose of linked lists as a dynamic, resizable strcture more evident. If you were to take my previous code example, and make the lists at runtime rather than declaring a lot of node variables, you would see this a lot clearer. This would be particularly clear if you allowed the user to enter the data, and let them choose how many data points to have.

(BTW, main() should always be declared as returning an int, as it passes a status value back to the command-line shell; void main() is incorrect for almost all cases.)

list* copylist_sorted(list a)
{
    if (a == 0)
        return 0;

    listrec old = a ->head;
    list* copy = new list();

    while (old != 0)
    {
        insert(copy, old ->value);
        old = old->next;
    }

    return copy;
}

int main()
{
    list* queue[2];
    int temp;
    char yesno;

    queue[0] = new list();

    do
    {
        cout << "Please enter an integer value: ";
        cin >> temp;
        enqueue(queue[0], temp);
        cout << " Continue (Y/N)? ";
        cin >> yesno;
    } while (toupper(yesno) == 'Y');

    cout << "The original list is: ";
    printlist(queue[0]);

    queue[1] = copylist_sorted(queue[0]);

    cout << "The sorted copy of the list is: ";
    printlist(queue[1]);

    freelist(queue[0]);
    freelist(queue[1]);

    return 0;
}

[catastrophe2]

i got it working.

thnx everyone!