# DSA: Basics of Recursion, Pointers, and Dynamic Allocation

### Recursion in C

Recursion in C is a technique where a function calls itself in order to solve a problem. Each time the function calls itself, a new stack frame is created for that call, containing its own set of local variables. This continues until a base condition is met, at which point the function stops calling itself and the stack unwinds, resolving each call in reverse order.

Here's a simple recursive function to compute the factorial of a number:

```c
#include <stdio.h>

// Function to calculate factorial using recursion
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // Base case
    }
    return n * factorial(n - 1); // Recursive case
}

int main() {
    int num = 5;
    int result = factorial(num);
    printf("Factorial of %d is %d\n", num, result);
    return 0;
}
```

**Factorial of 5 Using a Function Call Stack**

To understand how the factorial of 5 is computed using recursion, let's visualize the function call stack.

#### Function Call Stack for `factorial(5)`

```c
    Stack Frame
    -----------
    factorial(5)
    n = 5
    return 5 * factorial(4)
    -----------           5 * factorial(4)

    Stack Frame
    -----------
    factorial(4)
    n = 4
    return 4 * factorial(3)
    -----------           5 * 4 * factorial(3)

    Stack Frame
    -----------
    factorial(3)
    n = 3
    return 3 * factorial(2)
    -----------           5 * 4 * 3 * factorial(2)

    Stack Frame
    -----------
    factorial(2)
    n = 2
    return 2 * factorial(1)
    -----------           5 * 4 * 3 * 2 * factorial(1)

    Stack Frame
    -----------
    factorial(1)
    n = 1
    return 1 (base case)
    -----------           5 * 4 * 3 * 2 * 1 = 120
```

**Explanation of Recursion and Local Variables**

**Initial Call**: `factorial(5)` is called.

1. * **Local Variable**: `n = 5`
        
    * The function checks if `n` is 0 or 1. Since it is not, it proceeds to the recursive call: `return 5 * factorial(4)`.
        
2. **First Recursive Call**: `factorial(4)` is called.
    
    * **Local Variable**: `n = 4`
        
    * Again, it checks if `n` is 0 or 1. Since it is not, it proceeds to the recursive call: `return 4 * factorial(3)`.
        
3. **Second Recursive Call**: `factorial(3)` is called.
    
    * **Local Variable**: `n = 3`
        
    * The function proceeds to the recursive call: `return 3 * factorial(2)`.
        
4. **Third Recursive Call**: `factorial(2)` is called.
    
    * **Local Variable**: `n = 2`
        
    * The function proceeds to the recursive call: `return 2 * factorial(1)`.
        
5. **Fourth Recursive Call**: `factorial(1)` is called.
    
    * **Local Variable**: `n = 1`
        
    * This time, the base case is met (since `n` is 1), and the function returns 1.
        
6. **Unwinding the Stack**:
    
    * The return value of `factorial(1)` (which is 1) is passed to `factorial(2)`.
        
    * `factorial(2)` returns `2 * 1 = 2`.
        
    * The return value of `factorial(2)` (which is 2) is passed to `factorial(3)`.
        
    * `factorial(3)` returns `3 * 2 = 6`.
        
    * The return value of `factorial(3)` (which is 6) is passed to `factorial(4)`.
        
    * `factorial(4)` returns `4 * 6 = 24`.
        
    * The return value of `factorial(4)` (which is 24) is passed to `factorial(5)`.
        
    * `factorial(5)` returns `5 * 24 = 120`.
        

Each recursive call creates a new stack frame with its own copy of the local variable `n`. When the base case is met, the stack starts to unwind, resolving each recursive call and propagating the results back up the call stack until the initial call is resolved.

**Recursive Code to Find the Largest and Smallest Elements in an Array**

Here's a recursive function to find the largest and smallest elements in an array:

```c
#include <stdio.h>
#include <limits.h>

// Function to find the largest element in the array using recursion
int findLargest(int arr[], int n) {
    if (n == 1) {
        return arr[0];
    }
    int max = findLargest(arr, n - 1);
    if (arr[n - 1] > max) {
        return arr[n - 1];
    } else {
        return max;
    }
}

// Function to find the smallest element in the array using recursion
int findSmallest(int arr[], int n) {
    if (n == 1) {
        return arr[0];
    }
    int min = findSmallest(arr, n - 1);
    if (arr[n - 1] < min) {
        return arr[n - 1];
    } else {
        return min;
    }
}

int main() {
    int arr[] = {34, 15, 88, 2, 23};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    int largest = findLargest(arr, n);
    int smallest = findSmallest(arr, n);
    
    printf("Largest element: %d\n", largest);
    printf("Smallest element: %d\n", smallest);
    
    return 0;
}
```

