Introduction

This document explains dynamic memory allocation in C and how it's used to create dynamic data structures, focusing on linked lists. Understanding dynamic memory is crucial for building efficient and flexible programs that can adapt to varying data sizes at runtime.

Dynamic Memory

What is Dynamic Memory?

Dynamic memory is memory allocated during the execution of a program (runtime), as opposed to static memory, which is allocated during compilation. In C, dynamic memory is managed through functions provided by the standard library (stdlib.h). The key advantage of dynamic memory is that the size of memory needed can be determined during runtime, enabling programs to handle data of unpredictable or varying sizes.

Dynamic Memory Allocation Functions

The core functions for dynamic memory allocation in C are:

• malloc(size_t size): Allocates a block of memory of the specified size (in bytes). It returns a pointer to the beginning of the allocated memory, or NULL if the allocation fails. The allocated memory is uninitialized.
• calloc(size_t num, size_t size): Allocates a block of memory for an array of num elements, each of size bytes. It initializes all bytes in the allocated memory to zero. Returns a pointer to the allocated memory or NULL if the allocation fails.
• realloc(void *ptr, size_t size): Resizes a previously allocated block of memory pointed to by ptr to a new size of size bytes. It attempts to preserve the contents of the original block. If resizing to a larger size, the new memory is uninitialized. Returns a pointer to the reallocated memory, which may be the same as ptr or a new memory address. If ptr is NULL, realloc behaves like malloc. If size is 0 and ptr is not NULL, the memory pointed to by ptr is freed. Returns NULL if resizing fails.
• free(void *ptr): Deallocates a block of memory that was previously allocated using malloc, calloc, or realloc. It is crucial to free memory when it's no longer needed to prevent memory leaks. Passing NULL to free has no effect.

Example of Dynamic Memory Allocation

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

int main() {
    int *arr;
    int n;

    printf("Enter the number of elements: ");
    scanf("%d", &n);

    // Allocate memory for 'n' integers
    arr = (int *)malloc(n * sizeof(int));

    if (arr == NULL) {
        printf("Memory allocation failed!\n");
        return 1; // Indicate an error
    }

    // Initialize the array (optional)
    for (int i = 0; i < n; i++) {
        arr[i] = i * 2;
    }

    // Print the array
    printf("Array elements: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // Free the allocated memory
    free(arr);

    return 0;
} 

Memory Leaks

A memory leak occurs when dynamically allocated memory is no longer referenced by the program, but it has not been freed using free(). Over time, memory leaks can lead to program slowdown and eventual crashes. Always ensure you free() memory that you have allocated when it's no longer required.

Data Structures

A data structure is a particular way of organizing and storing data in a computer so that it can be used efficiently. Dynamic memory allocation is essential for creating dynamic data structures, whose size can change during program execution.

Examples of Data Structures

• Arrays (static vs. dynamic arrays)
• Linked Lists
• Stacks
• Queues
• Trees
• Graphs

Linked Lists: A Dynamic Data Structure

What is a Linked List?

A linked list is a linear data structure where each element (node) contains data and a pointer (link) to the next element in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations. This allows for dynamic resizing and efficient insertion and deletion of elements.

Structure of a Node

Each node in a linked list typically has two parts:

• Data: The information you want to store in the list.
• Next: A pointer to the next node in the list. The last node's next pointer is usually set to NULL.

Creating a Linked List in C

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

// Define the structure for a node
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1); // Exit the program if allocation fails
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the beginning of the list
void insertAtBeginning(Node** headRef, int data) {
    Node* newNode = createNode(data);
    newNode->next = *headRef;
    *headRef = newNode;
}

// Function to print the linked list
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Function to free the linked list's memory (important to prevent memory leaks)
void freeList(Node* head) {
    Node* current = head;
    Node* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    Node* head = NULL; // Initialize an empty list

    // Insert some nodes
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 1);

    printf("Linked List: ");
    printList(head);

    // Free the allocated memory
    freeList(head);
    head = NULL; // Important: Set the head to NULL after freeing

    return 0;
} 

Explanation of the Code

1. Node Structure: Defines the Node structure containing an integer data and a pointer next to the next node.
2. createNode(): Allocates memory for a new node using malloc(), initializes its data field, sets its next pointer to NULL, and returns a pointer to the new node. Error handling is included to check for allocation failures.
3. insertAtBeginning(): Inserts a new node at the beginning of the linked list. It updates the headRef (a pointer to the head pointer) to point to the new node.
4. printList(): Traverses the linked list and prints the data of each node.
5. freeList(): Iterates through the list, freeing each node one by one to prevent memory leaks. It's crucial to free the memory occupied by the list after you are finished with it. We need to store the next node before freeing the current node.
6. main(): Creates an empty linked list, inserts some nodes, prints the list, and then frees the allocated memory using freeList(). It is *critical* to set the `head` to `NULL` after freeing the list. This prevents dangling pointers.

Benefits of Linked Lists

• Dynamic Size: Can grow or shrink as needed during runtime.
• Efficient Insertion and Deletion: Insertion and deletion of nodes are relatively easy, especially compared to arrays (where elements after the insertion/deletion point need to be shifted).

Disadvantages of Linked Lists

• Memory Overhead: Each node requires extra memory for the pointer.
• No Random Access: Accessing a specific element requires traversing the list from the beginning, making random access inefficient.

Conclusion

Dynamic memory allocation is a powerful feature in C that allows programs to manage memory more efficiently and create dynamic data structures like linked lists. Understanding the principles of dynamic memory, including allocation, deallocation, and memory leak prevention, is crucial for writing robust and efficient C programs. Linked lists are just one example of the many dynamic data structures that can be implemented using dynamic memory allocation. Other examples include stacks, queues, and trees.