Dynamic Memory Allocation in Data Structures: malloc, calloc, realloc, free and Linked Structures

Dynamic memory allocation appears twice in the TU syllabus. In C Programming (CSC115 and BIT102) it is the last part of the pointers unit, and in Data Structures and Algorithms (CSC211 and BIT201) it is the mechanism behind every linked list, tree and graph you build. The exam question is usually "What is dynamic memory allocation? Explain malloc(), calloc(), realloc() and free() with examples" for 5 marks, or "Differentiate static and dynamic memory allocation and explain how a linked list uses dynamic allocation" for 10.

This article covers the concept, the four functions with short code, the link to data structures, the errors examiners want you to name, and an answer outline. The unit notes and solved questions are on the Pointers notes page for CSC115 and the Lists notes page for CSC211.

Static versus dynamic allocation

When a C program runs, its memory is divided into segments. The code segment holds instructions. The data segment holds global and static variables. The stack holds local variables and function call records, allocated and freed automatically as functions are called and return. The heap is a pool of memory that the program requests and releases itself while it is running.

Static (or compile-time) allocation is what happens for ordinary variables and arrays: int marks[50]; reserves space for exactly 50 integers before the program starts, and that size cannot change. Dynamic (or run-time) allocation is what happens when the program asks for memory while running, using the functions in <stdlib.h>, and the size can depend on input.

Dynamic allocation exists because real programs do not know in advance how many students, records or nodes they will handle. An array sized for the worst case wastes memory; an array sized too small fails. Allocating exactly what is needed, when it is needed, solves both.

The four functions

malloc()

void *malloc(size_t size); allocates a single block of size bytes and returns a pointer to its first byte. The block's contents are uninitialised (garbage). It returns NULL if the request cannot be satisfied, so the return value must be checked.

int *p = (int *) malloc(5 * sizeof(int));
if (p == NULL) { printf("Memory not available"); exit(1); }

calloc()

void *calloc(size_t n, size_t size); allocates memory for n elements of size bytes each, so n * size bytes in total, and sets every byte to zero. It is the natural choice for arrays that must start at zero, such as counters.

int *p = (int *) calloc(5, sizeof(int));   /* 5 integers, all 0 */

realloc()

void *realloc(void *ptr, size_t newsize); changes the size of a block previously obtained from malloc or calloc. If the block can be extended in place it is; otherwise a new block is allocated, the old contents are copied, and the old block is freed. The existing data up to the smaller of the old and new sizes is preserved. Any extra bytes are uninitialised.

p = (int *) realloc(p, 10 * sizeof(int));  /* now room for 10 integers */

free()

void free(void *ptr); returns a block to the heap so it can be reused. After free(), the pointer still holds the old address but must not be used; good practice sets it to NULL.

free(p);
p = NULL;

A complete example

The classic exam program reads n marks into a dynamically sized array and prints their sum:

#include <stdio.h>
#include <stdlib.h>
int main() {
    int n, i, sum = 0, *marks;
    printf("How many students? ");
    scanf("%d", &n);
    marks = (int *) malloc(n * sizeof(int));
    if (marks == NULL) { printf("Allocation failed\n"); return 1; }
    for (i = 0; i < n; i++) scanf("%d", &marks[i]);
    for (i = 0; i < n; i++) sum += marks[i];
    printf("Total = %d\n", sum);
    free(marks);
    return 0;
}

The program allocates exactly n integers, uses the pointer like an array, and frees the block before exiting.

Dynamic allocation in data structures

This is the part the Data Structures paper cares about. An array is a static structure: contiguous, fixed size, with elements reached by index. A linked list is a dynamic structure: each element is a node allocated separately on the heap, holding its data and a pointer to the next node.

struct node {
    int data;
    struct node *next;
};
struct node *newnode = (struct node *) malloc(sizeof(struct node));
newnode->data = 10;
newnode->next = NULL;

Every insertion into a linked list, stack or queue implemented with links calls malloc for one node; every deletion calls free for one node. The list therefore grows and shrinks to exactly the number of elements present, with no upper limit other than available memory. Trees and graphs are built the same way: a binary tree node holds data and two pointers, allocated when the node is created.

The comparison examiners expect:

The BIT syllabus covers the same material in the Linked Lists unit of BIT201.

Errors to name in the answer

• Memory leak: allocated memory that is never freed, so the program's memory use grows until it fails. Caused by losing the only pointer to a block or forgetting free().
• Dangling pointer: a pointer that still holds the address of a block that has been freed. Using it gives undefined behaviour.
• Double free: calling free() twice on the same block, which corrupts the allocator.
• Buffer overflow: writing beyond the size that was allocated.
• Unchecked NULL: using the result of malloc without testing for failure.
• Fragmentation: after many allocations and releases of different sizes, free memory is split into small pieces, so a large request fails even though the total free memory would be enough.

Exam answer outline

For 5 marks: define dynamic memory allocation and the heap, then give the four functions with their prototypes, one line each, and a two-line example of malloc with free.

For 10 marks: add the static versus dynamic table, the complete marks program, the linked list node example with an explanation of how insertion and deletion use malloc and free, and three of the errors above. If the question is framed from the data structures side, lead with the array versus linked list comparison and keep the function descriptions short.

Dynamic allocation is also the base of the Introduction to Data Structures and Algorithms unit, where the distinction between static and dynamic data structures is a standard 1-mark and 5-mark question. Solved past questions for both subjects are on the CSC115 and CSC211 pages.