How to recognize if object is on the stack or heap memory

Question

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?

Answer 1

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).