Destructor for a doubly-linked list that points to its value

Question

Suppose I have a doubly-linked list defined by the class

    class list
    {
        /*...*/

    private:
        struct node
        {
           node* prev;
           node* next;
           int* value;
        }

        node* first; //NULL if none
        node* last; //NULL if none

        /*...*/
    }

If I wanted to make a destructor for this list do I have to explicitly delete the value?

list::~list()
{
    node* move = first;
    while(first)
    {
        first = move->next;
        delete move;
        move = first;
    }
}

Would the above work to ensure that no memory is leaked? Or do I have to do:

list::~list()
{
    node* move = first;
    while(first)
    {
        first = move->next;
        delete move->value;
        delete move->prev;
        delete move;
        move = first;
    }
}

I'm confused as to how I can make sure that no memory is leaked in this case. How do I deal with the pointers in the nodes specifically? If I delete move does it automatically take care of these?

Solution 1

You need to pair each new with exactly one delete. That is, you probably don't want to delete prev (this node already was deleted) but you want to delete value. Well, I'd embed the value into the object and not point to it:

struct node
{
     node* prev;
     node* next;
     int   value;
};

If the value absolutely needs to be a pointer, I'd use a std::unique_ptr<int> (or, if you need to use C++ 2003, a std::auto_ptr<int>).

Solution 2

For each successful new expression, call delete exactly once on that object.

For each successful new[] expression, call delete[] exactly once on that object.

That means that neither of your cleanup functions are OK:

• The first function forgets to delete the value, which means a memory leak.

• The second function, by deleting both move and move->prev at each node in the list, risks deleting most nodes twice, which is Undefined Behavior.

To avoid the memory leak for the first function, simply store the integer directly instead of allocating it dynamically.

Solution 3

Whether you have to delete the memory pointer by the value member - only you can know. It is a question of memory ownership, a question of your design. If the list owns the data memory pointed by the value members, then you have to delete it in the list destructor (i.e. when the list dies, the data it owned dies with it).

If the list does not own the value memory, then you are not supposed to delete it. Again, only you can answer the question of whether your list is supposed to own the value memory. It is a matter of your intent.

Now, as for the memory occupied by node objects, it is obviously owned by the list, so it has to be carefully deallocated in the destructor. The first version of your destcructor is close to being correct (the second makes no sense at all), except that it written in a slightly obfuscated fashion. This should be sufficient

list::~list()
{
  while (first)
  {
    node *move = first;
    first = first->next;
    delete move;
  }
}

(Again, if you have to delete value, then delete move->value should be added to your cycle before delete move.)

P.S. Once you get this, you might want to look into various smart pointer classes, which allow you to explicitly express memory ownership relationsips, thus making them known to the compiler. When used properly, they will make memory management almost automatic.

Comments

[Karthik T]

You should delete value only if you do new, if the user of the class does the allocation, the user should do the deletion