Pointers & Dynamic Memory: Allocation, Arithmetic, and Linked Structures

TAKEAWAYS:

• Pointers store memory addresses and enable indirect access to variables, arrays, and functions.
• Dynamic memory allocation (malloc, calloc) allocates memory at runtime, while free releases it to prevent leaks.
• Pointer arithmetic allows traversal of arrays and contiguous memory blocks (e.g., strings, structs).
• Linked structures (lists, trees) rely on pointers to dynamically link nodes, enabling flexible growth and shrinking.
• Memory leaks and dangling pointers are common pitfalls; always validate pointers before dereferencing.
• Real-world applications include managing user data in apps (e.g., Pathao’s ride queues) and optimizing performance in games (e.g., dynamic terrain loading).

---

1. Pointers: The Foundation of Dynamic Memory

Pointers are variables that store memory addresses of other variables. They enable indirect access, efficient data manipulation, and dynamic memory management.

1.1 How Pointers Work

• A pointer variable holds the address (location in RAM) of another variable.
• The & operator gives the address of a variable, while * declares a pointer or dereferences it.
• Example:

  int x = 10;
  int *ptr = &x;  // ptr stores the address of x
  printf("%d", *ptr);  // Output: 10 (dereferencing ptr)
  

1.2 Pointer Arithmetic

Pointers can be incremented/decremented to traverse contiguous memory (e.g., arrays, strings).

• ptr++ moves the pointer to the next memory location of the same data type.
• Example:

  int arr[3] = {10, 20, 30};
  int *ptr = arr;  // ptr points to arr[0]
  printf("%d", *(ptr + 1));  // Output: 20 (arr[1])
  

VISUAL: Pointer Arithmetic in an Array

```figure
{"type":"array","values":[10,20,30],"pointers":{"0":"ptr = &arr[0]","1":"ptr + 1","2":"ptr + 2"},"caption":"Memory layout of `arr` with pointer arithmetic (ptr = &arr[0])"}

1.3 Pointers to Pointers (Double Pointers)

Used for complex data structures (e.g., 2D arrays, function pointers).

• Example:

  int x = 100;
  int *ptr = &x;
  int **pptr = &ptr;  // pptr points to ptr
  printf("%d", **pptr);  // Output: 100
  

---

2. Dynamic Memory Allocation

Static memory (e.g., arrays declared with int arr[10]) has fixed size. Dynamic memory allocates memory at runtime using:

• malloc(): Allocates uninitialized memory.
• calloc(): Allocates and initializes memory to zero.
• realloc(): Resizes previously allocated memory.
• free(): Releases memory to avoid leaks.

2.1 malloc() and calloc()

Example: Dynamic Array

int *arr = (int*)malloc(5 * sizeof(int));  // Allocates space for 5 integers
if (arr == NULL) { printf("Memory allocation failed!"); exit(1); }
arr[0] = 10;  // Access like a normal array
free(arr);    // Release memory

VISUAL: Memory Before/After malloc

```mermaid
graph LR
    A["Before malloc"] --> B["Stack: x (unallocated)"]
    C["After malloc"] --> D["Heap: arr[0..4] (allocated)"]
    D --> E["arr[0] = 10"]

2.2 Common Pitfalls

1. Memory Leaks: Forgetting to free() allocated memory.

   int *ptr = malloc(100 * sizeof(int));
   // ... use ptr ...
   // ptr is never freed! Leak occurs.
   

2. Dangling Pointers: Using a pointer after free().

   int *ptr = malloc(sizeof(int));
   free(ptr);
   *ptr = 5;  // Undefined behavior!
   

3. Invalid Pointers: Dereferencing NULL or uninitialized pointers.

   int *ptr;
   printf("%d", *ptr);  // Crash!
   

Exam Tip: Always check if malloc()/calloc() returns NULL before use.

---

3. Pointers and Strings

Strings in C are null-terminated character arrays. Pointers simplify string manipulation.

• Example:

  char str[] = "Hello";
  char *ptr = str;  // ptr points to 'H'
  while (*ptr != '\0') { printf("%c", *ptr++); }  // Prints "Hello"
  

VISUAL: String Traversal with Pointers

```figure
{"type":"linked-list","values":["H","e","l","l","o","\\0"],"pointers":{"0":"ptr = str","1":"ptr++ (after *ptr = 'H')","5":"ptr at '\\0' (termination)"},"caption":"String traversal: `while (*ptr != '\\0')` prints 'H', 'e', 'l', 'l', 'o'"}

---

4. Linked Lists: Real-World Application

Linked lists use pointers to dynamically link nodes. Example: Pathao’s ride queue.

• Each node contains:
  • Data (e.g., ride request details).
  • Pointer to the next node.

Code Example: Singly Linked List

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

Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

VISUAL: Linked List Insertion

Trace: Inserting 30 at the End

---

5. Dynamic Memory in Real-World Systems

In the Real World

1. Pathao’s Ride Queue:

   • Uses a linked list to manage pending ride requests dynamically. New requests are appended to the end (O(1) time), and the front is dequeued when a driver accepts (O(1)).
   • Why pointers? Static arrays would waste memory if unused slots exist.

2. Khalti’s Transaction Logs:

   • Dynamically allocates memory for each transaction record (e.g., malloc for Transaction structs). Old logs are free()d after processing to save space.
   • Why calloc? Ensures fields like amount start at 0 to avoid garbage values.

3. Ncell’s Call Routing:

   • Uses pointers to function tables to route calls to different services (e.g., *123# for balance). The system checks a pointer array to decide which function to call.
   • Example:

     void (*serviceFunctions[])(void) = {checkBalance, recharge, ...};
     serviceFunctions[0]();  // Calls checkBalance
     

---

6. Exam Tip: How to Score Full Marks

1. Define Clearly:
   • Start with definitions (e.g., "A pointer is a variable that stores the memory address of another variable.").
2. Show Code + Trace:
   • Always include a short code snippet and a step-by-step trace table (like the linked list example above).
3. Highlight Pitfalls:
   • Examiners love discussions on memory leaks, dangling pointers, and NULL checks.
4. Compare malloc vs calloc:
   • Use a table (as shown earlier) to contrast initialization and use cases.
5. Link to Applications:
   • Relate dynamic memory to real systems (e.g., Pathao’s queues, Khalti’s logs). Even if not asked, this adds depth.

Common Exam Questions:

• "Explain dynamic memory allocation with malloc and free." → Must show code + trace.
• "How do pointers enable linked lists?" → Draw the structure and explain next pointers.
• "What are memory leaks? How to avoid them?" → Discuss free() and validation.

---

Final Note: Pointers are powerful but dangerous. Always validate pointers before dereferencing, and free memory when done to avoid leaks. Practice with small programs (e.g., dynamic arrays, linked lists) to master the concepts.