C++ deep copy a linked list resursively

Question

I am a C++ beginner trying to write a function to create a deep copy of a linked list in C++. The function calls itself until it is at the last node in the source list, then copies that node. However when I run this I get a segmentation fault or EXC_BAD_ACCESS error. Here is what I have so far:

struct node {
int data;
node* next;
};    


void copy_list(const node*& source_ptr, node*& dest_ptr)
{
if (dest_ptr != nullptr){
    clear_list(dest_ptr);
    }

if (source_ptr == nullptr) return; //we already cleared dest_ptr

if (source_ptr->next == nullptr) // this is the last node
{
    dest_ptr = new node(); //initialize in memory
    dest_ptr->data = source_ptr->data; //copy the last datum
    dest_ptr->next = nullptr; //since this is the end
    return;
}
const node* cursor = source_ptr->next; // this happens if source is not yet at the end

copy_list(cursor, dest_ptr->next);
}

I know there are other questions similar to this, but they haven't helped me. I have also tried using other methods than recursion for example a while loop that looks something like:

dest_ptr = new node(); 
dest_ptr->data = source_ptr->data;
node* dest = dest_ptr->next;
const node* cursor = source_ptr->next; 

 while(cursor != nullptr)
{
    dest = new() node; 
    dest-> data = cursor->data;
    //dest->next = nullptr;
    dest = dest->next;
    cursor = cursor->next;
}

The while loop doesn't give errors but the copy is blank (except for the first node which is copied outside the while loop).

Any help is greatly appreciated. Thanks!

Answer 1

If you're a beginner, start from simple things: try to avoid recursion until you understand loops. So I will only comment on the loop version (recursion is a bad approach to this particular problem anyway).

If code doesn't do what you want, you should try stepping through it in a debugger to note what exactly it does, or try to explain it as a list of instructions to someone (a rubber duck is ideal for this, as it's patient).

You can also approach this by reasoning about the code:

Each variable should have a clearly defined purpose, ideally reflected in its name. I can see that the purpose of source_ptr is to point to the source list. And the purpose of cursor is to traverse the source list.

dest_ptr is probably intended to hold the newly created copy. You're taking a good start by copying the first data into it.

What is the purpose of dest, however? You start by copy the value of dest_ptr->next (which will actually be null) into it. Then, in the loop, you immediately overwrite dest with a newly created node. Copy cursor->data into this new node, and copy the (uninitialised this time) pointer dest->next into dest. However, note that you never read the value of dest, you just overwrite it in the next iteration.

I suspect you actually intended dest to be a pointer to a pointer to node, and your intention was to do this:

dest_ptr = new node();
dest_ptr->data = source_ptr->data;
node **dest = &dest_ptr->next;
const node *cursor = source->ptr->next;

while (cursor)
{
  *dest = new node();
  (*dest)->data = cursor->data;
  dest = &((*dest)->next);
  cursor = cursor->next;
}

This would do what you want, but pointers to pointers are ugly. It would be better to use dest as a second cursor for traversing the destination list:

dest_ptr = new node();
dest_ptr->data = source_ptr->data;
node *dest = dest_ptr;
const node *cursor = source_ptr->next;

while (cursor)
{
  dest->next = new node();
  dest = dest->next;
  dest->data = cursor->data;
  cursor = cursor->next;
}