A free list is a data structure that holds the addresses of computer memory locations that are available for use by a running program when using dynamic memory allocation. The list becomes necessary when a program must allocate space from an area of free memory called the heap. The implementation of a free list can be a simple linked list or could be a more complex data structure such as a sort tree. Most high-level computer programming languages automatically handle the free list, removing the need for manual management.
When a program requires space to store information during program execution, it must request a specific amount of memory from the underlying operating system. The locations of memory blocks that can be utilized are stored in the free list. For the allocation to be successful, the amount of requested memory needs to be available in one or more of these blocks. When a pointer to an appropriate memory location is returned, that element of the list is removed.
After a program is done using the memory, it can de-allocate it. This involves passing the pointer to the memory block back into the free list, where it will become available the next time an allocation is attempted. It is possible for memory allocation to fail because the list is empty or because there are no available memory blocks large enough to fulfill the program’s request.
The simplest form of memory management is called the first fit system. This system maintains a single list of free memory locations. When a request for memory is sent, the list is traversed and the first block that is large enough is returned. If the block is more than twice the requested size, then it is halved, and the unused half is added back to the list. This method trades simple coding for the risk of having fragmented memory areas that might never be returned to the list.
A different form of memory management is called the buddy allocation system. Unlike the first fit system, buddy allocation keeps several free lists, each one holding open blocks of only one particular size. This means that when an allocation request is received, the list that holds blocks that are just large enough to fill the request is consulted, and an open location is returned. If no free blocks that are less than twice the size requested are available, a larger block is split in two to fulfill the requirements.
The term "free list" can refer to either a single linked list of memory addresses, or it can refer to a much more complex type of data structure. Different types of sort trees, if kept simple and balanced, can help increase the speed of finding open memory blocks at the expense of complicating the source code. A linked list can be slower than a specialized sort tree but creates programming code that is far easier to read, debug and modify.
Some programming languages and operating systems make use of a special mechanism called garbage collection. This is a process that can help take the different entries on a free list and consolidate the free spaces so that they are contiguous. This has the effect of preventing fragmentation and allowing for larger blocks of memory to be allocated.
