Miscellaneous Topics in DS

Memory Allocation

• The process of creating new memory by the compiler either at compile time or during program execution/at run time is called memory allocation.
• Whenever a new node is created, memory is allocated by the system. This memory is taken/created from list of those memory locations which are free i.e. not allocated. This list is called AVAIL List. Similarly, whenever a node is deleted/destroyed, the deleted space becomes reusable/free and is added to the list of unused space i.e. to AVAIL List. This unused space can be used again in future for memory allocation for other new operations.
• There are two types of memory allocation –
  •  Static Memory Allocation –
    • When memory is allocated during compilation time/before run time by the compiler of given exact size and datatype of memory, it is called static memory location.
    • This memory allocation is fixed and can not be increased or decreased after allocation.
    • If more memory is allocated than requirements, then memory is wasted. If less memory is allocated than requirements, then program will not run successfully. So, exact memory requirements must be known in advance.
    • Example – Array.
  • Dynamic Memory Allocation –
    • When memory is allocated during run/execution time it is called dynamic memory allocation.
    • This memory is not fixed and is allocated according to our requirements. Thus, in this allocation there is no wastage of memory. So there is no need to know exact memory requirements in advance.
    • In C, this In-built library function malloc()/calloc() is used to allocate a fresh block of memory in the form of heap. A memory heap is a location in memory where memory may be allocated at random access i.e. individual data elements allocated on the heap are typically released in ways which is asynchronous from one another.
    • Examples – Linked list, Stack, Queue, Tree, Graphs etc.

Memory De-allocation

• The process of removal of created/existing memory by the compiler after program completion is called memory de-allocation.
• It increases the no. of free space for memory for future use.
• It does the reverse of memory allocation.

Dynamic Memory Allocation/De-allocation Methods

• The process of creating fresh memory during program execution/at run time of the program is called dynamic memory allocation.
• It is a system memory management techniques occurs at run time.
• These methods are mainly used in C to allocate fresh/de-allocate existing memory dynamically.
• These methods are present in C standard library(malloc.h/stdlib.h).
• The C++ programming language also performs similar functions, but the operators new and delete are used for that.
• When we use malloc()/calloc() to allocate memory, it actually allocates some more/extra memory than specified. This extra memory is needed to store some related metadata which keeps track of the size of the block, link to next block, etc. Thus, it is considered as the dis-advantage of dynamic memory allocation.
• In C programming language, Dynamic Memory Management is performed via a group four functions named malloc(), calloc(), realloc(), and free(). Here, first three are used in dynamic memory allocation whereas free() is used in dynamic memory de-allocation.These are – 

malloc() :

• The name “malloc” stands for memory allocation.
• Malloc() is a system function which allocates a block of memory in the “heap” and returns a pointer to the new block.
• The malloc() function creates/allocates single large block of fresh memory with the specified size in bytes and returns a pointer of type void which can be cast into a pointer of any form for the allocated memory.
• The prototype of malloc() and other heap functions are in stdlib.h/malloc.h.
• Syntax: pointer = (cast-type*) malloc(sizeof(cast-type));
• It is defined as –
  • void *malloc (number_of_bytes);

Here void * is a returned type C standard states that this pointer can be converted to any type.

• For Example –
  • char *cp; cp = (char *) malloc (100);
  • int *ip; ip = (int *) malloc (100*sizeof(int));
  • ptr = (int*) malloc(sizeof(int));
  • ptr = (struct student*) malloc(sizeof(struct student)); 
• Malloc() returns NULL if it cannot fulfill the request.
• The malloc() function allocates memory and leaves it uninitialized.
• The malloc() function reserves a block of memory of the specified number of bytes.

calloc() :

• The name “calloc” stands for contiguous allocation.
• calloc() is another memory allocation function that is used for allocating a specified amount of memory in bytes and then initialize it to zero and finally returns a void pointer to the allocated memory location, which can then be cast to the desired type as in malloc. When it fails to allocate specified size of space, it returns a NULL pointer.
• Calloc is better than malloc because of the allocated region is initialized to zero or no garbage values but malloc is faster than calloc. This is because calloc takes little longer time than malloc to initialize the allocated memory by zero.

realloc() :

• It is used to dynamically change the memory allocation of a previously allocated memory.
• In other words, if the memory previously allocated with the help of malloc() or calloc() is insufficient/unsatisfactory, realloc() can be used to re-allocate memory dynamically again to satisfy the required conditions.

free() :

• This C library function de-allocates the memory, that was previously allocated by a calling either a calloc, malloc, or realloc method.
• free() is the opposite of malloc(), which de-allocates memory.
• The argument of free() is a pointer to a block of memory in the heap.This pointer which was obtained by a malloc() function.
• The syntax is: free (ptr);
• The advantage of free() is simply memory management when we no longer need a block.