Chapter 14: Dynamic Memory Allocation and Linked Lists

📌 Learning Objectives

LO 14.1: Understand dynamic memory allocation concepts
LO 14.2: Use malloc(), calloc(), realloc(), and free() functions
LO 14.3: Understand self-referential structures
LO 14.4: Create and traverse linked lists
LO 14.5: Insert and delete nodes in linked lists

14.1 Introduction to Dynamic Memory Allocation

Static memory allocation (arrays) requires specifying size at compile time. Dynamic memory allocation allows allocating memory at run time, optimizing memory usage.

Advantages of dynamic allocation:

Memory can be allocated as needed during program execution
No need to know the exact size requirements in advance
Memory can be released when no longer needed
Enables creation of dynamic data structures like linked lists

14.2 Memory Allocation Functions

C provides four functions for dynamic memory management, declared in <stdlib.h>:

Function	Syntax	Description
`malloc`	`void *malloc(size_t size);`	Allocates a block of size bytes. Returns pointer to first byte.
`calloc`	`void *calloc(size_t n, size_t size);`	Allocates space for n elements of size bytes each, initialized to 0.
`realloc`	`void realloc(void ptr, size_t size);`	Changes size of previously allocated memory.
`free`	`void free(void *ptr);`	Frees previously allocated memory.

Memory layout of a C program:

        ┌─────────────────────┐
        │   Program Code      │
        ├─────────────────────┤
        │   Static/Global     │  ← Permanent storage area
        │     Variables       │
        ├─────────────────────┤
        │                     │
        │        HEAP         │  ← Dynamic memory allocation
        │  (grows downward)   │
        ├─────────────────────┤
        │                     │
        │       STACK         │  ← Local variables, function calls
        │  (grows upward)     │
        └─────────────────────┘

14.3 Allocating Memory with malloc()

The malloc() function allocates a block of memory of specified size and returns a void pointer to it.

#include <stdlib.h>
int *ptr;
ptr = (int *)malloc(10 * sizeof(int));  // Allocate space for 10 integers

if (ptr == NULL) {
    printf("Memory allocation failed!\n");
    exit(1);
}

📝 Worked-Out Problem 14.1

Using malloc to allocate array dynamically:

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

int main() {
    int *arr;
    int n, i, sum = 0;
    
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    arr = (int *)malloc(n * sizeof(int));
    
    if (arr == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }
    
    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        sum += arr[i];
    }
    
    printf("Sum = %d\n", sum);
    printf("Average = %.2f\n", (float)sum / n);
    
    free(arr);  // Free allocated memory
    return 0;
}

Output:
Enter the number of elements: 5
Enter 5 elements:
10 20 30 40 50
Sum = 150
Average = 30.00

14.4 Allocating Multiple Blocks with calloc()

calloc() allocates memory for an array of elements, each of specified size, and initializes all bytes to zero.

int *ptr;
ptr = (int *)calloc(10, sizeof(int));  // Allocate and zero-initialize 10 integers

📝 Worked-Out Problem 14.2

Using calloc for array allocation:

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

