the free list

When you call free() on a block, the allocator does not hand that memory back to the operating system right away — that would be slow, and you will probably ask for memory again soon. Instead it keeps the block and remembers it is available, so the next malloc can reuse it instantly. The free list is the simplest way an allocator keeps that memory: a linked list of the blocks that are currently free and ready to be handed out again.

Here is the clever part. The allocator does not need any extra storage to build this list, because the free blocks themselves are empty — nobody is using their contents. So the allocator stores the next pointer of the linked list inside the free block's own memory. Each free block holds, in its first few bytes, the address of the next free block; together they chain into a list. When you call malloc, the allocator walks this chain looking for a block big enough to satisfy your request, unlinks it from the list, and returns it to you. When you call free, it links your block back onto the list. The search strategy has names: first-fit takes the first block large enough; best-fit scans for the smallest block that still fits, to waste less; these are trade-offs between speed and fragmentation.

This is the conceptual core of a simple allocator, and real allocators elaborate on it heavily — they keep many free lists separated by size class so the search is fast, they keep headers describing each block, and they coalesce adjacent free blocks. But the picture to hold in your head is: free memory is not gone, it is parked on a list, threaded through the free blocks themselves, waiting to be reused. This is also why a heap buffer overflow that writes past a freed block can corrupt the allocator: it may overwrite the next pointer stored inside a free block, breaking the chain.