Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
Program 
gives the code for the Release member
function of the DoublyLinkedPool class.
This function takes as its lone argument a pointer to the
user part of the memory area to be released.
Program: DoublyLinkedPool Class Release Member Function Definition
The implementation shown is both simple and fast. The Release function makes no attempt to combine adjacent free areas. And since the free list is not sorted, it simply inserts the area to be freed at the front of the free list. This is done by inserting the area into the free list immediately after the sentinel. The private member function InsertAfter is called to accomplish this.
Because the free list is a doubly-linked list, the insertion can be done in constant time. Therefore, the worst-case running time of the Release function is O(1).
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.