t3hdaniel t3hdaniel - 10 days ago 7
C++ Question

C++ Deep Copying Linked List

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.

Answer

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->value = tmp->value;
    // 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;
    }
}
Comments