**Explanation of Recursion for an Array of Size 5**

Consider the array `arr[] = {34, 15, 88, 2, 23}`. The array size `n = 5`.

#### Function Call Stack for `findLargest(arr, 5)`

```c
    Stack Frame
    -----------
    findLargest(arr, 5)
    n = 5
    max = findLargest(arr, 4)
    return max (max(88, 23))
    -----------           88

    Stack Frame
    -----------
    findLargest(arr, 4)
    n = 4
    max = findLargest(arr, 3)
    return max (max(88, 2))
    -----------           88

    Stack Frame
    -----------
    findLargest(arr, 3)
    n = 3
    max = findLargest(arr, 2)
    return max (max(88, 88))
    -----------           88

    Stack Frame
    -----------
    findLargest(arr, 2)
    n = 2
    max = findLargest(arr, 1)
    return max (max(34, 15))
    -----------           34

    Stack Frame
    -----------
    findLargest(arr, 1)
    n = 1
    return arr[0]
    -----------           34
```

#### Function Call Stack for `findSmallest(arr, 5)`

```c
    Stack Frame
    -----------
    findSmallest(arr, 5)
    n = 5
    min = findSmallest(arr, 4)
    return min (min(2, 23))
    -----------           2

    Stack Frame
    -----------
    findSmallest(arr, 4)
    n = 4
    min = findSmallest(arr, 3)
    return min (min(2, 2))
    -----------           2

    Stack Frame
    -----------
    findSmallest(arr, 3)
    n = 3
    min = findSmallest(arr, 2)
    return min (min(15, 88))
    -----------           15

    Stack Frame
    -----------
    findSmallest(arr, 2)
    n = 2
    min = findSmallest(arr, 1)
    return min (min(15, 34))
    -----------           15

    Stack Frame
    -----------
    findSmallest(arr, 1)
    n = 1
    return arr[0]
    -----------           34
```

**Explanation of Recursion and Local Variables**

1. **Initial Call**: `findLargest(arr, 5)` is called.
    
    * **Local Variable**: `n = 5`
        
    * It makes a recursive call to `findLargest(arr, 4)`.
        
2. **First Recursive Call**: `findLargest(arr, 4)` is called.
    
    * **Local Variable**: `n = 4`
        
    * It makes a recursive call to `findLargest(arr, 3)`.
        
3. **Second Recursive Call**: `findLargest(arr, 3)` is called.
    
    * **Local Variable**: `n = 3`
        
    * It makes a recursive call to `findLargest(arr, 2)`.
        
4. **Third Recursive Call**: `findLargest(arr, 2)` is called.
    
    * **Local Variable**: `n = 2`
        
    * It makes a recursive call to `findLargest(arr, 1)`.
        
5. **Fourth Recursive Call**: `findLargest(arr, 1)` is called.
    
    * **Local Variable**: `n = 1`
        
    * This time, the base case is met, and the function returns `arr[0]` (which is 34).
        
6. **Unwinding the Stack**:
    
    * The return value of `findLargest(arr, 1)` (34) is passed to `findLargest(arr, 2)`.
        
    * `findLargest(arr, 2)` compares 34 and 15, returning the larger value, which is 34.
        
    * The return value of `findLargest(arr, 2)` (34) is passed to `findLargest(arr, 3)`.
        
    * `findLargest(arr, 3)` compares 34 and 88, returning the larger value, which is 88.
        
    * The return value of `findLargest(arr, 3)` (88) is passed to `findLargest(arr, 4)`.
        
    * `findLargest(arr, 4)` compares 88 and 2, returning the larger value, which is 88.
        
    * The return value of `findLargest(arr, 4)` (88) is passed to `findLargest(arr, 5)`.
        
    * `findLargest(arr, 5)` compares 88 and 23, returning the larger value, which is 88.
        

The same logic applies to finding the smallest element, with the difference being the comparison condition (`<` instead of `>`). Each recursive call creates a new stack frame with its own copy of the local variable `n`, and the stack unwinds once the base case is met, resolving each recursive call in reverse order.

