The simplest organization for the list of available space is a two-way circular list, with nodes kept in arbitrary order, in order by size, or in order by actual memory address. Two-way lists are convenient for making insertions and deletions. They allow the list to be traversed starting from any list record, and in either direction. A request for a node of size l then requires a traversal of the list, starting from some initial node.
Two simple policies for selection of the list node to be deleted to satisfy a request are first-fit and best-fit. First-fit selects the first node encountered whose size is sufficient. Best-fit does a complete traversal and selects that node of smallest size that is sufficient to satisfy the request. Of course, if an exact fit is found, the traversal need not continue. For both policies, any leftover storage is retained as a node on the list.
When a node is returned to the list, its neighbors (in terms of storage addresses) are coalesced with it if free, and the resultant node properly inserted on the list. All nodes require tag and size fields, with the list nodes also needing backward and forward link fields. The tag field distinguishes nodes in use from those not in use, depending on which of two values it contains.
Allowing the starting node to circulate around the list, always being set to the successor of the deleted (or truncated) node, typically improves performance.This circulation provides time for the smaller nodes left behind it to coalesce so that, by the next time around, larger nodes have been formed.
Intuitively, spending more time fitting the size of the selected node to the size of the requested node should cut down on fragmentation effects. Surprisingly, this need not always happen, but it is the normal situation.