Pooling memory for allocating links turns the allocation into amortized constant time. List insertion is O(1) if you insert it at the head, and while moving th

Pooling memory for allocating links turns the allocation into amortized constant time. List insertion is O(1) if you insert it at the head, and while moving the most-recently-accessed link to the head of the chain doesn't change the worst case behavior, it greatly improves the average in practice (and is dead easy).