CODEWITHSUNDEEP
c++c++11linked-listdeep-copy
helloworld922
helloworld922

Reputation: 10939

Creating a deep copy of a doubly-linked list node

I have my node defined something like:

class LLNode
{
public:
    std::shared_ptr<LLNode> prev;
    std::shared_ptr<LLNode> next;
    std::shared_ptr<int> data;
    LLNode(void)
    : prev(std::shared_ptr<LLNode>(nullptr)),
    next(std::shared_ptr<LLNode>(nullptr)),
    data(std::shared_ptr<int>(nullptr))
    {
    }

    LLNode(const LLNode &node)
    : prev(std::shared_ptr<LLNode>(node.prev == nullptr?nullptr:new LLNode(node.prev))),
    next(std::shared_ptr<LLNode>(node.next == nullptr?nullptr:new LLNode(node.next))),
    data(std::shared_ptr<int>(new int(node.data)))
    {
    }
};

However, if I have a node which is linked to another node (which obviously will often be the case), copying node A will instantiate a copy of the next node B, which in turn will try to instantiate a copy of node A, which will try to copy node B, etc. etc. until there's a stackoverflow or memory error. This could be fixed by only instantiating a new copy of next (or prev), but then nothing linked previously (or next) to this node will be copied.

Is there a good way to copy a doubly linked list node?

Upvotes: 2

Views: 1793

Answers (2)

wilx
wilx

Reputation: 18238

You are doing the mistake that you are trying to copy the whole chain/list from a single node. That does not make that much sense to do in copy ctor of a list node. Make the copy ctor just copy the members' values, do not recurse. Copying the whole chain/list is the job for a LinkedList class.

Upvotes: 4

Benjamin Lindley
Benjamin Lindley

Reputation: 103733

Just set next and prev to null, regardless of the next and prev values of the node being copied. Write a separate function that copies the node and all it's children, which would be used to copy the whole list.

Upvotes: 0

Related Questions