### **Pointers in C**

Pointers are variables that store the memory address of another variable. They are a powerful feature in C that allow for efficient array manipulation, dynamic memory allocation, and the creation of complex data structures like linked lists.

**Defining Pointers**

To define a pointer, you specify the type of data the pointer will point to, followed by an asterisk (\*) and the pointer's name.

```c
int *ptr; // Pointer to an integer
char *cptr; // Pointer to a character
float *fptr; // Pointer to a float
```

**Assigning Addresses to Pointers**

Pointers are assigned the address of a variable using the address-of operator (`&`).

```c
int var = 10;
int *ptr;
ptr = &var; // ptr now holds the address of var
```

**Dereferencing Pointers**

Dereferencing a pointer means accessing the value stored at the memory address the pointer points to. This is done using the dereference operator (`*`).

```c
int var = 10;
int *ptr;
ptr = &var;
int value = *ptr; // value now holds 10, which is the value at the address ptr points to
```

Here’s a complete example that demonstrates defining, assigning, and dereferencing pointers in C:

```c
#include <stdio.h>

int main() {
    int var = 10;  // Define an integer variable
    int *ptr;      // Define a pointer to an integer

    ptr = &var;    // Assign the address of var to ptr

    printf("Address of var: %p\n", &var); // Print address of var
    printf("Address stored in ptr: %p\n", ptr); // Print address stored in ptr
    printf("Value of var: %d\n", var); // Print value of var
    printf("Value pointed to by ptr: %d\n", *ptr); // Dereference ptr to get value of var

    *ptr = 20;     // Change the value of var using the pointer
    printf("New value of var: %d\n", var); // Print new value of var

    return 0;
}
```

**Explanation**

1. **Defining a Pointer**:
    
    ```c
    int *ptr;
    ```
    
    This defines a pointer `ptr` that can hold the address of an integer variable.
    
2. **Assigning an Address to the Pointer**:
    
    ```c
    ptr = &var;
    ```
    
    The address of the variable `var` is assigned to the pointer `ptr` using the address-of operator `&`.
    
3. **Dereferencing the Pointer**:
    
    ```c
    int value = *ptr;
    ```
    
    The value stored at the address `ptr` points to is accessed using the dereference operator `*`. This assigns the value of `var` (which is 10) to the variable `value`.
    
4. **Changing the Value Using the Pointer**:
    
    ```c
    *ptr = 20;
    ```
    
    This changes the value at the address `ptr` points to. Since `ptr` points to `var`, the value of `var` is now changed to 20.
    

#### Pointer Arithmetic

Pointers can be incremented or decremented, which moves the pointer to the next or previous memory location of the type it points to.

```c
int arr[5] = {10, 20, 30, 40, 50};
int *p = arr;

printf("%d\n", *p);   // Output: 10
p++;                  // Move to the next integer
printf("%d\n", *p);   // Output: 20
```

#### Null Pointers

A null pointer is a pointer that is not assigned any address. It is defined using the macro `NULL`.

```c
int *ptr = NULL;
if (ptr == NULL) {
    printf("Pointer is null\n");
}
```

### Double Pointers in C

**Concept of Double Pointers**

A double pointer is a pointer that points to another pointer. It allows for an additional level of indirection.

```c
int var = 10;     // integer variable
int *ptr = &var;  // single pointer pointing to the integer variable
int **pptr = &ptr; // double pointer pointing to the single pointer
```

Let's use an example to explain how double pointers work. We will show real addresses and values.

```c
#include <stdio.h>

int main() {
    int var = 10;     // Step 1: Create an integer variable
    int *ptr = &var;  // Step 2: Create a pointer to the integer variable
    int **pptr = &ptr; // Step 3: Create a double pointer pointing to the pointer

    printf("Address of var: %p\n", &var); // Print the address of var
    printf("Value of var: %d\n", var); // Print the value of var

    printf("Address of ptr: %p\n", &ptr); // Print the address of ptr
    printf("Value stored in ptr (Address of var): %p\n", ptr); // Print the address stored in ptr
    printf("Value pointed to by ptr (Value of var): %d\n", *ptr); // Print the value pointed to by ptr

    printf("Address of pptr: %p\n", &pptr); // Print the address of pptr
    printf("Value stored in pptr (Address of ptr): %p\n", pptr); // Print the address stored in pptr
    printf("Value pointed to by pptr (Address of var): %p\n", *pptr); // Print the address pointed to by pptr
    printf("Value pointed to by the address stored in pptr (Value of var): %d\n", **pptr); // Print the value pointed to by the address stored in pptr

    return 0;
}
```

