C ++ class RAI style for related nodes

Question

I play with linked lists as an exercise at the moment.

In the examples I'm looking at in Cracking The Coding Interview , there is no LinkedList (manager) class, only nodes, and you hang on the head of Node in your main function.

I was looking for C ++ implementations, but most of them seem to be more C-style than C ++, i.e. not object oriented. They use structs, no classes and have a static method to delete a list that you need to explicitly remember to call. I wanted to write a reasonable C ++ class class with resource initialization, with reasonable destructors to handle memory deallocation, and I wanted to use only the Node class (LinkedList class).

The only way I saw this work was to have the Node destructor delete the next Node, if there is one, but I read that this recursive delete is a bad idea, because you end up creating a column of the same length as linked list.

So, to summarize my question:

• When writing an object-oriented class to handle linked lists in C ++, should you have a LinkedList (manager) class that handles the removal of list nodes in its destructor?
• If not, how would you deal with the destruction of nodes?

Thanks!

Answer 1

When writing an object-oriented class to handle linked lists in C ++, should you have a LinkedList (manager) class that handles the removal of list nodes in its destructor?

No, the structure is determined by the relationships between nodes, so there is no need for a separate manager object. It is sometimes more convenient to have it, especially if you are creating a library such as STL and you want all containers to have a similar interface, but you can certainly implement a linked list with only the node type.

If not, how would you deal with the destruction of nodes?

One way to avoid recursion is to remove each of the node from the list before deleting, for example:

~node() { while (node * victim = next) { next = victim->next; victim->next = nullptr; delete victim; } }