CareerCup

malloc is a memory allocator which manages the memory use requested by user.
It reduces requesting new memory from OS by recycling the freed memory space. It uses Free List to keep track of the freed memory. When free(ptr) is called, the allocator looks at the header/footer of the memory block. The header of the memory block contains enough information (such as total bytes, status(freed/allocated), etc..) to remove it.

Coalescing the freed memory with its neighbor freed memory can optimize the memory use. It also reduces the external fragmentation.

Generally with the traditional memory managers some leading bytes (2 bytes) are allocated .Now when user call free(addr) it tries to do the addr-2 and get the size of the block .Then it just add this block to the available free list .Where in the free list it is added depends upon the memory manager(first fit , best fit and worst fit) also this free list needs not to be a single linked list generally a balanced tree .