Free list

Free list

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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Free list — List List, n. [AS. l[=i]st a list of cloth; akin to D. lijst, G. leiste, OHG. l[=i]sta, Icel. lista, listi, Sw. list, Dan. liste. In sense 5 from F. liste, of German origin, and thus ultimately the same word.] 1. A strip forming the woven border… …   The Collaborative International Dictionary of English

  • free list — ☆ free list n. a list of goods not subject to tariff duties …   English World dictionary

  • free list — noun a list of commodities that are not subject to tariffs • Hypernyms: ↑list, ↑listing * * * noun : a list of persons or things for which no charge is made in circumstances when a charge is usual; specifically : a schedule of commodities… …   Useful english dictionary

  • free list — A list of articles on the importation of which no duties are charged, contained in the former § 1201 of Title 19 of the United States Code. In the present tariff schedules, the dutiable list and the free list are combined in 19 USC § 1202 by… …   Ballentine's law dictionary

  • Free List (Liechtenstein) — The Free List ( de. Freie Liste) is a left wing political party in Liechtenstein. As of 2005, it has three members of 25 in the Landtag of Liechtenstein, and describes itself as social, democratic and ecologist.External links*… …   Wikipedia

  • free list — a list or register of articles that may be brought into a country duty free. [1800 10] * * * …   Universalium

  • free list — A list, issued by the Customs and Excise, of the goods that can be imported into the UK without paying duty …   Big dictionary of business and management

  • List — List, n. [AS. l[=i]st a list of cloth; akin to D. lijst, G. leiste, OHG. l[=i]sta, Icel. lista, listi, Sw. list, Dan. liste. In sense 5 from F. liste, of German origin, and thus ultimately the same word.] 1. A strip forming the woven border or… …   The Collaborative International Dictionary of English

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • List of academic databases and search engines — This page contains a partial list of representative major databases and search engines useful in an academic setting for finding and accessing articles in academic journals, or in repositories, archives, or other collections of scientific and… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”