Assume the following memory addresses:

* `var`: Address = `0x100`, Value = `10`
    
* `ptr`: Address = `0x200`, Value = `0x100` (address of `var`)
    
* `pptr`: Address = `0x300`, Value = `0x200` (address of `ptr`)
    

```c
Memory Layout:

Address       Variable    Value
---------     --------    -----
0x100         var         10
0x200         ptr         0x100 (address of var)
0x300         pptr        0x200 (address of ptr)

ASCII Art Representation:

pptr -> Address: 0x300, Value: 0x200 (Address of ptr)
 |
 v
ptr  -> Address: 0x200, Value: 0x100 (Address of var)
  |
  v
var   -> Address: 0x100, Value: 10
```

**Explanation of Double Pointers**

1. **Step 1: Create an Integer Variable** `var`:
    
    ```c
    int var = 10;
    ```
    
    * **Memory Address**: `0x100`
        
    * **Value**: `10`
        
2. **Step 2: Create a Pointer** `ptr` to the Integer Variable:
    
    ```c
    int *ptr = &var;
    ```
    
    * **Memory Address**: `0x200`
        
    * **Value**: `0x100` (Address of `var`)
        
3. **Step 3: Create a Double Pointer** `pptr` Pointing to the Pointer `ptr`:
    
    ```c
    int **pptr = &ptr;
    ```
    
    * **Memory Address**: `0x300`
        
    * **Value**: `0x200` (Address of `ptr`)
        
4. **Accessing Values and Addresses**:
    
    * Address of `var`: `0x100`
        
    * Value of `var`: `10`
        
    * Address of `ptr`: `0x200`
        
    * Value stored in `ptr` (Address of `var`): `0x100`
        
    * Value pointed to by `ptr` (Value of `var`): `10`
        
    * Address of `pptr`: `0x300`
        
    * Value stored in `pptr` (Address of `ptr`): `0x200`
        
    * Value pointed to by `pptr` (Address of `var`): `0x100`
        
    * Value pointed to by the address stored in `pptr` (Value of `var`): `10`
        

**Use Case: Modifying a Pointer in a Function**

Double pointers are particularly useful when you need to modify the value of a pointer in a function.

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

// Function to allocate memory and assign the address to the double pointer
void allocateMemory(int **pptr) {
    *pptr = (int *)malloc(sizeof(int));
    **pptr = 100; // Assign a value to the allocated memory
}

int main() {
    int *ptr = NULL;
    allocateMemory(&ptr);

    if (ptr != NULL) {
        printf("Value allocated: %d\n", *ptr);
        free(ptr); // Free the allocated memory
    } else {
        printf("Memory allocation failed\n");
    }

    return 0;
}
```

**Explanation**

1. **Initial State**:
    
    * `ptr` is initially `NULL`.
        
2. **Function Call**:
    
    * `allocateMemory(&ptr)` is called.
        
    * `pptr` in `allocateMemory` is a pointer to `ptr`.
        
3. **Memory Allocation**:
    
    * `*pptr` points to the allocated memory.
        
    * `**pptr` assigns the value `100` to the allocated memory.
        
4. **Main Function**:
    
    * After `allocateMemory`, `ptr` points to the newly allocated memory with the value `100`.
        
    * The allocated memory is then freed.
        

```c
Before allocateMemory(&ptr):
ptr  -> Address: 0x400, Value: NULL

Inside allocateMemory:
pptr -> Address: 0x500, Value: 0x400 (Address of ptr)
 |
 v
ptr  -> Address: 0x400, Value: 0x600 (Address of allocated memory)
                       |
                       v
Allocated Memory       -> Address: 0x600, Value: 100

After allocateMemory:
ptr  -> Address: 0x400, Value: 0x600 (Address of allocated memory)
                       |
                       v
Allocated Memory       -> Address: 0x600, Value: 100
```

**Double Pointers: Linked List Node Insertion at Head**

**Node Definition**

A node in a linked list typically contains data and a pointer to the next node.

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

// Definition of a node in a linked list
struct Node {
    int data;
    struct Node* next;
};
```

**Creating and Linking Nodes**

