0

I am required to create a recursive worker function to create a deep copy of a singly linked list in C++, containing key-item pairs. It passes tests when I use the deepdelete deconstructor, but when I attempt to test by copying using a deep copy constructor, I get errors in the lookup() function.

The below is what I have so far:

Deconstructor:

Dictionary::~Dictionary()
{
    deepDelete(head);
}

Copy constructor:

Dictionary::Dictionary(const Dictionary & org)
{
    this->head = deepCopy(org.head);
}

Deep delete recursive worker function:

 void Dictionary::deepDelete(Node* current)
 {
     if (current == NULL)
     {
         return;
     }
     else
     {
        deepDelete(current->next);
        delete current;
     }
 }

Copy constructor recursive worker function:

Dictionary::Node* Dictionary::deepCopy(Node* org)
{ 
    if (org == NULL)
    {
        return nullptr;
    }
    else
    {
        Node* headc = new Node;
        headc->k = org->k;
        headc->i = org->i;

        if (org->next != NULL)
        {
            //I have tried both of these, which produce the same error
            headc->next = org->next;
            //headc->next = deepCopy(org->next);
        }       
        return headc;
    }
    return nullptr;
}

Lookup function (Error here):

Dictionary::Item* Dictionary::lookup(Key k)
{
    Node *temp = head;

    while (temp != NULL)
    {
        //Exception thrown: read access violation.
        temp was 0x10.
        if (temp->k == k)
        {
            return &temp->i;
        }
        temp = temp->next;
    }
    return nullptr;
}

Insert function:

bool Dictionary::insert(Key k, Item i)
{
    if (lookup(k) == nullptr)
    {
        Node *temp = new Node;
        temp->k = k;
        temp->i = i;
        temp->next = NULL;
        if (head == nullptr)
        {
            head = temp;
            tail = temp;
            temp = NULL;
        }
        else
        {
            tail->next = temp;
            tail = temp;
        }
        return true;
    }
    else
    {
        return false;
    }
}

.h file (As requested:

#pragma once
#include <string>
#include <string.h>
using namespace std;
class Dictionary
{
public:
    using Key = std::string;
    using Item = std::string;
    Dictionary()
    {
        head = nullptr;
        tail = nullptr;
    };
    ~Dictionary();
    Dictionary(const Dictionary &);
    Item* lookup(Key);
    bool insert(Key, Item);
    bool remove(Key);
private:
    struct Node
    {
        Key k;
        Item i;
        Node *next;
    };
    Node* head;
    Node* tail;
    static void deepDelete(Node*);
    static Node* deepCopy(Node*);
    static Item* lookupRec(Key, Node*&);
    static bool insertRec(Key, Item, Node*&);
    static bool removeRec(Key, Node*&);
};

The deep delete and copy functions must be recursive and must be deep. I have to use a singly linked list and cannot use std::list. I am fairly sure the problem is in deepcopy but I cannot figure it out for the life of me.

Philip Nelson
  • 1,027
  • 12
  • 28
Armakar
  • 11
  • 3
  • What does your `Node` look like? – JohnFilleau Feb 25 '20 at 23:01
  • I've updated the code with my .h file. It's just a singly linked list with key/value pairs – Armakar Feb 25 '20 at 23:02
  • Read [ask]. Exactly what errors are you getting? Have you tried debugging this yet? – jwdonahue Feb 25 '20 at 23:05
  • Recommendation: Separate the linked list from the user of the linked list. It's almost always much easier to validate the linked list on its own and then have the user of the linked list contain a linked list rather than be a linked list. – user4581301 Feb 25 '20 at 23:05
  • The error is in the lookup() function, it's commented. (Exception thrown: read access violation. temp was 0x10.) I have tried debugging this and stepping through. What's throwing me off is that the error is in the lookup function but is only triggered when I use the copy constructor, so I can't figure it out. – Armakar Feb 25 '20 at 23:06
  • 1
    A note on `deepDelete`. Recursively deleting a long linked list is a really easy way exhaust the program's Automatic storage. – user4581301 Feb 25 '20 at 23:06
  • Since you know that temp was the wrong value the next job is to figure out where it got set to the wrong value. The debugger is a excellent tool for this. Stop through likely point where you modify the list and see if you've missed a case. Or perhaps my above note is more than just a potential problem and temp is wrong because you've run off the end of the stack. – user4581301 Feb 25 '20 at 23:09
  • Sidenote: You can reduce the complexity of the `insert` method (and probably the removal methods) by abstracting away the differences between `head` and any other `next` pointer with a pointer to a pointer. [Example here](https://stackoverflow.com/a/59779376/4581301). – user4581301 Feb 25 '20 at 23:12
  • You have a copy constructor but no assignment operator. You should add one if for no better reason than completeness. See [the Rule of Three](https://en.cppreference.com/w/cpp/language/rule_of_three). Read up on Three's friends Five and Zero as well. Very helpful. – user4581301 Feb 25 '20 at 23:14
  • @user4581301 "*Recursively deleting a long linked list is a really easy way exhaust the program's Automatic storage*" - same with recursively copying a list, too. Linked lists are better handled using iterative loops instead of recursive loops. – Remy Lebeau Feb 25 '20 at 23:41
  • @RemyLebeau second time today you've caught me up on that. I thought I was tired and grumpy today. Clearly I'm more tired than grumpy. – user4581301 Feb 25 '20 at 23:43

1 Answers1

0

headc->next = deepCopy(org->next); is right, as you need deep copy. And you don’t need if (org->next != NULL), you check for NULL in the deepCopy itself. That condition seems to be the reason for the crash as headc->next of the last node was left uninitialized. But your copy constructor/deepCopy also misses one important thing: it leaves tail unassigned; that would crash the program in insert would it not crash earlier.

Also adding copy assignment, as pointed out in comments, is a good idea. It should probably be deepDelete followed by deepCopy.

numzero
  • 2,009
  • 6
  • 6