int main() {
    int *arr;
    int n, i;
    
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    arr = (int *)calloc(n, sizeof(int));
    
    if (arr == NULL) {
        printf("Memory allocation failed!\n");
        return 1;
    }
    
    // calloc initializes to zero automatically
    printf("Initial values (all zeros):\n");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    
    printf("Enter %d values:\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    
    printf("You entered:\n");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    
    free(arr);
    return 0;
}

Output:
Enter the number of elements: 5
Initial values (all zeros):
0 0 0 0 0
Enter 5 values:
10 20 30 40 50
You entered:
10 20 30 40 50

14.5 Releasing Memory with free()

Always release dynamically allocated memory when it's no longer needed to prevent memory leaks.

free(ptr);  // ptr must point to memory allocated by malloc/calloc/realloc

⚠️ Important:

Never free memory that hasn't been allocated dynamically.
Never use memory after it has been freed (dangling pointer).
Set pointer to NULL after freeing to avoid accidental use.

14.6 Altering Memory Size with realloc()

realloc() changes the size of previously allocated memory, preserving the existing content.

int *new_ptr;
new_ptr = (int *)realloc(old_ptr, new_size * sizeof(int));

📝 Worked-Out Problem 14.3

Using realloc to resize allocated memory:

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

int main() {
    char *buffer;
    int size = 20;
    
    buffer = (char *)malloc(size * sizeof(char));
    if (buffer == NULL) {
        printf("Initial allocation failed\n");
        return 1;
    }
    
    strcpy(buffer, "Hello World");
    printf("Buffer: %s\n", buffer);
    printf("Current size: %d bytes\n", size);
    
    // Need more space
    size = 50;
    buffer = (char *)realloc(buffer, size * sizeof(char));
    
    if (buffer == NULL) {
        printf("Reallocation failed\n");
        return 1;
    }
    
    strcat(buffer, " - This is a longer string");
    printf("After realloc: %s\n", buffer);
    printf("New size: %d bytes\n", size);
    
    free(buffer);
    return 0;
}

Output:
Buffer: Hello World
Current size: 20 bytes
After realloc: Hello World - This is a longer string
New size: 50 bytes

14.7 Self-Referential Structures

A self-referential structure contains a pointer to another structure of the same type. This is the foundation of linked lists.

struct node {
    int data;              // data field
    struct node *next;     // pointer to next node (self-referential)
};

A linked list with three nodes:

    ┌─────────┬─────┐    ┌─────────┬─────┐    ┌─────────┬─────┐
    │ data: 10│ next│───→│ data: 20│ next│───→│ data: 30│ next│───→ NULL
    └─────────┴─────┘    └─────────┴─────┘    └─────────┴─────┘
         Node1                Node2                Node3

14.8 Creating a Linked List

📝 Worked-Out Problem 14.4

Creating and traversing a linked list:

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

struct node {
    int data;
    struct node *next;
};

struct node *create_list() {
    struct node *head = NULL, *temp = NULL, *new_node;
    int value;
    
    printf("Enter numbers (-999 to stop):\n");
    scanf("%d", &value);
    
    while (value != -999) {
        new_node = (struct node *)malloc(sizeof(struct node));
        if (new_node == NULL) {
            printf("Memory allocation failed\n");
            return head;
        }
        
        new_node->data = value;
        new_node->next = NULL;
        
        if (head == NULL) {
            head = new_node;  // First node
            temp = head;
        } else {
            temp->next = new_node;  // Link new node
            temp = new_node;
        }
        
        scanf("%d", &value);
    }
    
    return head;
}

void display_list(struct node *head) {
    struct node *temp = head;
    
    if (temp == NULL) {
        printf("List is empty\n");
        return;
    }
    
    printf("Linked List: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int count_nodes(struct node *head) {
    int count = 0;
    struct node *temp = head;
    
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}

int main() {
    struct node *head;
    
    head = create_list();
    display_list(head);
    printf("Number of nodes: %d\n", count_nodes(head));
    
    return 0;
}

Output:
Enter numbers (-999 to stop):
10 20 30 40 50 -999
Linked List: 10 20 30 40 50
Number of nodes: 5

14.9 Inserting a Node in a Linked List

Insertion can occur at the beginning, at the end, or at a specific position.

📝 Worked-Out Problem 14.5

Inserting nodes in a linked list:

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

struct node {
    int data;
    struct node *next;
};

struct node *insert_beginning(struct node *head, int value) {
    struct node *new_node = (struct node *)malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = head;
    return new_node;
}

struct node *insert_end(struct node *head, int value) {
    struct node *new_node = (struct node *)malloc(sizeof(struct node));
    struct node *temp = head;
    
    new_node->data = value;
    new_node->next = NULL;
    
    if (head == NULL)
        return new_node;
    
    while (temp->next != NULL)
        temp = temp->next;
    
    temp->next = new_node;
    return head;
}

struct node *insert_after(struct node *head, int key, int value) {
    struct node *temp = head, *new_node;
    
    while (temp != NULL && temp->data != key)
        temp = temp->next;
    
    if (temp == NULL) {
        printf("Key %d not found\n", key);
        return head;
    }
    
    new_node = (struct node *)malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = temp->next;
    temp->next = new_node;
    
    return head;
}

void display_list(struct node *head) {
    struct node *temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    struct node *head = NULL;
    
    head = insert_end(head, 20);
    head = insert_end(head, 30);
    head = insert_end(head, 40);
    printf("After inserting at end: ");
    display_list(head);
    
    head = insert_beginning(head, 10);
    printf("After inserting at beginning: ");
    display_list(head);
    
    head = insert_after(head, 30, 35);
    printf("After inserting 35 after 30: ");
    display_list(head);
    
    return 0;
}

Output:
After inserting at end: 20 30 40
After inserting at beginning: 10 20 30 40
After inserting 35 after 30: 10 20 30 35 40

14.10 Deleting a Node from a Linked List

📝 Worked-Out Problem 14.6

Deleting nodes from a linked list:

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

struct node {
    int data;
    struct node *next;
};

struct node *delete_first(struct node *head) {
    struct node *temp;
    
    if (head == NULL) {
        printf("List is empty\n");
        return NULL;
    }
    
    temp = head;
    head = head->next;
    free(temp);
    
    return head;
}

struct node *delete_last(struct node *head) {
    struct node *temp = head, *prev = NULL;
    
    if (head == NULL) {
        printf("List is empty\n");
        return NULL;
    }
    
    if (head->next == NULL) {
        free(head);
        return NULL;
    }
    
    while (temp->next != NULL) {
        prev = temp;
        temp = temp->next;
    }
    
    prev->next = NULL;
    free(temp);
    
    return head;
}

struct node *delete_key(struct node *head, int key) {
    struct node *temp = head, *prev = NULL;
    
    if (head == NULL)
        return NULL;
    
    // If head node itself holds the key
    if (temp != NULL && temp->data == key) {
        head = temp->next;
        free(temp);
        return head;
    }
    
    // Search for the key
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == NULL) {
        printf("Key %d not found\n", key);
        return head;
    }
    
    prev->next = temp->next;
    free(temp);
    
    return head;
}

void display_list(struct node *head) {
    struct node *temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    struct node *head = NULL;
    int i;
    
    // Create a list: 10 20 30 40 50
    for (i = 10; i <= 50; i += 10)
        head = insert_end(head, i);
    
    printf("Original list: ");
    display_list(head);
    
    head = delete_first(head);
    printf("After deleting first: ");
    display_list(head);
    
    head = delete_last(head);
    printf("After deleting last: ");
    display_list(head);
    
    head = delete_key(head, 30);
    printf("After deleting 30: ");
    display_list(head);
    
    return 0;
}

Output:
Original list: 10 20 30 40 50
After deleting first: 20 30 40 50
After deleting last: 20 30 40
After deleting 30: 20 40

14.11 Types of Linked Lists

Singly Linked List

Each node points to the next node; traversal is only forward.

Doubly Linked List

Each node has pointers to both next and previous nodes.

struct dnode {
    int data;
    struct dnode *prev;
    struct dnode *next;
};

Circular Linked List

The last node points back to the first node, forming a circle.

Circular Doubly Linked List

Combines both features: circular with forward and backward pointers.

Types of Linked Lists:

Singly:      [data|next] → [data|next] → [data|next] → NULL

Doubly:      NULL ← [prev|data|next] ↔ [prev|data|next] ↔ [prev|data|next] → NULL

Circular:    [data|next] → [data|next] → [data|next] ──┐
             ↑                                            │
             └────────────────────────────────────────────┘

Circular
Doubly:      ┌───────────────────────────────────────────┐
             ↓                                           │
             [prev|data|next] ↔ [prev|data|next] ↔ [prev|data|next]
             ↑                                           │
             └───────────────────────────────────────────┘

14.12 Advantages of Linked Lists

Dynamic size: Can grow or shrink during program execution
No memory waste: Allocates exactly the memory needed
Easy insertion/deletion: Only pointers need to be rearranged
Flexibility: Can be used to implement stacks, queues, trees, etc.

14.13 Disadvantages of Linked Lists

Sequential access only: Cannot access elements randomly like arrays
Extra memory: Each node requires additional memory for pointer(s)
Slower traversal: Accessing elements requires following pointers

Important Points to Remember

Always check if memory allocation succeeded (return value != NULL).
Free dynamically allocated memory when no longer needed to prevent memory leaks.
Never free memory that hasn't been allocated dynamically.
After freeing, set pointer to NULL to avoid dangling pointer issues.
In linked lists, always maintain the head pointer to access the list.
When inserting/deleting, be careful with pointer order to avoid losing nodes.
Always check for NULL before dereferencing pointers.
The last node's next pointer must be NULL to mark the end of list.

Chapter Exercises

Review Questions

State true or false:
a) Dynamically allocated memory can only be accessed using pointers.
b) calloc() is used to change memory allocation previously allocated with malloc().
c) Memory should be freed when it is no longer required.
d) Only one call to free() is needed to release an entire array allocated with calloc().
e) The link field in a linked list always points to the successor.
f) When realloc() reserves a new block, the contents of the old block are deleted.
g) In a linked list, nodes need not be physically contiguous in memory.
What is a linked list? How is it represented?
What is dynamic memory allocation? How does it help?
What is the principal difference between malloc() and calloc()?
Why is a linked list called a dynamic data structure?
Describe different types of linked lists.
What does ptr = (int *)malloc(sizeof(int)); achieve?

