C Dynamic data structure - Introduction

By Dr. Roger Ianjamasimanana

1. What are dynamic data structures?
2. Stack vs heap memory
    2.1 Stack memory
    2.2 Heap memory
3. Dynamic memory allocation functions
    3.1 The malloc function
    3.2 The calloc function
    3.3 The realloc function
    3.4 The free function
4. Memory leaks and how to avoid them
5. Dynamic arrays
    5.1 Implementing a simple dynamic array
6. Introduction to linked lists
    6.1 Why use linked lists?
    6.2 The node structure
    6.3 Creating a complete linked list implementation
7. Visualising linked lists
    7.1 Inserting at the beginning
8. Comparing arrays and linked lists
9. Common mistakes with dynamic data structures
    9.1 Forgetting to check for NULL
    9.2 Using memory after freeing
    9.3 Freeing memory twice
10. Practical exercise
11. Summary

1. What are dynamic data structures?

When you declare an array in C, you must specify its size at compile time. This means you decide how much memory the array will use before your programme even runs. But what if you do not know in advance how many elements you will need?

Dynamic data structures solve this problem. They allow your programme to request memory while it is running and release that memory when it is no longer needed. This flexibility makes dynamic data structures essential for building real-world applications.

2. Stack vs heap memory

Before diving into dynamic data structures, you need to understand where your data lives in memory. C programmes use two main memory regions: the stack and the heap.

2.1 Stack memory

The stack is where local variables live. When you declare a variable inside a function, it goes on the stack. The stack is fast but limited in size, and memory is automatically freed when a function returns.

#include <stdio.h>

void demonstrateStack() {
    int localVariable = 42;  // This lives on the stack
    int localArray[5] = {1, 2, 3, 4, 5};  // This also lives on the stack
    
    printf("Local variable value: %d\n", localVariable);
    printf("Local array first element: %d\n", localArray[0]);
}
// When this function ends, localVariable and localArray are automatically destroyed

int main() {
    demonstrateStack();
    return 0;
}

2.2 Heap memory

The heap is a larger pool of memory that you manage manually. You request memory from the heap when you need it and release it when you are finished. This gives you flexibility but also responsibility; if you forget to release memory, your programme develops a memory leak.

The heap is where dynamic data structures live. Unlike stack memory, heap memory persists until you explicitly free it or your programme ends.

3. Dynamic memory allocation functions

C provides four main functions for working with heap memory. All of these are declared in the <stdlib.h> header file.

3.1 The malloc function

The malloc function (memory allocation) requests a block of memory of a specified size. It returns a pointer to the beginning of that block, or NULL if the allocation fails.

void *malloc(size_t size);

The function takes the number of bytes you want and returns a void pointer. You typically cast this pointer to the type you need.

#include <stdio.h>
#include <stdlib.h>

int main() {
    // Allocate memory for a single integer
    int *number = (int *)malloc(sizeof(int));
    
    if (number == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }
    
    *number = 100;
    printf("Value stored in dynamically allocated memory: %d\n", *number);
    
    // Always free memory when done
    free(number);
    
    return 0;
}

Allocating memory for an array

To allocate memory for multiple elements, multiply the size of one element by the number of elements you need.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n = 5;
    
    // Allocate memory for 5 integers
    int *array = (int *)malloc(n * sizeof(int));
    
    if (array == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }
    
    // Use the array just like a normal array
    for (int i = 0; i < n; i++) {
        array[i] = (i + 1) * 10;
    }
    
    // Print the values
    printf("Dynamic array contents: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    
    // Free the memory
    free(array);
    
    return 0;
}

3.2 The calloc function

The calloc function (contiguous allocation) works similarly to malloc, but with two important differences. First, it takes two arguments: the number of elements and the size of each element. Second, it initialises all allocated memory to zero.

void *calloc(size_t num_elements, size_t element_size);

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n = 5;
    
    // Allocate and initialise memory for 5 integers to zero
    int *array = (int *)calloc(n, sizeof(int));
    
    if (array == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }
    
    // All values are automatically initialised to 0
    printf("Initial values (all zeros): ");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    
    free(array);
    
    return 0;
}

When to use calloc vs malloc

Use calloc when you need your memory initialised to zero. Use malloc when you plan to immediately overwrite the memory with your own values, as malloc is slightly faster since it skips the initialisation step.

3.3 The realloc function

The realloc function (re-allocation) changes the size of a previously allocated memory block. This is useful when you need to grow or shrink a dynamic array.

void *realloc(void *ptr, size_t new_size);

#include <stdio.h>
#include <stdlib.h>

