C++ Deep Copying Linked List

Question

First of all, this is part of an assignment I'm currently trying to figure out. I'm trying to create a copy constructor that deep copies a given LinkedList. I have coded the LinkedList methods already.

Here's the necessary parts of the LinkedList.h file.

LinkedList.h
private:
    struct node {
        Val data;
        node* next = nullptr;

    };

    typedef struct node* nodePtr;


    nodePtr head = nullptr;
    nodePtr current = nullptr;
    nodePtr temp = nullptr;
};

The parameters are given: "LinkedList::LinkedList(const LinkedList & ll)" ll is the linked list to be copied. I first tested if there is a head in the linked list, if not then that means the linked list is empty. Then I copied the head from the old list to the new list. I then set the new current to the head in preparation for the while loop. Inside the while loop, I am copying the data of the current node as well as the pointer to the next node. At the end I set the next pointer to nullptr to signify the end of the new list.

LinkedList.cpp

LinkedList::LinkedList(const LinkedList & ll){
    if (ll.head == nullptr) {
        return;
    }
    head = ll.head;
    current = head;


    while (ll.current->next != nullptr) {
        current->data = ll.current->data;
        current->next = ll.current->next;
    }
    current->next = nullptr;
}

I'm not sure if this is deep copying or not. I also know that ll.current's starting position is not at the head. I tried ll.current = ll.head. However, since it is given that this function is const. I can't set it like that.

There is also another function given: LinkedList & LinkedList::operator=(const LinkedList & ll) { } That I suspect may be needed. I'm hoping it optional that I use this.

Write the copy constructor and destructor first. The assignment operator is simple once you implement those functions. Also, your copy constructor is instantly wrong if ll.head is nullptr. The reason is that you didn't initialize any of the members -- you just return. — PaulMcKenzie
That's not deep copying. Deep Copying involves allocating memory to members before copying value in them. — sameerkn
Also you are currently overriding the value in current->data and current->next without changing where current points to. — Simon Kraemer

user2205930 user2205930 · Accepted Answer · 2016-11-25T09:36:12

You need to allocate new memory or new list elements as you add them, change your code to do the following:

// LinkedList.cpp

LinkedList::LinkedList(const LinkedList & ll)
{
    if (ll.head == nullptr)
        return;

    // Create a temp variable since ll.current doesn't move/change.
    node* tmp = ll.head;

    // Allocate a new node in memory.
    head = new node;
    // Copy over the value.
    head->data = tmp->data;
    // Set the 'next' value to null (the loop will fill this in). 
    head->next = nullptr;
    // Point 'current' to 'head'.
    current = head;
    
    // Move to next item in ll's list.
    tmp = tmp->next;

    while (tmp != nullptr)
    {
        // Allocate new memory for a new 'node'.
        current->next = new node;
        // Point to this new 'node'.
        current = current->next;
        // Copy over the data.
        current->data = tmp->data;
        // By default set the 'next' to null.
        current->next = nullptr;
        // Move along ll's list.
        tmp = tmp->next;
    }
}

Also, in your class get rid of typedef node* nodePtr. There is no need for that, it's cleaner to simply use node* for head, current and temp. Lastly, don't forget in your class' destructor to clear out dynamically allocated memory:

LinkedList::~LinkedList()
{
    current = head;

    while(current != nullptr)
    {
        current = current->next;
        delete head;
        head = current;
    }
}

C++ Deep Copying Linked List

2 Answers