Thread: Writing a deconstructor for a linked list

Maybe...

Code:

LinkedListCollection::~LinkedListCollection() {
    intListElement *current= this->head_;
    intListElement *next1;
    while(current!=0){
        next1=current->next;
        delete current;
        current = next1;
    }
}

Also, it's called a destructor (or dtor), not a deconstructor.

I wouldn't directly use a loop in the destructor at all. Doing that will delete some objects more than once (since operator delete invokes destructors as well) and that is undefined behaviour.

Code:

LinkedListCollection::~LinkedListCollection()
{
    delete head_;
    delete next;
}

Since operator delete does nothing for a NULL pointer, this will effectively delete the list. All it requires is that head and next are pointers to objects created with operator new or NULL otherwise. And since operator delete invokes the destructor, this will recursively delete the whole list.

I don't quite understand why every element in your linked list has a "head". That implies a tree structure, not a simple linked list.

Originally Posted by sigur47

every node in my linked list does not have a head.I just add my nodes at the beginning of the linked list

If so, that doesn't change my point. It appears your design is not as clean as it might be.

And lack of cleanliness in a design tends to mean it is harder to get right, harder to debug, and harder to clean up.

Presumably LinkedListCollection has the head_ of type pointer-to-intListElement, and the intListElement type has the next pointer (and data). The full code hasn't been shown.

Based on the information you have provided, I wouldn't have a clue. All I have, from information you have given, is reason to question the design.

However, it appears you are using two types (LinkedListCollection and intListElement) to, collectively, represent a linked list - LinkedList collection contains the head, and intListElement manages links going down from the head.

Why can't that be done using a single class? Why doesn't intListElement have a destructor that, if invoked, deletes next? And, if it does, what does LinkedListCollection do that intListElement (with suitable renaming) could not?

Originally Posted by grumpy

I wouldn't directly use a loop in the destructor at all. Doing that will delete some objects more than once (since operator delete invokes destructors as well) and that is undefined behaviour.

Code:

LinkedListCollection::~LinkedListCollection()
{
    delete head_;
    delete next;
}

Since operator delete does nothing for a NULL pointer, this will effectively delete the list. All it requires is that head and next are pointers to objects created with operator new or NULL otherwise. And since operator delete invokes the destructor, this will recursively delete the whole list.

I don't quite understand why every element in your linked list has a "head". That implies a tree structure, not a simple linked list.

Whilst I very much always respect grumpy's advice, (probably more than just about anyone else's here in fact), I thoroughly despise using recursion to perform linked-list deletion.
**cough** "stack overflow"
"Tail-recursion elimination optimisation" I hear you say...
"Debug build" you'll hear me reply...

If you want my advice here, definitely use recursion for any problem that involves O(log n) deep recursive calls, or maybe even O(sqrt n).
BUT, don't use it for O(n) deep recursive calls!

You may want to double check the code posted because nothing in it suggests that every element in the linked-list has a head. There are two classes involved, LinkedListCollection and intListElement, not just one.
Edit: Oh you noticed that in a later post. Alright, I now have no idea where you are coming from. How is hk_mp5kpdw's corrected code any different to something the likes of std::list?

Originally Posted by iMalc

Whilst I very much always respect grumpy's advice, (probably more than just about anyone else's here in fact), I thoroughly despise using recursion to perform linked-list deletion.
**cough** "stack overflow"
"Tail-recursion elimination optimisation" I hear you say...
"Debug build" you'll hear me reply...

The tail recursion optimisation is often, in practice, performed by compilers even in the debug build ..... particularly by C++ compilers, because a lot of code (such as destructor calls) is recursive. It is a reasonably simple optimisation for a compiler, and also not something that can be readily detected in an IDE or debugger (you will always have the illusion of executing a line again and again if you step through).

Tail recursion aside, in a linked list, the linked list object is the master, and node objects should be a small internal implementation detail. Having the node destructor delete its successor is, IMO, the wrong approach. In fact, having the node be anything but a simple struct without any member functions is probably the wrong approach. All the work should be done in the actual linked list class.

Though I am not sure if I agree on that a node must be a struct and no more, deleting the next pointer in a node destructor seems silly. Why would deleting a node delete the next? It often happens that we must rearrange nodes, and insert and removes references, hence this makes no sense. A node is a separate object.

Yeah now you mention it, the other feeling I have about this is that you should never have to do more work to make less happen. Where the deletion is done recursively, if you want to delete a single item from the middle of the list you are forced to NULL the next pointer before deleting that node.
That to me, goes against the principles of C++ where you only pay for what you use.

At the same time, the simplicity and elegance of the recursive delete means it does have its place somewhere.