Memory Allocations in Data Structures

Memory allocation is the process of setting aside sections of memory in a program to be used to store variables, and instances of structures and classes.

There are two types of memory allocations possible in C:

  1. Compile-time or Static allocation.
  2. Run-time or Dynamic allocation (using pointers).

Compile-time or Static allocation

  • Static memory allocation allocated by the compiler. Exact size and type of memory must be known at compile time.​​​​​​​
int x, y;
float a[5];

When the first statement is encountered, the compiler will allocate two bytes to each variables x and y. The second statement results into the allocction of 20 bytes to the array a (5*4, where there are five elements and each element of float type tales four bytes). Note that as there is no bound checking in C for array boundaries, i.e., if you have declared an array of five elements, as above and by mistake you are intending to read more than five values in the array a, it will still work without error. For example you are reading the above array as follows :

for ( i = 0 ; i < 10 ; i++)
{
  scanf ("%d", &a[i]);
}

Run-time or Dynamic allocation

  • Dynamic memory allocation is when an executing program requests that the operating system give it a block of main memory. The program then uses this memory for some purpose. Usually the purpose is to add a node to a data structure. In object-oriented languages, dynamic memory allocation is used to get the memory for a new object.
  • The memory comes from above the static part of the data segment. Programs may request memory and may also return previously dynamically allocated memory. Memory may be returned whenever it is no longer needed. Memory can be returned in any order without any relation to the order in which it was allocated. The heap may develop "holes" where previously allocated memory has been returned between blocks of memory still in use.
  • A new dynamic request for memory might return a range of addresses out of one of the holes. But it might not use up all the hole, so further dynamic requests might be satisfied out of the original hole.

​​​​​​​C provides the following dynamic allocation and de-allocation functions :

  • malloc( )
  • calloc( )
  • free( )
  • realloc( )

​​​​​​​The Malloc( ) Function

The malloc( ) function allocates a block of memory in bytes. The user should explicitly give the block sixe it requires of the use. The malloc( ) is like a request to the RAM of the system to allocate memoty.

Syntax:-

malloc (number of elements * size of each element) ;

Example:-

int *ptr ;
ptr = malloc (10 *sizeof(int))

The Calloc( ) Function

This function works exactly similar to malloc( ) function except for the fact that it needs two arguments as against one argument required by malloc( ).

Example:-

int *ptr ;
ptr = (int *) calloc (10, 2);

The Free( ) Function

The free( ) function is used to de-allocate the previously allocated memory using malloc( ) or calloc( ) functions.

Syntax:-

free (ptr_var);  // Where ptr_var is the pointer in which the address of the allocated memory block is assigned.

The Realloc( ) Function

This function is used to resize the size of memory block, which is already allocated. It found use of in two situations :

  • If the allocated memory block is insufficient for current application.
  • If the allocated memory is much more than what is required by the current application.

Syntax:-

ptr_var = realloc (ptr_var, new_size);