Coding a function to copy a linked-list in C++

Question

I need to implement an auxilliary function, named copyList, having one parameter, a pointer to a ListNode. This function needs to return a pointer to the first node of a copy of original linked list. So, in other words, I need to code a function in C++ that takes a header node of a linked list and copies that entire linked list, returning a pointer to the new header node. I need help implementing this function and this is what I have right now.

Listnode *SortedList::copyList(Listnode *L) {

    Listnode *current = L;  //holds the current node

    Listnode *copy = new Listnode;
    copy->next = NULL;

    //traverses the list
    while (current != NULL) {
       *(copy->student) = *(current->student);
       *(copy->next) = *(current->next);

        copy = copy->next;
        current = current->next;
    }
    return copy;
}

Also, this is the Listnode structure I am working with:

struct Listnode {    
  Student *student;
  Listnode *next;
};

Note: another factor I am running into with this function is the idea of returning a pointer to a local variable.

Answer 1

The first question you need to ask yourself is what the copy semantics are. In particular, you're using a Student* as node contents. What does copying node contents mean? Should we copy the pointer so that the two lists will point to (share) the same student instances, or should you perform a deep copy?

struct Listnode {    
  Student *student; // a pointer?  shouldn't this be a `Student` object?
  Listnode *next;
};

The next question you should ask yourself is how you will allocate the nodes for the second list. Currently, you only allocate 1 node in the copy.

I think you code should look more like:

Listnode *SortedList::copyList(Listnode *L) {

    Listnode *current = L;

    // Assume the list contains at least 1 student.
    Listnode *copy = new Listnode;
    copy->student = new Student(*current->student);
    copy->next = NULL;

    // Keep track of first element of the copy.
    Listnode *const head = copy;

    // 1st element already copied.
    current = current->next;

    while (current != NULL) {
       // Allocate the next node and advance `copy` to the element being copied.
       copy = copy->next = new Listnode;

       // Copy the node contents; don't share references to students.
       copy->student = new Student(*current->student);

       // No next element (yet).
       copy->next = NULL;

       // Advance 'current' to the next element
       current = current->next;
    }

    // Return pointer to first (not last) element.
    return head;
}

---

If you prefer sharing student instances between the two lists, you can use

copy->student = current->student;

instead of

copy->student = new Student(*current->student);

Answer 2

This is an excellent question since you've done the bulk of the work yourself, far better than most "please do my homework for me" questions.

A couple of points.

First, what happens if you pass in an empty list? You probably want to catch that up front and just return an empty list to the caller.

Second, you only allocate the first node in the copy list, you need to do one per node in the original list.

Something like (pseudo-code (but C++-like) for homework, sorry):

# Detect empty list early.

if current == NULL:
    return NULL;

# Do first node as special case, maintain pointer to last element
# for appending, and start with second original node.

copy = new node()
last = copy

copy->payload = current->payload
current = current->next

# While more nodes to copy.

while current != NULL:
    # Create a new node, tracking last.

    last->next = new node()
    last = last->next

    # Transfer payload and advance pointer in original list.

    last->payload = current->payload
    current = current->next

# Need to terminate new list and return address of its first node

last->next = NULL
return copy

And, while you're correct that you shouldn't return a pointer to a local stack variable, that's not what you're doing. The variable you're returning points to heap-allocated memory, which will survive function exit.