We will create two nodes and link them, designating one as the head and the other as the tail.

```c
int main() {
    // Step 1: Create the first node (head)
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;

    // Step 2: Create the second node (tail)
    struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
    tail->data = 2;
    tail->next = NULL;

    // Step 3: Link the first node to the second node
    head->next = tail;

    // Print the initial list
    printf("Initial linked list:\n");
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    // Step 4: Pointer to the head pointer (Node **)
    struct Node** headPtr = &head;

    // Step 5: Call the function to insert a new node at the head
    insertAtHead(headPtr, 0);

    // Print the updated list
    printf("Updated linked list after inserting at head:\n");
    temp = *headPtr;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    // Free allocated memory
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}
```

**Function to Insert a Node at the Head**

```c
// Function to insert a new node at the head of the list
void insertAtHead(struct Node** head, int data) {
    // Step 1: Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    // Step 2: Assign data to the new node
    newNode->data = data;

    // Step 3: Set the next of the new node to the current head
    newNode->next = *head;

    // Step 4: Update the head pointer to the new node
    *head = newNode;
}
```

Let's assume the following memory addresses:

* `head`: Address = `0x100`, Value = `Address of first node`
    
* `first node`: Address = `0x200`, Data = `1`
    
* `tail`: Address = `0x300`, Data = `2`
    
* `new node`: Address = `0x400`, Data = `0`
    

#### Initial State

```c
Memory Layout:

Address       Variable   Value
---------     --------   -----
0x100         head       0x200 (Address of first node)
0x200         first node 1
0x204         next       0x300 (Address of tail)
0x300         tail       2
0x304         next       NULL

head -> 0x200
        +-------+     +-------+
        |  1    | --> |  2    | --> NULL
        +-------+     +-------+
        0x200          0x300
```

#### After Inserting a Node at the Head

```c
Memory Layout:

Address       Variable   Value
---------     --------   -----
0x100         head       0x400 (Address of new node)
0x200         first node 1
0x204         next       0x300 (Address of tail)
0x300         tail       2
0x304         next       NULL
0x400         new node   0
0x404         next       0x200 (Address of first node)

ASCII Art:

head -> 0x400
        +-------+     +-------+     +-------+
        |  0    | --> |  1    | --> |  2    | --> NULL
        +-------+     +-------+     +-------+
        0x400          0x200          0x300
```

**Detailed Explanation**

1. **Initial Setup**:
    
    * **Create the first node (head)**:
        
        ```c
        struct Node* head = (struct Node*)malloc(sizeof(struct Node));
        head->data = 1;
        head->next = NULL;
        ```
        
        * **Memory Address**: `0x200`
            
        * **Data**: `1`
            
        * **Next**: `NULL`
            
    * **Create the second node (tail)**:
        
        ```c
        struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
        tail->data = 2;
        tail->next = NULL;
        ```
        
        * **Memory Address**: `0x300`
            
        * **Data**: `2`
            
        * **Next**: `NULL`
            
    * **Link the first node to the second node**:
        
        ```c
        head->next = tail;
        ```
        
2. **Pointer to the Head Pointer**:
    
    ```c
    struct Node** headPtr = &head;
    ```
    
3. **Inserting a New Node at the Head**:
    
    * **Allocate memory for the new node**:
        
        ```c
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = 0;
        newNode->next = *head;
        ```
        
        * **Memory Address**: `0x400`
            
        * **Data**: `0`
            
        * **Next**: `0x200` (Address of the current head)
            
    * **Update the head pointer to the new node**:
        
        ```c
        *head = newNode;
        ```
        

**Updated Linked List**

* **Head** now points to the new node.
    
* The new node points to the previous head node.
    
* The previous head node points to the tail node.
    

**Without Double Pointers:**

Instead of using a `Node**` to pass the head pointer to the function, we can have the function return a new head pointer (`Node*`). The new head pointer can then be assigned to the head in the main function.

**Creating and Linking Nodes**

We will create two nodes and link them, designating one as the head and the other as the tail.

```c
int main() {
    // Step 1: Create the first node (head)
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;

    // Step 2: Create the second node (tail)
    struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
    tail->data = 2;
    tail->next = NULL;

    // Step 3: Link the first node to the second node
    head->next = tail;

    // Print the initial list
    printf("Initial linked list:\n");
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    // Step 4: Call the function to insert a new node at the head
    head = insertAtHead(head, 0);

    // Print the updated list
    printf("Updated linked list after inserting at head:\n");
    temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    // Free allocated memory
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}
```