Multiple Choice Questions

Which memory management function releases allocated memory?
a) delete()
b) release()
c) free()
d) None
Which principle is stack based on?
a) First In First Out
b) Last In First Out
c) No restriction
d) None
________ is free memory space available for dynamic allocation.
a) Stack
b) Queue
c) Heap
d) Permanent storage
In a ________ linked list, the last node points to the first node.
a) Singly
b) Doubly
c) Circular
d) None
What does sizeof operator return?
a) Size in bytes
b) Size in bits
c) Number of elements
d) Address

Debugging Exercises

Find errors in the following code segments:

int *ptr = (int *)malloc(sizeof(int));
*ptr = 25;
free(ptr);
*ptr = 30;  // Error?

int *arr = (int *)malloc(5 * sizeof(int));
free(arr[0]);  // Error?

struct node *p = (struct node *)malloc(sizeof(struct node));
p->data = 10;
p->next = p;  // Logical error?

int *ptr = (int *)malloc(sizeof(int));
ptr = NULL;
free(ptr);  // Is this valid?

Programming Exercises

Write a program to create a linked list and print it using both recursive and iterative methods.
Write a menu-driven program to create a linked list of students and perform operations: display, count, edit, and delete.
Write recursive and non-recursive functions to reverse a linked list.
Create an interactive program to maintain a linked list of customer names and phone numbers with add/delete features.
Modify the above program to maintain the list in alphabetical order.
Write a program to combine two sorted linked lists into a third sorted list.
Create a circular linked list with functions to count nodes, display contents, and locate a given node.
Construct an ordered doubly linked list and write out the contents.
Write a function to traverse a singly linked list in reverse order.
Write a function to merge two ordered singly linked lists into a third ordered list.
Write a function to find the last node of a linked list.
Write a function to count the total number of nodes in a linked list.
Write functions to implement a doubly linked list with insert, delete, and find operations.

