Free list
From Wikipedia, the free encyclopedia
A free list is a data structure used in a scheme for dynamic memory allocation. It operates by connecting unallocated regions of memory together in a linked list, using the first word of each unallocated region as a pointer to the next. It's 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. To free a region, we just add it to the free list. To allocate a region, we simply remove a single region from the end of the free list and use it. If the regions are variable-sized, we may have to search for a region of large enough size, which can be expensive.
Free lists have the disadvantage, inherited from linked lists, of poor locality of reference and so poor data cache utilization, and they provide no way of consolidating adjacent regions to fulfill allocation requests for large regions, unlike the buddy allocation system. Nevertheless, they're still useful in a variety of simple applications where a full-blown memory allocator is unnecessary or requires too much overhead.
[edit] References
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 210–212 of section 10.3: Implementing pointers and objects.
