C++ How do I create a copy of a Linked List as a class object?

Question

I'm trying to make a copy of a linked List using the duplicate() method of the LinkedList class. I've been scratching my head all day about how to make this method work.

The duplicate method needs to make an exact copy of the list, returning a pointer to the new list. I want to be able to call LinkedList methods on the new list. Should I be returning a LinkedList pointer? or a Node pointer? I feel like I'm totally missing something easy here.

How would I even store the location of the new head node in the LinkedList pointer?

//LinkedList.h
#pragma once

#include<string>

using namespace std;

struct Node {
    string nodeData;
    Node* nextNode;
};

class LinkedList {
public:
    LinkedList();

    ~LinkedList();

    bool insert(string givenData);

    bool remove(string givenData);

    void print() const;

    int count() const;

    int find(string givenData) const;

    bool removeAll();

    LinkedList* duplicate() const;

private:
    Node* head;
};


//LinkedList.cpp duplicate() method
LinkedList* LinkedList::duplicate() const {
    LinkedList* newList;
    Node* newHeadNode = new Node;
    Node* newNode = new Node;

    newHeadNode->nodeData = head->nodeData;
    newHeadNode->nextNode = head->nextNode;

    Node* currentNode = head->nextNode;
    Node* previousNode = head;

    while ((currentNode) && (newNode->nodeData > currentNode->nodeData)) {
        previousNode = currentNode;
        currentNode = currentNode->nextNode;

        newNode->nextNode = previousNode->nextNode;
        previousNode->nextNode = newNode;
    }
}

score 3 · Answer 1 · answered May 27 '17 at 00:45

3

You are confusing the role of pointers and data, to begin.

All nodes have "links" to the next node. If you want to duplicate a list, you want to create copies of each node, and connect them. This means that you should not connect the new nodes to the old ones, but just the new nodes between them.

newHeadNode->nextNode = head->nextNode; is thus wrong.

Also, your class has an insert method, which you can use, and probably already correctly create a node and set the old tail node pointer.

Your function body should look like

LinkedList* LinkedList::duplicate() const {
    // create a new list
    LinkedList* newList = new LinkedList();
    // start from the first node of the old list
    currnode = this->head;

    // until currnode is valid
    while(currnode){
        // insert the data in the new list (the new list will deal with the pointers)
        newList->insert(currnode->data);
        // go to the next node of the old list
        currnode = currnode->nextNode;
    }

    return newList;

}

answered May 27 '17 at 00:45

user1620443

784
3
14

Thanks so much! That seems to be working. I'd like to avoid calling the insert() function for memory efficiency. My professor asked us to avoid it if we can. This is where I got stuck! – Cody Potter May 27 '17 at 00:54
@CodyPotter Your professor is advocating [discarding the D from DRY](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself). From a software engineering standpoint that's a bad call. Writing duplicate and close functions is kind of silly in C++. Instead, take advantage of copy constructors and [The Rule of Three](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three), something the `LinkedList` class is currently violating the hell out of. – user4581301 May 27 '17 at 01:21
@user4581301 I appreciate the feedback. I'm certain my professor is aware of this. He just wants us to get experience working with pointers. He mentioned that calling the insert function to copy nodes in a loop resulted in a factorial amount of steps for the program. I'm having trouble understanding how doing it without the insert() function would be any more efficient. – Cody Potter May 27 '17 at 01:42
1

@CodyPotter Haven't seen the insert function, but likely it is seek to end, place node. So for every node you add you have to seek further to add the next. With an add loop you can remember where you placed the last node and not have to seek. This is what you did with `previousNode`. – user4581301 May 27 '17 at 03:32
@user4581301: it is clear that `insert()` has to start over from the beginning every time it is called, since `LinkedList` only has a `head` member and no `tail` member. If `LinkedList` is updated to include a `tail` member, or if `insert()` is updated to take an optional sibling `Node*` as input, then the factorial effect can be eliminated. – Remy Lebeau May 27 '17 at 03:36

Remy Lebeau · Accepted Answer · 2017-05-27T03:59:22.873

Your duplicate() code has several logic issues in it.

The code can be simplified to the following:

LinkedList::LinkedList()
    : head(NULL)
{
}

LinkedList* LinkedList::duplicate() const
{
    LinkedList* newList = new LinkedList;

    Node* currentNode = head;
    Node* previousNode = NULL;

    while (currentNode)
    {
        Node* newNode = new Node;
        newNode->nodeData = currentNode->nodeData;
        newNode->nextNode = NULL;

        if (!newList->head)
            newList->head = newNode;

        if (previousNode)
            previousNode->nextNode = newNode;
        previousNode = newNode;

        currentNode = currentNode->nextNode;
    }

    return newList;
}