Interview Questions

How can you find the size of a variable without using sizeof?
What will be the output of: printf("Address of main = %p", main);
What is a wild pointer?
What is a dangling pointer?
What is the difference between NULL and NUL?
What is a restricted pointer?
What is the main difference between stack and queue?
How do you detect memory leaks in C programs?
What is the difference between malloc() and calloc()?
Write code to reverse a linked list iteratively.

Case Study 1: Building a Sorted Linked List

📝 Case Study: Inserting in sorted order

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

struct node {
    int data;
    struct node *next;
};

struct node *insert_sorted(struct node *head, int value) {
    struct node *new_node, *current, *prev = NULL;
    
    new_node = (struct node *)malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = NULL;
    
    if (head == NULL)
        return new_node;
    
    current = head;
    
    // Find position to insert
    while (current != NULL && current->data < value) {
        prev = current;
        current = current->next;
    }
    
    if (prev == NULL) {  // Insert at beginning
        new_node->next = head;
        return new_node;
    } else {              // Insert in middle or end
        prev->next = new_node;
        new_node->next = current;
        return head;
    }
}

void display(struct node *head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

int main() {
    struct node *head = NULL;
    int value;
    
    printf("Enter numbers to insert (-1 to stop):\n");
    scanf("%d", &value);
    
    while (value != -1) {
        head = insert_sorted(head, value);
        scanf("%d", &value);
    }
    
    printf("Sorted list: ");
    display(head);
    
    return 0;
}

Output:
Enter numbers to insert (-1 to stop):
50 30 40 10 20 -1
Sorted list: 10 20 30 40 50

Case Study 2: Implementing a Stack using Linked List

📝 Case Study: Stack operations with linked list

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

struct node {
    int data;
    struct node *next;
};

struct node *push(struct node *top, int value) {
    struct node *new_node = (struct node *)malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = top;
    return new_node;
}

struct node *pop(struct node *top) {
    struct node *temp;
    
    if (top == NULL) {
        printf("Stack underflow!\n");
        return NULL;
    }
    
    temp = top;
    printf("Popped: %d\n", top->data);
    top = top->next;
    free(temp);
    
    return top;
}

void display(struct node *top) {
    if (top == NULL) {
        printf("Stack is empty\n");
        return;
    }
    
    printf("Stack: ");
    while (top != NULL) {
        printf("%d ", top->data);
        top = top->next;
    }
    printf("\n");
}

int main() {
    struct node *stack = NULL;
    int choice, value;
    
    while (1) {
        printf("\n1. Push\n2. Pop\n3. Display\n4. Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter value to push: ");
                scanf("%d", &value);
                stack = push(stack, value);
                break;
            case 2:
                stack = pop(stack);
                break;
            case 3:
                display(stack);
                break;
            case 4:
                exit(0);
        }
    }
    
    return 0;
}

