Block allocation onto the free list is Θ(n) if all elements are threaded into the free list at once:
free list = new node [n] for (i = 0; i < n - 1; i++) free list[i].next = free list + (i + 1) free list[n - 1].next = 0
At the cost of a bit more code complexity block allocation can be made constant time by initializing the new elements lazily (that is, on demand):
free list = free list next = new node [n] free list end = free list + n
free list next points to the next available uninitialized element;
free list end points to the end of of the block.
Element allocation now requires two checks: one for when the free list is empty and there are no more uninitialized blocks, and the other when the free list is empty but there are some uninitialized blocks:
if free list == free list end // allocate a new element block if free list == free list next free list next->next = free list next + 1 free list next++ // allocate an element
In this case initialization is one ahead of demand; it may be more efficient to initialize a constant number of elements ahead, but initialization is not that expensive and the complications may not be worth it.
Block allocation is actually more complicated than shown here: deallocating the blocks requires a second list containing all the blocks allocated to the ADT instance. This is easiest done by stealing one of the elements from the block and using it as a link in the chain of blocks.
This page last modified on 24 January 2006.