Deep copy queue recursively C++ (Implemented using a doubly linked list)

Question

I'm building a queue using a doubly linked list. I want my deep copy constructor to recursively deep copy the entire queue however I get a segmentation fault when I do the following:

// Recursive helper method for deep copy constructor
void queue::copyAllNodes(Node* og, Node *cpy) {
    if(og == nullptr) back = og;
    else {
        cpy->previous = og->previous;
        cpy->data = og->data;
        cpy->next = og->next;
        copyAllNodes(og->next, cpy->next);
    }
}

my constructor has another helper function that allows me to pass in the original and the copy node i want to copy.

Answer 1

First, understand you're not actually copying anything here. You're just enumerating by recursion and assigning pointers. At best that is a shallow copy; in reality your algorithm is completely broken. There are ways to copy a linked list recursively, including bidirectional linked lists. Whether it is wise to do so is another story.

---

Unidirectional List

Before getting into the subject of a bidirectional linked list, consider the base case of a unidirectional list. Suppose you have a linked list with nodes like this:

template<class T>
struct Node
{
    T data;
    Node *next;

    Node(T dat, Node *nxt = nullptr)
        : data(std::move(dat))
        , next(nxt)
    {
    }
};

Now suppose you want to make a deep copy of this recursively. In its most simple form the algorithm for a recursive copy would be:

Node *copyDeep(const Node *p)
{
    Node *res = nullptr;
    if (p)
        res = new Node(p->data, copyDeep(p->next));
    return res;
}

---

Bidirectional List

Introducing a double-linked node (both next and prev members) makes this a bit more challenging, but not by much. First the node has to be modified to include the new member:

struct Node
{
    T data;
    Node *next;
    Node *prev;

    Node(T dat, Node *nxt = nullptr)
        : data(std::move(dat))
        , next(nxt)
        , prev(nullptr)
    {
    }
};

With that, copyDeep can be modified to remember the added node to be used as an added argument to the recursed call. One way of doing that is:

Node *copyDeep(Node *p, Node *prev = nullptr)
{
    if (p)
    {
        Node *res = new Node(p->data);
        res->prev = prev
        res->next = copyDeep(p->next, res);
        return res;
    }
    return nullptr;
}

---

In both cases it is easier, faster, and less error prone (including stack overflows) to do this iteratively. In answer to your question, yes you can recursively copy a linked list. Whether it's a good idea to do so I leave to you.