Freelist

Freelist is the simplest data structure for tracking available blocks in a heap: a linked list in which each free block stores a pointer to the next free block. When memory is requested, the allocator traverses the list and returns the first block large enough to satisfy the request. When memory is freed, the block is inserted back into the list. The freelist is elegant in its simplicity and catastrophic in its performance: allocation time is linear in the number of free blocks, and the strategy of returning the first-fit block produces severe external fragmentation. The freelist remains useful as a teaching device and as the fallback mechanism in more sophisticated allocators, but no production system should rely on a pure freelist for general-purpose allocation. Its persistence in textbooks long after its obsolescence in practice is a reminder that pedagogical clarity and engineering soundness are not the same thing.