C++ Linked List Memory Management

Question

I'm attempting to craft my own basic singly linked list in C++ as a learning exercise, and I'm encountering some difficulty in the memory management department. As it stands I have...

A 'Node' class:

class Node
{
public:
    char *value;
    Node *next;
    Node();
    ~Node();
};

Node::Node()
{
}

Node::~Node()
{
    delete[] value;
}

And then my list (I've omitted certain method calls for brevity):

class LinkedList
{
private:

    Node *head;

public:

    LinkedList();
    ~LinkedList();
    void Add(char **x);

};

LinkedList::LinkedList()
{
    head = 0;
}

LinkedList::~LinkedList()
{
    Node *temp;
    Node *current = head;

    while(current)
    {
     temp = current;
     current = current->next;
     delete temp;
    }
}

void LinkedList::Add(char **x)
{
    Node *nodeToAdd = new Node();
    nodeToAdd->value = *x;
    nodeToAdd->next = NULL;

    Node *current = head;

    if(!head)
    {
     head = nodeToAdd;
     return;
    }

    while(current->next)
    {
     current = current->next;
    }

    current->next = nodeToAdd;
}

I'm attempting to use this code as follows (again I've omitted things for brevity):

int main()
{
    LinkedList *list = new LinkedList();

    char *alpha = "alpha";
    char *beta = "beta";
    char *charlie = "charlie";
    char *delta = "delta";
    char *echo = "echo";

    list->Add(&alpha);
    list->Add(&beta);
    list->Add(&charlie);
    list->Add(&delta);
    list->Add(&echo);

    delete list;

}

The last call in main to delete the list produces an error:

Debug Assertion Failed! Expression: _BLOCK_TYPE_IS_VALID(pHead->nBlockUse)

What am I doing wrong here?

Answer 1

The data pointed to by the various Node::value aren't dynamically allocated, so you shouldn't delete them. Applying the concept of "ownership", nodes should either make their own copies of data, which they own and can delete, or nodes don't own data, so they shouldn't be responsible for deleting it.

You can also implement multiple ownership using reference counting, like Objective-C does (see Objective-C Memory Management Rules for more info) but you have to be careful to avoid ownership cycles. You often find some type of reference counting in third-party smart pointers, such as Boost's smart_ptr library. Since you're doing this for the learning experience, it may make more sense to roll your own than use a library. Of course, you could also use a library for now, letting you focus on whatever you're trying to learn.

One day a student came to Moon and said: “I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons.”

Moon patiently told the student the following story:

“One day a student came to Moon and said: ‘I understand how to make a better garbage collector...

Answer 2

you are trying to release the memory which is not allocated on heap.

char *alpha = "alpha"; --- not allocated on heap

calling delete[]in Node destructor would lead to heap corruption.

Some points:

1) initialize pointers properly in the constructor:

Node::Node():value(NULL),next(NULL)
{
}

2) Take a ownership of value.

• Allocate the memory on heap and copy the contents

Answer 3

value and next in Node class doesn't have memory allocated. You should allocate memory in Node's constructor.

Answer 4

The problem is that you're assuming that you can delete the data inside node, but you're passing in pointers to string literals instead, which you can't delete.

If you're assuming that the Node object controls the lifetime of the data inside it, your Node constructor or the Add function in LinkedList will have to make a copy of the data that it is being passed.

Answer 5

In your destructor, you are trying to array delete (delete [ ]) a static string. You have change your Add function to reserve the string and copy it first. See the code below.

However, if I were you and fairly new to memory management, I'd really use something like CString instead of a raw "char *" as it's much easier to deal with.

void LinkedList::Add(const char *x)
{
    Node *nodeToAdd = new Node();

    int len=strlen(x);
    nodeToAdd->value = new char [len+1];    // room for string + terminating 0
    strcpy(nodeToAdd->value,x);

    nodeToAdd->next = NULL;

    Node *current = head;

    if(!head)
    {
        head = nodeToAdd;
        return;
    }

    while(current->next)
    {
        current = current->next;
    }

    current->next = nodeToAdd;
}

Answer 6

You shouldn't release a pointer use delete[]/delete if it's not created by new operator. There are some actions under the hood for the delete[] operation, like releasing/reclaiming marked memory from a managed pool. Since your pointer doesn't belong to these stuff, there will be a problem. IMHO, the underlying delete[] code is the _BLOCK_TYPE_IS_VALID(pHead->nBlockUse) stuff.