**Function to Insert a Node at the Head**

```c
// Function to insert a new node at the head of the list
struct Node* insertAtHead(struct Node* head, int data) {
    // Step 1: Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    // Step 2: Assign data to the new node
    newNode->data = data;

    // Step 3: Set the next of the new node to the current head
    newNode->next = head;

    // Step 4: Return the new node as the new head
    return newNode;
}
```

Let's assume the following memory addresses:

* `head`: Address = `0x100`, Value = `Address of first node`
    
* `first node`: Address = `0x200`, Data = `1`
    
* `tail`: Address = `0x300`, Data = `2`
    
* `new node`: Address = `0x400`, Data = `0`
    

#### Initial State

```c
Memory Layout:

Address       Variable   Value
---------     --------   -----
0x100         head       0x200 (Address of first node)
0x200         first node 1
0x204         next       0x300 (Address of tail)
0x300         tail       2
0x304         next       NULL

head -> 0x200
        +-------+     +-------+
        |  1    | --> |  2    | --> NULL
        +-------+     +-------+
        0x200          0x300
```

#### After Inserting a Node at the Head

```c
Memory Layout:

Address       Variable   Value
---------     --------   -----
0x100         head       0x400 (Address of new node)
0x200         first node 1
0x204         next       0x300 (Address of tail)
0x300         tail       2
0x304         next       NULL
0x400         new node   0
0x404         next       0x200 (Address of first node)

ASCII Art:

head -> 0x400
        +-------+     +-------+     +-------+
        |  0    | --> |  1    | --> |  2    | --> NULL
        +-------+     +-------+     +-------+
        0x400          0x200          0x300
```

**Detailed Explanation**

1. **Initial Setup**:
    
    * **Create the first node (head)**:
        
        ```c
        struct Node* head = (struct Node*)malloc(sizeof(struct Node));
        head->data = 1;
        head->next = NULL;
        ```
        
        * **Memory Address**: `0x200`
            
        * **Data**: `1`
            
        * **Next**: `NULL`
            
    * **Create the second node (tail)**:
        
        ```c
        struct Node* tail = (struct Node*)malloc(sizeof(struct Node));
        tail->data = 2;
        tail->next = NULL;
        ```
        
        * **Memory Address**: `0x300`
            
        * **Data**: `2`
            
        * **Next**: `NULL`
            
    * **Link the first node to the second node**:
        
        ```c
        head->next = tail;
        ```
        
2. **Inserting a New Node at the Head**:
    
    * **Allocate memory for the new node**:
        
        ```c
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = 0;
        newNode->next = head;
        ```
        
        * **Memory Address**: `0x400`
            
        * **Data**: `0`
            
        * **Next**: `0x200` (Address of the current head)
            
    * **Return the new node as the new head**:
        
        ```c
        return newNode;
        ```
        
3. **Main Function Updates the Head**:
    
    * Assign the returned new node as the new head:
        
        ```c
        head = insertAtHead(head, 0);
        ```
        

**Updated Linked List**

* **Head** now points to the new node.
    
* The new node points to the previous head node.
    
* The previous head node points to the tail node.
    

This process demonstrates how to insert a new node at the head of a linked list using a `Node*` function that returns the new head, providing flexibility and control over the data structure.

### Dynamic Memory in C

Dynamic memory in C refers to memory that is allocated during runtime using functions from the standard library, such as `malloc`, `calloc`, `realloc`, and `free`. This memory is managed on the heap, allowing for flexible and efficient use of memory resources.

Here's a simple program that demonstrates dynamic memory allocation using `malloc`:

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

