The free list is a stack: the next object allocated is the last one freed. We can use a list implementation of the stack operations PUSH and POP to implement the procedures for allocating and freeing objects, respectively. We assume that the global variable free used in the following procedures points to the first element of the free list.
ALLOCATE-OBJECT() 1 if free = NIL 2 then error "out of space" 3 else x ← free 4 free ← next[x] 5 return x
FREE-OBJECT(x) 1 next[x] ← free 2 free ← x
The free list initially contains all n unallocated objects. When the free list has been exhausted, the ALLOCATE-OBJECT procedure signals an error. It is common to use a single free list to service several linked lists. Figure 10.8 shows two linked lists and a free list intertwined through key, next, and prev arrays.
The two procedures run in O(1) time, which makes them quite practical. They can be modified to work for any omogeneous collection of objects by letting any one of the fields in the object act like a next field in the free list.