Dynamic memory allocation

In the middle of a routine you realize that you need some scratch space n floating point numbers long, and n is a complicated function of the inputs to the routine. What do you do? Do you add another scratch space argument to your routine along with its length as an argument and check that it is big enough (stopping the program immediately if it is not)? Often a better idea is to allocate the memory needed. In Fortran 90 this is done using the allocate command; in C you use the malloc function; in C++ and Java the new operator will do this task; in Pascal the allocation is done by the new operator, but the syntax is different from C++ or Java. These can be used to dynamically allocate memory. All of these commands return, or set, a pointer to the allocated block of memory.

The allocated block of memory is taken from a global list of available memory which is ultimately controlled by the operating system. This block of memory remains allocated until it is no longer accessible (if garbage collection is used), explicitly de-allocated, or the program terminates. So dynamically allocated memory can be used to hold return values or returned data structures. Dynamically allocated memory can be passed to other routines, and treated like memory that has been statically allocated, or allocated on a stack in most respects.

The data structure that controls the allocation and de-allocation of memory is called a memory heap. A memory heap may contain a pair of linked lists of pointers to blocks of memory.