Case Study 3: Implementing a Queue using Linked List

📝 Case Study: Queue operations with linked list

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

struct node {
    int data;
    struct node *next;
};

struct queue {
    struct node *front;
    struct node *rear;
};

struct queue* create_queue() {
    struct queue *q = (struct queue *)malloc(sizeof(struct queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(struct queue *q, int value) {
    struct node *new_node = (struct node *)malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = NULL;
    
    if (q->rear == NULL) {
        q->front = q->rear = new_node;
        return;
    }
    
    q->rear->next = new_node;
    q->rear = new_node;
}

int dequeue(struct queue *q) {
    struct node *temp;
    int value;
    
    if (q->front == NULL) {
        printf("Queue is empty\n");
        return -1;
    }
    
    temp = q->front;
    value = temp->data;
    q->front = q->front->next;
    
    if (q->front == NULL)
        q->rear = NULL;
    
    free(temp);
    return value;
}

void display(struct queue *q) {
    struct node *temp = q->front;
    
    if (temp == NULL) {
        printf("Queue is empty\n");
        return;
    }
    
    printf("Queue: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    struct queue *q = create_queue();
    int choice, value;
    
    while (1) {
        printf("\n1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter value to enqueue: ");
                scanf("%d", &value);
                enqueue(q, value);
                break;
            case 2:
                value = dequeue(q);
                if (value != -1)
                    printf("Dequeued: %d\n", value);
                break;
            case 3:
                display(q);
                break;
            case 4:
                exit(0);
        }
    }
    
    return 0;
}