2-d Linked List copy constructor using recursion

Question

I am trying to make a 2-d singly linked list where each node has a right pointer and a below pointer. I've had a lot of troubles implementing the copy constructor since I am pretty sure recursion is the way to go, and I am pretty bad at recursion. Do I need to change anything that you see, or does it look ok?

Here is the declaration in the header:

typedef int elementType;
struct node;
typedef node* nodePtr;
struct node
{
    elementType elt;
    nodePtr right = NULL;
    nodePtr below = NULL;
};

class LinkedList
{
protected:
    nodePtr head, tail;
    int size;
public:
    LinkedList();
    LinkedList(const LinkedList &list); // copy constructor

    void recursiveCreate(nodePtr ptr);
}

This is in my cpp file

LinkedList::LinkedList(const LinkedList &list)
{
    nodePtr current = NULL;

    if (list.head == 0)
        head == 0;

    else
    {
        current = list.head;
        recursiveCreate(current);       
    }
}

void LinkedList::recursiveCreate(nodePtr ptr)
{
    nodePtr n = new node; //create new node
    n->elt = ptr->elt;      //copy value into that new node
    n->right = ptr->right;  //move right n pointer
    n->below = n->below;    //move right below pointer
    recursiveCreate(ptr->right);  //call on right node
    recursiveCreate(ptr->below);  //call on below node
}

score 1 · Accepted Answer · answered Mar 27 '17 at 22:34

The up front big thing: This is a binary tree, not a linked list. Calling it a linked list just leads to confusion.

On topic, recursion is not the way to go for a linked list. For a tree it could be. But what you have does not work for a couple reasons.

1) There is no terminating condition. The recursion will plow into a NULL pointer and do bad things. First off in recursiveCreate you want to exit if nodePtr is NULL.

2) You're setting the current node to point at the wrong stuff. For example,

n->right = ptr->right;

has the node pointing at a node in the wrong list. That's an almost certain bad end. You want to point at the node created by recursiveCreate.

Let's take a look at what this would have to look like:

nodePtr LinkedList::recursiveCreate(nodePtr ptr)
{
    if (ptr == nullptr) 
    {
        return nullptr; // source tree stops here
    }
    nodePtr n = new node; //create new node
    n->elt = ptr->elt;      //copy value into that new node
    n->right = recursiveCreate(ptr->right);  //call on right node
    n->below = recursiveCreate(ptr->below);  //call on below node
    return n;
}

and

LinkedList::LinkedList(const LinkedList &list)
{
    nodePtr current = nullptr;

    if (list.head == nullptr) // NAG!!! For Crom's sake! 0 is not a pointer!
        head == nullptr;      // Use nullptr and get type checking working for you.

    else
    {
        head = recursiveCreate(list.head);       
    }
}

Special bonus operator

LinkedList & operator=(LinkedList list) // pass by reference. Copy constructor copies 
                                        // for you
{
    std::swap(head, list.head); // steal head from copy and give copy the empty   
    return *this; // all done.
}

2-d Linked List copy constructor using recursion

1 Answers1