I have recently received a university assignment for my Data Structures course, which requires me to create a doubly linked list in C++.
While working on my doubly linked list, I needed to implement various functionalities, but one method that particularly caught my attention is named "clear()". This method is responsible for clearing all elements within the doubly linked list:
void clear(Node* head_ptr)
{
Node* previous_ptr = nullptr;
while(head_ptr != nullptr)
{
previous_ptr = head_ptr; // Store previous node.
head_ptr = head_ptr->next;
delete previous_ptr;
}
};
The method is quite straightforward; it simply iterates through all elements and deallocates the memory for each Node. I then invoke this method within my destructor as follows:
~List()
{
clear_list(m_head_ptr);
};
Then I got to thinking. This method of freeing memory is fine if my node elements are on the heap, like this:
int main()
{
List list;
Node* node_1 = new Node(3, nullptr); // The tail node.
Node* node_2 = new Node(1, node_1);
Node* node_3 = new Node(5, node_2);
Node* node_4 = new Node(7, node_3); // The head node.
list.add(node_1);
list.add(node_2);
list.add(node_3);
list.add(node_4);
// Then do some stuff with the list...
} // The list goes out of scope and the destructor is called...
But, this breaks as soon as I create the Nodes on the stack and pass a pointer to stack objects, like this:
int main()
{
List list;
Node* node_1(3, nullptr); // The tail node.
Node* node_2(1, node_1);
Node* node_3(5, node_2);
Node* node_4(7, node_3); // The head node.
list.add(&node_1);
list.add(&node_2);
list.add(&node_3);
list.add(&node_4);
// Then do some stuff with the list...
} // The list goes out of scope and the destructor is called and the program crashes because it attempts to free stack objects...
The reason is because I am attempting to free stack objects which is not a good idea. Naturally, we wouldn't normally use stack-based Nodes because we typically want our Node data to persist beyond the scope in which they are created. Nevertheless, this leads me to my question:
How do I counter this? Is there a way to check if some Node in memory is on the heap or the stack in my function and then free it accordingly? Or, is there a better way to approach the problem?
The easiest and most effective solution is usually for the list to manage allocation of nodes itself. The user shouldn't even need to be aware that a node type exists, not to mention allocating them and such.
So, to the user, the equivalent of what you show in the question would be something like this:
List list;
list.add_head(1);
list.add_head(3);
list.add_head(5);
list.add_head(7);
You'd typically also have an add_tail to add items to the end of the list. Each add (head or tail) should normally return an abstract iterator type (which will probably be a wrapper around a pointer to a node), so you can do something like:
auto pos = list.add_head(7);
list.add_tail(5);
list.add_after(pos, 3);
...which would add 7 at the beginning, 5 at the end, and 3 just after the 7.
This way, the list itself allocates all the nodes, and knows how to dispose of them. You might go a step further, and have it delegate allocation and disposal to an Allocator class. That can certainly be useful, but may be a bit beyond what makes sense for basically an exercise (in practical use, you probably want to use a container from the standard library--and while the standard library does provide both singly- and doubly-linked lists, they're rarely useful).