int main() {
    int *array = (int *)malloc(3 * sizeof(int));
    
    if (array == NULL) {
        printf("Initial allocation failed!\n");
        return 1;
    }
    
    // Store initial values
    array[0] = 10;
    array[1] = 20;
    array[2] = 30;
    
    printf("Original array (3 elements): ");
    for (int i = 0; i < 3; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    
    // Resize the array to hold 5 elements
    int *temp = (int *)realloc(array, 5 * sizeof(int));
    
    if (temp == NULL) {
        printf("Reallocation failed!\n");
        free(array);  // Free original memory if realloc fails
        return 1;
    }
    
    array = temp;  // Update pointer to new memory location
    
    // Add new values
    array[3] = 40;
    array[4] = 50;
    
    printf("Resized array (5 elements): ");
    for (int i = 0; i < 5; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    
    free(array);
    
    return 0;
}

Important note about realloc

Always assign the result of realloc to a temporary pointer first. If realloc fails, it returns NULL but does not free the original memory. If you assign directly to your original pointer, you lose access to the original memory and create a memory leak.

3.4 The free function

The free function releases memory back to the system. Every call to malloc, calloc, or realloc should eventually have a corresponding call to free.

void free(void *ptr);

#include <stdio.h>
#include <stdlib.h>

int main() {
    int *ptr = (int *)malloc(sizeof(int));
    
    if (ptr == NULL) {
        return 1;
    }
    
    *ptr = 42;
    printf("Value: %d\n", *ptr);
    
    // Release the memory
    free(ptr);
    
    // Good practice: set pointer to NULL after freeing
    ptr = NULL;
    
    return 0;
}

4. Memory leaks and how to avoid them

A memory leak occurs when your programme allocates memory but never frees it. Over time, memory leaks can cause your programme to consume more and more memory, eventually slowing down or crashing your system.

Example of a memory leak

#include <stdio.h>
#include <stdlib.h>

// BAD: This function leaks memory
void leakyFunction() {
    int *data = (int *)malloc(100 * sizeof(int));
    // Do some work with data...
    // Oops! Forgot to free(data) before returning
}

// GOOD: This function properly manages memory
void properFunction() {
    int *data = (int *)malloc(100 * sizeof(int));
    
    if (data == NULL) {
        return;
    }
    
    // Do some work with data...
    
    free(data);  // Always free before returning
}

int main() {
    // Each call to leakyFunction loses memory
    for (int i = 0; i < 1000; i++) {
        leakyFunction();  // Memory leak!
    }
    
    // properFunction cleans up after itself
    for (int i = 0; i < 1000; i++) {
        properFunction();  // No leak
    }
    
    return 0;
}

Tips to avoid memory leaks

Match every allocation with a free: for every malloc or calloc, ensure there is a corresponding free.
Free memory before reassigning pointers: if you allocate new memory to a pointer that already points to allocated memory, free the old memory first.
Set pointers to NULL after freeing: this helps you identify freed pointers and prevents accidental use of freed memory.
Use tools like Valgrind: memory debugging tools can help you find leaks during development.

5. Dynamic arrays

A dynamic array is an array that can grow or shrink during programme execution. Unlike static arrays, dynamic arrays do not have a fixed size determined at compile time.

5.1 Implementing a simple dynamic array

The following example demonstrates how to create a dynamic array that grows automatically when it becomes full.

#include <stdio.h>
#include <stdlib.h>

// Structure to represent a dynamic array
typedef struct {
    int *data;      // Pointer to the array elements
    int size;       // Number of elements currently in the array
    int capacity;   // Total capacity of the array
} DynamicArray;

// Initialise a new dynamic array
DynamicArray *createArray(int initialCapacity) {
    DynamicArray *arr = (DynamicArray *)malloc(sizeof(DynamicArray));
    
    if (arr == NULL) {
        return NULL;
    }
    
    arr->data = (int *)malloc(initialCapacity * sizeof(int));
    
    if (arr->data == NULL) {
        free(arr);
        return NULL;
    }
    
    arr->size = 0;
    arr->capacity = initialCapacity;
    
    return arr;
}

// Add an element to the array
int addElement(DynamicArray *arr, int value) {
    // Check if we need to resize
    if (arr->size >= arr->capacity) {
        int newCapacity = arr->capacity * 2;
        int *temp = (int *)realloc(arr->data, newCapacity * sizeof(int));
        
        if (temp == NULL) {
            return 0;  // Resize failed
        }
        
        arr->data = temp;
        arr->capacity = newCapacity;
        printf("Array resized to capacity: %d\n", newCapacity);
    }
    
    arr->data[arr->size] = value;
    arr->size++;
    
    return 1;  // Success
}

// Free the dynamic array
void freeArray(DynamicArray *arr) {
    if (arr != NULL) {
        free(arr->data);
        free(arr);
    }
}

// Print the array contents
void printArray(DynamicArray *arr) {
    printf("Array (size=%d, capacity=%d): ", arr->size, arr->capacity);
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");
}

int main() {
    // Create a dynamic array with initial capacity of 2
    DynamicArray *myArray = createArray(2);
    
    if (myArray == NULL) {
        printf("Failed to create array!\n");
        return 1;
    }
    
    // Add elements (array will grow automatically)
    for (int i = 1; i <= 10; i++) {
        addElement(myArray, i * 10);
        printArray(myArray);
    }
    
    // Clean up
    freeArray(myArray);
    
    return 0;
}

When you run this programme, you will see the array automatically doubling its capacity whenever it becomes full. This doubling strategy is efficient because it minimises the number of expensive reallocation operations.

6. Introduction to linked lists

A linked list is a data structure where elements (called nodes) are stored in separate memory locations and connected through pointers. Unlike arrays, linked list elements do not need to be stored in contiguous memory.

6.1 Why use linked lists?

Linked lists offer several advantages over arrays. Inserting or deleting elements at the beginning or middle of a linked list is efficient because you only need to update pointers. With arrays, these operations require shifting all subsequent elements.

However, linked lists also have disadvantages. Accessing an element by index requires traversing the list from the beginning, making random access slow. Linked lists also use more memory because each node stores both data and a pointer.

6.2 The node structure

Each node in a singly linked list contains two parts: the data and a pointer to the next node.

#include <stdio.h>
#include <stdlib.h>

// Define the node structure
struct Node {
    int data;           // The value stored in this node
    struct Node *next;  // Pointer to the next node
};

int main() {
    // Create three nodes manually
    struct Node *first = (struct Node *)malloc(sizeof(struct Node));
    struct Node *second = (struct Node *)malloc(sizeof(struct Node));
    struct Node *third = (struct Node *)malloc(sizeof(struct Node));
    
    // Check allocation
    if (first == NULL || second == NULL || third == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }
    
    // Assign data and link the nodes
    first->data = 10;
    first->next = second;
    
    second->data = 20;
    second->next = third;
    
    third->data = 30;
    third->next = NULL;  // Last node points to NULL
    
    // Traverse and print the list
    struct Node *current = first;
    printf("Linked list: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
    
    // Free the nodes
    free(first);
    free(second);
    free(third);
    
    return 0;
}

6.3 Creating a complete linked list implementation

The following programme demonstrates a complete singly linked list with functions to insert, delete, search, and display elements.

#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// Create a new node
Node *createNode(int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return NULL;
    }
    
    newNode->data = value;
    newNode->next = NULL;
    
    return newNode;
}

// Insert at the beginning of the list
Node *insertAtBeginning(Node *head, int value) {
    Node *newNode = createNode(value);
    
    if (newNode == NULL) {
        return head;
    }
    
    newNode->next = head;
    return newNode;  // New node becomes the new head
}

// Insert at the end of the list
Node *insertAtEnd(Node *head, int value) {
    Node *newNode = createNode(value);
    
    if (newNode == NULL) {
        return head;
    }
    
    // If list is empty, new node becomes the head
    if (head == NULL) {
        return newNode;
    }
    
    // Traverse to the last node
    Node *current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    current->next = newNode;
    return head;
}

// Delete a node with a specific value
Node *deleteNode(Node *head, int value) {
    if (head == NULL) {
        printf("List is empty!\n");
        return NULL;
    }
    
    // Special case: deleting the head
    if (head->data == value) {
        Node *temp = head;
        head = head->next;
        free(temp);
        printf("Deleted %d from the list.\n", value);
        return head;
    }
    
    // Search for the node to delete
    Node *current = head;
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }
    
    // Node not found
    if (current->next == NULL) {
        printf("Value %d not found in the list.\n", value);
        return head;
    }
    
    // Delete the node
    Node *temp = current->next;
    current->next = temp->next;
    free(temp);
    printf("Deleted %d from the list.\n", value);
    
    return head;
}

// Search for a value in the list
int search(Node *head, int value) {
    Node *current = head;
    int position = 0;
    
    while (current != NULL) {
        if (current->data == value) {
            return position;
        }
        current = current->next;
        position++;
    }
    
    return -1;  // Not found
}

// Display the list
void displayList(Node *head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    
    printf("List: ");
    Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Free all nodes in the list
void freeList(Node *head) {
    Node *current = head;
    Node *next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

// Count the number of nodes
int countNodes(Node *head) {
    int count = 0;
    Node *current = head;
    
    while (current != NULL) {
        count++;
        current = current->next;
    }
    
    return count;
}

int main() {
    Node *head = NULL;
    
    // Insert elements
    printf("=== Inserting elements ===\n");
    head = insertAtEnd(head, 10);
    head = insertAtEnd(head, 20);
    head = insertAtEnd(head, 30);
    displayList(head);
    
    head = insertAtBeginning(head, 5);
    displayList(head);
    
    // Search for elements
    printf("\n=== Searching ===\n");
    int pos = search(head, 20);
    if (pos != -1) {
        printf("Found 20 at position %d\n", pos);
    }
    
    pos = search(head, 100);
    if (pos == -1) {
        printf("100 not found in the list\n");
    }
    
    // Count nodes
    printf("\n=== Counting ===\n");
    printf("Number of nodes: %d\n", countNodes(head));
    
    // Delete elements
    printf("\n=== Deleting elements ===\n");
    head = deleteNode(head, 20);
    displayList(head);
    
    head = deleteNode(head, 5);
    displayList(head);
    
    head = deleteNode(head, 100);  // Try to delete non-existent value
    
    // Clean up
    printf("\n=== Cleaning up ===\n");
    freeList(head);
    printf("All memory freed.\n");
    
    return 0;
}

7. Visualising linked lists

Understanding how linked lists work in memory is crucial. Here is a visual representation of a linked list with three nodes containing values 10, 20, and 30.

head
  |
  v
+------+------+    +------+------+    +------+------+
|  10  | next |--->|  20  | next |--->|  30  | NULL |
+------+------+    +------+------+    +------+------+

Each box represents a node. The left section holds the data, and the right section holds the pointer to the next node. The last node's pointer is NULL, indicating the end of the list.

7.1 Inserting at the beginning

When you insert a new node at the beginning, you create the node, point it to the current head, and then update the head to point to the new node.

Before inserting 5:

head
  |
  v
+------+------+    +------+------+
|  10  | next |--->|  20  | NULL |
+------+------+    +------+------+

After inserting 5 at beginning:

head
  |
  v
+------+------+    +------+------+    +------+------+
|   5  | next |--->|  10  | next |--->|  20  | NULL |
+------+------+    +------+------+    +------+------+

8. Comparing arrays and linked lists

Both data structures have their place. Understanding their trade-offs helps you choose the right one for your needs.

Operation	Array	Linked list
Access by index	O(1) - instant	O(n) - must traverse
Insert at beginning	O(n) - shift all elements	O(1) - update pointers
Insert at end	O(1) if space available	O(n) - traverse to end
Delete from beginning	O(n) - shift all elements	O(1) - update head
Memory usage	Contiguous, efficient	Extra space for pointers
Cache performance	Excellent (locality)	Poor (scattered memory)

9. Common mistakes with dynamic data structures

9.1 Forgetting to check for NULL

Always check if memory allocation succeeded. Dereferencing a NULL pointer causes your programme to crash.

// BAD: No NULL check
int *ptr = (int *)malloc(sizeof(int));
*ptr = 10;  // Crash if malloc failed!

// GOOD: Always check
int *ptr = (int *)malloc(sizeof(int));
if (ptr == NULL) {
    // Handle error
    return;
}
*ptr = 10;

9.2 Using memory after freeing

Accessing memory after calling free leads to undefined behaviour. The memory might still contain your data, or it might have been overwritten.

// BAD: Using freed memory
int *ptr = (int *)malloc(sizeof(int));
*ptr = 42;
free(ptr);
printf("%d\n", *ptr);  // Undefined behaviour!

// GOOD: Set pointer to NULL after freeing
int *ptr = (int *)malloc(sizeof(int));
*ptr = 42;
free(ptr);
ptr = NULL;  // Now any attempt to use ptr will be caught

9.3 Freeing memory twice

Calling free on the same pointer twice corrupts the memory management system and can crash your programme.

// BAD: Double free
int *ptr = (int *)malloc(sizeof(int));
free(ptr);
free(ptr);  // Crash or corruption!

// GOOD: Set to NULL after freeing
int *ptr = (int *)malloc(sizeof(int));
free(ptr);
ptr = NULL;
// free(NULL) is safe and does nothing

10. Practical exercise

Try modifying the linked list implementation above to add these features:

Insert at a specific position: add a function that inserts a node at a given index.
Reverse the list: write a function that reverses the order of all nodes.
Find the middle element: implement a function that finds the middle node efficiently.

These exercises will strengthen your understanding of pointer manipulation and dynamic memory management.

11. Summary

Dynamic data structures are fundamental to writing flexible, efficient programmes. In this lesson, you learned the difference between stack and heap memory, how to use malloc, calloc, realloc, and free for memory management, and how to implement dynamic arrays and linked lists.

Remember to always free memory you allocate, check for NULL after allocation, and set pointers to NULL after freeing them. These habits will help you write robust, memory-safe C programmes.

In the next lesson, we will explore more complex data structures like stacks and queues, which build upon the linked list concepts you have learned here.

6 Views 0 Comments

Readers’ comment

🔐 Access