int main() {
    // Step 1: Declare a pointer
    int *ptr;

    // Step 2: Allocate memory dynamically
    ptr = (int *)malloc(sizeof(int));

    // Step 3: Check if the memory allocation was successful
    if (ptr == NULL) {
        printf("Memory allocation failed\n");
        return 1;
    }

    // Step 4: Assign a value to the allocated memory
    *ptr = 42;

    // Step 5: Print the value and the address
    printf("Value: %d\n", *ptr);
    printf("Address of allocated memory: %p\n", (void *)ptr);

    // Step 6: Free the allocated memory
    free(ptr);

    return 0;
}
```

**Process Memory Map Explanation**

The memory map of a process typically includes the following segments:

* **Code Segment**: Contains the executable code.
    
* **Data Segment**: Contains global and static variables.
    
* **Heap Segment**: Used for dynamic memory allocation.
    
* **Stack Segment**: Used for function call frames, local variables, and pointers.
    

Assume the following hypothetical memory addresses for illustration purposes:

* **Code Segment**: Starts at `0x400000`
    
* **Data Segment**: Starts at `0x600000`
    
* **Heap Segment**: Starts at `0x800000`
    
* **Stack Segment**: Starts at `0xFFFC0000` and grows downwards
    

**Process Memory Map with Dynamic Memory Allocation**

1. **Code Segment**:
    
    * The compiled code of the program is loaded here.
        
2. **Data Segment**:
    
    * Stores global and static variables.
        
3. **Heap Segment**:
    
    * Dynamically allocated memory using `malloc` is located here.
        
4. **Stack Segment**:
    
    * Stores function call frames and local variables.
        

**Memory Layout Example with Addresses and Values**

Let's assume the following addresses and values for our example:

* `ptr` (in `main` stack frame): Address = `0xFFFC0010`
    
* Allocated memory (in heap): Address = `0x80001000`, Value = `42`
    

#### Initial State (Before `malloc`)

```c
Memory Map:

Address          Segment         Variable/Value
-------------    -----------     -----------------
0x400000         Code            Program Code
0x600000         Data            Global/Static Variables
0x800000         Heap            <Empty>
0xFFFC0000       Stack           main()
                                +------------------+
                                | Return Address   |
                                |------------------|
                                | Other Local Vars |
                                |------------------|
                                | ptr              | --> Initially uninitialized
                                +------------------+
```

#### After `malloc`

```c
Memory Map:

Address          Segment         Variable/Value
-------------    -----------     -----------------
0x400000         Code            Program Code
0x600000         Data            Global/Static Variables
0x80001000       Heap            Value = 42
0xFFFC0000       Stack           main()
                                +------------------+
                                | Return Address   |
                                |------------------|
                                | Other Local Vars |
                                |------------------|
0xFFFC0010       ptr             0x80001000 (Address of allocated memory)
                                +------------------+
```

#### After Assignment

```c
Memory Map:

Address          Segment         Variable/Value
-------------    -----------     -----------------
0x400000         Code            Program Code
0x600000         Data            Global/Static Variables
0x80001000       Heap            Value = 42
0xFFFC0000       Stack           main()
                                +------------------+
                                | Return Address   |
                                |------------------|
                                | Other Local Vars |
                                |------------------|
0xFFFC0010       ptr             0x80001000 (Address of allocated memory)
                                +------------------+
```

**Detailed Explanation**

1. **Declare a Pointer**:
    
    ```c
    int *ptr;
    ```
    
    * **Memory Address**: `0xFFFC0010` (stack frame of `main`)
        
    * **Value**: Uninitialized
        
2. **Allocate Memory Dynamically**:
    
    ```c
    ptr = (int *)malloc(sizeof(int));
    ```
    
    * Allocates memory on the heap.
        
    * **Memory Address**: `0x80001000`
        
    * **Value**: `0x80001000` is stored in `ptr`.
        
3. **Check Memory Allocation**:
    
    ```c
    if (ptr == NULL) {
        printf("Memory allocation failed\n");
        return 1;
    }
    ```
    
    * Ensures `malloc` was successful.
        
4. **Assign a Value to Allocated Memory**:
    
    ```c
    *ptr = 42;
    ```
    
    * **Memory Address**: `0x80001000`
        
    * **Value**: `42`
        
5. **Print the Value and Address**:
    
    ```c
    printf("Value: %d\n", *ptr);
    printf("Address of allocated memory: %p\n", (void *)ptr);
    ```
    
    * Output:
        
        ```c
        Value: 42
        Address of allocated memory: 0x80001000
        ```
        
6. **Free the Allocated Memory**:
    
    ```c
    free(ptr);
    ```
    
    * Releases the memory allocated on the heap.
        

The pointer `ptr` resides in the stack frame of the `main` function, but it points to a memory location in the heap. This separation of pointer and allocated memory locations is crucial for understanding how dynamic memory management works in C. This approach provides flexibility in managing memory, especially for dynamic data structures and variable-sized data.