Free list

A free list (or freelist) is a data structure used in a scheme for dynamic memory allocation.

It is most suitable for allocating from a memory pool, where all objects have the same size.

Free lists make the allocation and deallocation operations very simple.

Free lists have the disadvantage, inherited from linked lists, of poor locality of reference and so poor data cache utilization, and they do not automatically consolidate adjacent regions to fulfill allocation requests for large regions, unlike the buddy allocation system.

Nevertheless, they are still useful in a variety of simple applications where a full-blown memory allocator is unnecessary or requires too much overhead.

This diagram represents five contiguous memory regions which each hold a pointer and a data block. The List Head points to the 2nd element, which points to the 5th, which points to the 4th, thereby forming a linked list of available memory regions.