What Is a Free List?

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.