Q:

Can a data structure implementation know if it is/isn't on the heap?

Consider a main file, and another file that implements a data structure (say: linked list).
The caller of the linked list can either put objects on the linked list on the stack or on the heap, and I assume that is the responsibility of the caller.
So when implementing the linked list, how does it know whether or not it's on the heap?  Consider a typical "method" that removes an node  from the list.  How does the linked list know whether or not it ought to free that memory?  From my understanding, freeing something on the stack causes undefined behavior.
Because this is part of a class project, I'm unable to pass something (isOnHeap) to indicate whether or not the caller has put the memory on the heap (clarification: unable as in our implementation does not allow this), so I'm assuming there may be a common solution to this problem, especially considering how common a case it'd be. Note that the linked list implementation must handle freeing of its own memory (assumed this is given since its implementation is hidden from the caller).

A:

Here is simple is_on_stack(addr) function : 
int *stack_start = nullptr;

bool is_on_stack(void* ptr) {
  int stack_probe;  
  if( stack_start < &stack_probe  )
    return stack_start < ptr && ptr < &stack_probe; // stack grows upwards;
  else 
    return &stack_probe < ptr && ptr < stack_start; // stack grows downwards;
}

int main() {
  int stack_probe = 0;
  stack_start = &stack_probe;

  int dummy;

  bool r1 = is_on_stack(&dummy); // shall be true

  int* heap_thing = (int*)malloc(sizeof(int));

  bool r2 = is_on_stack(heap_thing); // shall be false         
}

Key point here is these lines at the beginning of  main() function:
  int stack_probe = 0;
  stack_start = &stack_probe;

