I have a logical explanation to this but anybody is free to correct me. Here is what I think.

As we know, the memory structure is a link list so each block of memory in a group of blocks is linked to each other.

When we call malloc() or calloc(), we pass the information of how much memory needs to be allocated like

 Ex: malloc(sizeof(int) * 100).

Internally the OS finds free blocks of memory (depending on what is the sizeof(int) in that OS) that can be used and links them to each other marking the start and end sentinels. The starting address of this link list is returned for the calling program to use.

When a free(p) is called, only the starting address needs to be known. Once this is provided, the link list is run through and memory is marked as free or deallocated. These blocks can now be used by the OS for other memory allocations.

A delete(p), of course, calls the destructor before doing this.

The OS will have its own safty measures so that a program does not iterate through this link list as this is hidden to the outside world.

This also explains the reason a defragmented system is faster in responding to memory allocations than a fragmented system as the OS has to probably search for a free block.