That being said, if you add a Node *tail member to LinkedList, then duplicate() can be implemented in terms of insert(), which itself can be greatly simplified:

LinkedList::LinkedList()
    : head(NULL), tail(NULL)
{
}

bool LinkedList::insert(string givenData)
{
    Node* newNode = new Node;
    newNode->nodeData = givenData;
    newNode->nextNode = NULL;

    if (!head)
        head = newNode;

    if (tail)
        tail->nextNode = newNode;
    tail = newNode;

    return true;
}

LinkedList* LinkedList::duplicate() const
{
    LinkedList* newList = new LinkedList;

    Node* currentNode = head;
    while (currentNode)
    {
        newList->insert(currentNode->nodeData);
        currentNode = currentNode->nextNode;
    }

    return newList;
}

If adding tail is not an option, then at least consider adding an optional Node* parameter to insert() instead:

Node* LinkedList::insert(string givenData, Node *after)
{
    Node* newNode = new Node;
    newNode->nodeData = givenData;
    newNode->nextNode = NULL;

    if (!head) {
        head = newNode;
    }
    else {
        if (!after) {
            after = head;
            while (after->nextNode) {
                after = after->nextNode;
            }
        }
        newNode->nextNode = after->nextNode;
        after->nextNode = newNode;
    }

    return newNode;
}

LinkedList* LinkedList::duplicate() const
{
    LinkedList* newList = new LinkedList;

    Node* currentNode = head;
    Node *newNode = NULL;

    while (currentNode)
    {
        newNode = newList->insert(currentNode->nodeData, newNode);
        currentNode = currentNode->nextNode;
    }

    return newList;
}

Mr Awesome8 · Answer 3 · 2017-05-27T00:46:28.447

0

If you're trying to do a deep copy (assignment operator) of the linked list, consider using recursion.

Compare this against a passed in reference of the second list. If they are not the same, clear the list. If the passed in list has a head pointer, call the recursive method. This method would take a node* n. Check if it exits, if it does, call itself with n's next pointer. Then it should add n's data to the head of the list. Because this is recursive, the AddHead calls would wait on the stack until the recursion is done, and then get called in a reversed order, resulting in the correct ordering of the list.

If you are just doing a copy constructor you can simply set *this equal to the passed in list. E.g.

LinkedList (const LinkedList& other) {
    count = 0;
    head = nullptr;
    *this = other;
}

edited May 27 '17 at 00:46

answered May 27 '17 at 00:38

Mr Awesome8

281
4
10

I haven't learned recursion yet, so I'm afraid that's a bit above my head. I'm guessing I just need a shallow copy. I'm not too familiar with the concept. What do you mean by setting *this equal to the passed in list? – Cody Potter May 27 '17 at 00:46
Anything you can use recursion for can also be used with loops. Use a `while` loop instead if you are not comfortable with the concept. – Mr Awesome8 May 27 '17 at 00:48

score 0 · Answer 4 · answered May 27 '17 at 04:37

Looks like Remy Lebeau got in here before I could get back to this. Only thing I can add is a slightly tighter, and a bit more confusing, way to write duplicate. It's a good example of how an extra level of indirection can save a bit of work, so I'll drop it here anyway.

//LinkedList.cpp duplicate() method
LinkedList* LinkedList::duplicate() const {
    // make a new empty list
    LinkedList* newList = new LinkedList;

    //get the first node from the list to be duplicated
    Node * getp = head;

    //Here be where we get a bit weird. Rather than getting a pointer to the
    //head node like we did with the source list, we are going to get a pointer
    //to the head itself! Crazy, right?
    //But if you think about it, it means we can use head just like any other
    //pointer to a node (which it is) without having to write any special code
    //specifically to handle the head or having to carry around previousNode
    //pointers and other overhead
    Node ** putpp = &newList->head;

    //Loop through the source list
    while (getp != NULL)
    {
        *putpp = new Node; //make a new node and insert it into the list
                           //wherever putpp is currently pointing, head or
                           //any node's next
        (*putpp)->nodeData = getp->nodeData; // copy the source node's data
        putpp = &(*putpp)->nextNode; // point at the new node's next so we can
                                      // add the next new node
        getp = getp->nextNode; // point at the next source node
    }
    *putpp = NULL; // null the last next pointer to end the list
   return newList;
}

C++ How do I create a copy of a Linked List as a class object?

4 Answers4