Dynamic Memory Allocation, Pointers, Structures & Linked Lists

Runtime Creation of Variables, Arrays & Objects

• Objective of the lecture
  • Show how to create variables, arrays and user-defined objects while the program is running ("dynamic" objects)
  • Contrast with "static" objects that must appear, named, in the source code (e.g.
    c int i; char tires[SIZE]; )
  • Real-world motivation: programs often need to deal with data whose size is not known at compile time (customer lists, transaction logs, etc.)

Static vs. Dynamic Objects

• Static (compile-time)
  • Declared with a name in source; storage reserved by the compiler
  • Size & lifetime fixed for entire run
  • Examples: int i; char tires[100]; struct Books book1;
• Dynamic (run-time)
  • Space obtained from the heap while the program executes
  • Size can be computed at run-time; lifetime manually controlled (allocate ➜ use ➜ free)
  • Obtained with
  • C: malloc, calloc, realloc, free
  • C++: new, delete

Core C Function – malloc

• Prototype: void *malloc(size_t bytes);
• Returns the address (as void *) of a block containing bytes bytes
• Must be cast to the appropriate pointer type in C (not required in C++)
• When done, pass pointer to free(ptr) to release memory back to the OS
• Memory-math formula
  • Desired number of elements: $n$
  • Size of single element: $\text{sizeof(type)}$
  • Bytes to request: $n \times \text{sizeof(type)}$

Example 1 – Building an Integer Array Dynamically

int *p1  = (int *) malloc(4 * sizeof(int));          // 4 ints
int a[4];                                             // static equivalent

int *p2  = (int *) malloc(sizeof a);                 // same – uses sizeof array
int *p3  = (int *) malloc(4 * sizeof *p3);           // sizeof dereferenced ptr

for (int n=0; n<4; ++n) p1[n] = n*n;                 // fill with squares
for (int n=0; n<4; ++n) printf("p1[%d]=%d\n", n, p1[n]);

free(p1); free(p2); free(p3);                        // ALWAYS free

• Highlights
  • sizeof *p3 lets the compiler figure out the element size → avoids repetition errors
  • Forgetting free leaks memory; the block remains reserved even after main ends if the OS doesn’t reclaim it

Example 2 – Dynamic Character Buffer for Strings

char  name[]       = "Ali";                         // static string
char *description  = malloc(200 * sizeof(char));     // 200-char buffer

strcpy(description, "Hello dynamic world!\n");
printf("Name: %s\nDesc: %s", name, description);
free(description);

• Format specifier %s expects a pointer to the first character of a C-string

C++ Alternative – new / delete

• Syntax: int *foo = new int[5]; (requests 5 ints)
• Integrates constructors / destructors; returns typed pointer, no cast
• Must later perform delete[] foo;
• C programs cannot use new; C++ can choose either new or malloc

Structures Recap

struct Books {
    char title[50];
    char author[50];
    char subject[100];
    int  book_id;
};

• Static instances (compile-time)

  struct Books book1, book2;           // dot (.) operator
  strcpy(book1.title, "C Primer");
  printf("%s", book1.title);

• Pointers to instances

  struct Books *ptr = &book1;         // arrow (->) operator
  printf("%s", ptr->title);

• Rule of thumb
  • obj.member ➜ obj is a named object
  • ptr->member ➜ ptr is a pointer

Passing a Structure to a Function

• Pass by address to avoid copying every field

void printBook(const struct Books *b) {
    printf("Title: %s\nID: %d\n", b->title, b->book_id);
}
...
printBook(&book1);
printBook(&book2);

Linked Lists – Dynamic, Self-Expanding Containers

• Motivation
  • Arrays: fixed size; expanding requires recompilation or realloc complications
  • Linked list: add/remove elements on-the-fly by relinking pointers
• Basic singly linked node

struct Node {
    int         data;     // payload (could be a full struct)
    struct Node *next;    // pointer to next node (NULL for last)
};

How a List Grows

1. Allocate first node ➜ head points to it
2. To append a new node
   • Node *n = malloc(sizeof *n);
   • Fill n->data
   • Set the current last node’s next to n
   • n->next = NULL
3. To traverse

for (Node *ptr = head; ptr != NULL; ptr = ptr->next)
    printf("%d\n", ptr->data);

Visual Model

• [data | next] ➜ [data | next] ➜ ... ➜ NULL
• End marker = 0 (a.k.a. NULL macro)
• Can be extended into doubly linked list by adding a prev pointer: [prev | data | next]

Sample Insertion Run

• Code inserted nodes with data: 10, 20, 30, 1, 40, 56
• Printed sequence (because insert routine placed each new node at the front): 56 40 1 30 20 10
• Demonstrates that order depends on algorithm (prepend vs. append)

Menu-Driven Linked List (Supplied Example)

• Operations implemented
  • Append
  • Add at beginning
  • Delete at position
  • Display
  • Size/Count
• Combines previously taught concepts: functions, loops, switch menu, dynamic allocation, pointer manipulation

Best Practices & Common Pitfalls

• Always check malloc/new return value for NULL (out of memory)
• Pair every malloc with exactly one free; every new with delete/delete[]
• Do not use memory after it has been freed (dangling pointer)
• Prefer sizeof *ptr over sizeof(type) to stay type-safe during refactoring
• When working with structures that own dynamic memory, consider encapsulation functions (init, destroy) or C++ constructors/destructors

Connections & Real-World Relevance

• Builds on earlier lectures (arrays, pointers, structures) by adding heap management
• Linked lists map directly to database records, OS job queues, network packet buffers
• Ethical / practical impact: proper memory handling prevents crashes & security vulnerabilities (e.g., leaks, buffer overflows)

Key Equations & Snippets to Memorize

• Requested bytes: $\text{bytes} = n \times \text{sizeof(type)}$
• Allocation + check

  T *ptr = malloc(n * sizeof *ptr);
  if (!ptr) { /* handle error */ }

• Freeing

  free(ptr);  ptr = NULL;   // NULL out to avoid dangling reference

• Traversal loop

  for (Node *p=head; p; p=p->next) use(p);

What to Review Before the Exam

• Syntax differences: . vs ->, malloc vs new, free vs delete
• Writing a minimal linked-list: node definition, insertion at head, traversal
• Calculating correct malloc size expressions
• Passing structures by pointer to functions & using const-correctness (const struct Books *b)
• Why forgetting to free causes leaks and why double-freeing causes undefined behavior