C Prerequisites for Data Structures

Variables, Data Types & Memory Layout

Every variable occupies real bytes in RAM. Understanding type sizes and memory layout is the absolute foundation before you write even the simplest data structure.

Data Type Size Explorer INTERACTIVE

Select a C type to see how many bytes it occupies in memory, its binary layout, and value range. All sizes shown for a 64-bit system.

Memory Layout — each box = 1 byte

Stack Frame Builder ANIMATE

Declare variables and watch them get placed on the stack at consecutive decreasing addresses (stack grows downward on x86-64). Notice how types of different sizes take up different amounts of space.

Stack (grows ↓)

Code

// Declare variables to see them here

Signed vs Unsigned CONCEPT

The MSB (most significant bit) acts as a sign bit in signed types. Same bit pattern, different interpretation!

8-bit: 0xFF = 11111111

          signed char:
          -1
        

          unsigned char:
          255
        

unsigned int u = 4294967295; // 2^32 - 1
signed int   s = -1;
// SAME 32 bits: 0xFFFFFFFF
// Use size_t for array indices!

sizeof() Operator REFERENCE

Always use sizeof(type) instead of hardcoding sizes. Code must be portable across architectures.

#include <stdio.h>
#include <stddef.h>

int main() {
  printf("%zu\n", sizeof(char));    // 1
  printf("%zu\n", sizeof(int));     // 4
  printf("%zu\n", sizeof(double));  // 8
  printf("%zu\n", sizeof(int*));    // 8 (64-bit)
  // ALWAYS use sizeof in malloc:
  // malloc(n * sizeof(int))  ✓
  // malloc(n * 4)            ✗
}

C Memory Regions — The Big Picture ARCHITECTURE

A running C program has 4 memory regions. Data structures live in different regions depending on how they're created.

          High addr
          Low addr
        
Stack
Local variables, function params, return addresses
Grows ↓ downward. Auto-freed on return.

            ↕ gap (unmapped — segfault zone)
          
Heap
malloc() / calloc() allocations
Grows ↑ upward. YOU must free() it.
BSS / Data Segment
Global & static variables
Text (Code) Segment
Your compiled program instructions

💡

Key rule: Linked lists, trees, and graphs use heap memory (malloc). Arrays declared locally use stack. Understanding this prevents 90% of segfaults and memory leaks.

Arrays — Contiguous Memory Blocks

Arrays are the simplest data structure and the foundation for stacks, queues, and hash tables. The key insight: arr[i] is literally pointer arithmetic.

Array Memory Visualizer INTERACTIVE

Arrays store elements at consecutive addresses. Accessing element arr[i] computes address base + i × sizeof(type) — this is O(1) random access!

Array in Memory — base address: 0x1000

int arr[] = {10, 25, 7, 42, 18, 3, 61};
// arr[i]  ≡  *(arr + i)
// &arr[i] ≡  arr + i  (address)
// addr of arr[i] = base + i × 4  (for int)
// Proof: arr[2] → 0x1000 + 2×4 = 0x1008

Search Algorithm Visualizer ANIMATE

Linear Search O(n)

Binary Search O(log n)

Scans every element one by one. Works on unsorted arrays. Worst case: n comparisons.

Array — scanning position highlighted

int linearSearch(int arr[], int n, int target) {
  for (int i = 0; i < n; i++) {
    if (arr[i] == target)
      return i;       // found!
  }
  return -1;           // not found
}   // O(n) worst case

2D Arrays — Row-Major Layout CONCEPT

2D arrays are stored as one contiguous block in row-major order. Critical for adjacency matrices in graphs. Click a cell to see its 1D memory offset.

2D View (click a cell)

Linear Memory (row-major)

int M[3][4];
// Address of M[r][c] = base + (r×COLS + c) × sizeof(int)
// M[1][2] offset = (1×4 + 2) × 4 = 24 bytes from base
// In memory: M[0][0] M[0][1] M[0][2] M[0][3]
//            M[1][0] M[1][1] M[1][2] M[1][3]  (contiguous!)

Pointers — The Heart of Data Structures

Without pointers there are no linked lists, no trees, no graphs. A pointer is just a variable that stores a memory address. That's it. Master this and everything else follows.

Pointer Visualizer INTERACTIVE

A pointer stores the address of another variable. Use & to get an address, * to dereference (follow the arrow to the value).

Memory Layout

int  x   = 99;         // at address 0x2004
int* ptr = &x;          // ptr holds 0x2004
printf("%d", *ptr);    // dereference → 99
*ptr = 200;            // changes x to 200
printf("%d", x);       // prints 200!

Pointer Arithmetic ANIMATE

When you do ptr++, the pointer advances by sizeof(type) bytes, not 1 byte. This is how array traversal, memcpy, and string operations work internally.

Array traversal via pointer

NULL Pointer & Safety DANGER

NULL means "points to nothing". ALWAYS check for NULL before dereferencing — NULL dereference is the most common segfault in student code.

☠️

Never do: *ptr without checking ptr != NULL first.

int* p = NULL;
// SAFE pattern:
if (p != NULL) {
  *p = 5;         // safe ✓
}
// In linked lists:
while (node != NULL) {
  node = node->next; // traverse
}

Pointer to Pointer (double pointer) ADVANCED

Used when a function needs to change which node the head pointer points to — e.g., inserting at the beginning of a linked list.

int  x  = 42;
int* p  = &x;    // points to x
int** pp = &p;  // points to p
// *pp  → p  (the pointer)
// **pp → 42 (the value)

// Used in linked list insertion:
void insert(Node** head, int val) {
  Node* n = newNode(val);
  n->next = *head;
  *head = n;  // modifies caller's head!
}

Quick Check QUIZ

Structures — Building Data Structure Nodes

Every node in a linked list, tree, or graph IS a struct. Structs group related data — they are the DNA of every data structure you'll implement.

Struct Memory Layout with Padding INTERACTIVE

The compiler adds padding bytes to satisfy alignment requirements (an 8-byte pointer must be at an 8-byte-aligned address). This affects sizeof(struct)!

Struct Layout in Memory

Memory bytes (each square = 1 byte)

Dot (.) vs Arrow (->) Operator ANIMATE

The -> operator dereferences a pointer AND accesses a field in one step. It's just shorthand for (*ptr).field. Click on fields to highlight!

// Direct struct variable
Node n;
n.data = 42;
n.next = NULL;
printf("%d", n.data); // 42

// Pointer to struct
Node* p = &n;
p->data = 42;         // (*p).data
p->next = NULL;
// p->x  ≡  (*p).x

typedef — Cleaner Syntax BEST PRACTICE

// Without typedef (verbose)
struct Node {
  int          data;
  struct Node* next;
};
struct Node* head;  // ugly!

// With typedef (preferred ✓)
typedef struct Node {
  int        data;
  struct Node* next; // must use struct here
} Node;
Node* head;         // clean!

Self-Referential Structs KEY CONCEPT

A struct can contain a pointer to another struct of the SAME type — this is how linked lists and trees work!

typedef struct TreeNode {
  int   data;
  struct TreeNode* left;  // left child
  struct TreeNode* right; // right child
} TreeNode;
// Each node points to more TreeNodes!
// This creates the tree structure.

Dynamic Memory Allocation

Linked lists, trees, and hash tables grow and shrink at runtime — they MUST use heap memory. malloc/calloc/free are the only tools for this in C.

Heap Allocator Simulator INTERACTIVE

malloc() asks the OS for memory on the heap. The returned pointer is the only way to access that memory. If you lose it (without freeing) — memory leak.

Stack

main()
head = NULL

Heap (malloc'd nodes)

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

Node* newNode(int data) {
  Node* n = (Node*) malloc(sizeof(Node));
  if (!n) { perror("malloc"); exit(1); } // ALWAYS check!
  n->data = data;
  n->next = NULL;
  return n;
}

malloc vs calloc vs realloc REFERENCE

// malloc — uninitialized garbage bytes
int* p = (int*)malloc(4 * sizeof(int));

// calloc — zero-initialized (safer default)
int* p = (int*)calloc(4, sizeof(int));

// realloc — resize (for dynamic arrays)
int* tmp = (int*)realloc(p, 8*sizeof(int));
if (!tmp) { free(p); exit(1); } // don't lose p!
p = tmp;

free(p);  // return to OS
p = NULL; // prevent dangling ptr!

Memory Leak Demo DANGER

Valgrind output — every BTech student should know how to read this.

$ ./program # click a button above

Linked List — Operations Visualized

This section puts everything together: structs + pointers + malloc. Watch each operation manipulate pointers step-by-step. This is the foundation before implementing stacks/queues as linked lists.

Singly Linked List Simulator FULL INTERACTIVE

Build a linked list node by node. Every operation is explained with the exact C pointer manipulation happening under the hood.

Linked List — head pointer shown on left

// Build a list by inserting values above

Traversal Pattern ESSENTIAL

The universal pattern for traversing any linked list. Used inside print, search, and length functions.

void printList(Node* head) {
  Node* curr = head;     // don't move head!
  while (curr != NULL) {
    printf("%d → ", curr->data);
    curr = curr->next;   // advance pointer
  }
  printf("NULL\n");
}
// ⚠ Never do: head = head->next
// You'd lose the entire list!

Free the Entire List MEMORY SAFETY

When done, free every single node. If you free head first, you lose access to the rest — classic mistake!

void freeList(Node* head) {
  Node* curr = head;
  while (curr != NULL) {
    Node* tmp = curr->next; // save next!
    free(curr);             // free current
    curr = tmp;             // advance safely
  }
}
// ⚠ free(head) directly = memory leak!

Functions, Call Stack & Pass-by-Reference

Every data structure operation (insert, delete, search) is a function. The critical distinction: C passes everything by value — to modify something, pass a pointer to it.

Call Stack Simulator INTERACTIVE

Each function call pushes a stack frame containing local variables and the return address. Stack frames are popped (destroyed) when the function returns.

Call Stack (grows ↓)

Active Code

Pass by Value vs Reference — Side by Side ANIMATE

This is the most common source of bugs in student implementations: forgetting to pass a pointer when you need to modify the original.

// By VALUE — copy made
void doubleIt(int x) {
  x = x * 2; // only local copy!
}
int a = 5;
doubleIt(a);
// a is still 5 — BUG!

// By REFERENCE — pointer passed
void doubleIt(int* x) {
  *x = *x * 2; // modifies original
}
int a = 5;
doubleIt(&a);
// a is now 10 ✓

Recursion — Solving Problems with Sub-Problems

Tree traversals, graph DFS, merge sort, and tower of Hanoi are all naturally recursive. Every recursive function needs: (1) a base case, (2) progress toward the base case, (3) a recursive call.

Factorial — Call Tree & Stack Depth INTERACTIVE

Watch how each recursive call pushes a new stack frame. The "unwinding" happens when the base case is hit and values return back up the call chain.

Recursion unwind trace

int factorial(int n) {
  // BASE CASE: prevents infinite recursion
  if (n <= 1) return 1;
  // RECURSIVE CASE: progress toward n=1
  return n * factorial(n - 1);
}
// Stack depth = n frames = O(n) space!

Fibonacci Tree — Overlapping Subproblems ANIMATE

The Fibonacci call tree reveals overlapping subproblems — fib(3) is computed multiple times! This motivates dynamic programming. Red nodes = redundant computations.

Fibonacci call tree — red = repeated subproblem

// Naive — exponential time O(2^n)
int fib(int n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2);
}
// Memoized — O(n) time
int memo[100] = {0};
int fibMemo(int n) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  return memo[n] = fibMemo(n-1) + fibMemo(n-2);
}

Recursion on a Linked List APPLICATION

Most tree/list operations are elegantly expressed recursively. This is the pattern used in tree traversals.

// Sum all values in a linked list
int sumList(Node* node) {
  if (node == NULL)     // base case
    return 0;
  return node->data     // current
       + sumList(node->next); // rest
}
// Think: sum = head + sum(tail)

Stack Overflow Risk DANGER

Recursion uses stack memory. A list of 10,000 nodes will create 10,000 stack frames — stack overflow! Use iteration for long lists.

// Iterative sum — O(1) stack space ✓
int sumListIter(Node* head) {
  int total = 0;
  while (head) {
    total += head->data;
    head = head->next;
  }
  return total;
}
// Use recursion for: trees, graphs (DFS)
// Use iteration for: linked list traversal

Sorting Algorithms — Visualized

Sorting is the gateway to algorithm analysis — understanding O(n²) vs O(n log n). Bubble, insertion, and selection sort are the prerequisite before merge sort (which requires recursion + arrays).

Sorting Algorithm Visualizer INTERACTIVE

Bubble Sort O(n²)

Selection Sort O(n²)

Insertion Sort O(n²)

Comparisons: 0 Swaps: 0

Press Sort to begin

Complexity Comparison ANALYSIS

Algorithm	Best	Average	Worst	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes ✓
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No ✗
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes ✓
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes ✓

Bitwise Operations

Used in hash functions, bloom filters, visited arrays in BFS/DFS, memory-efficient flags, and low-level optimizations. A bit array can store 32 boolean values in a single int.

Bit Operation Visualizer INTERACTIVE

See each operation on individual bits. For graph algorithms: a 32-bit unsigned int can replace a bool visited[32] array!

8-bit representation

Bit Tricks for Data Structures APPLICATIONS

// ── COMMON BIT TRICKS ──

// 1. Check if power of 2
if (n & (n-1) == 0) // power of 2

// 2. Check odd/even (faster than %)
if (n & 1) // odd

// 3. Multiply/divide by 2
n << 1; // n × 2
n >> 1; // n ÷ 2 (floor)

// 4. Swap without temp
a ^= b; b ^= a; a ^= b;

// ── BIT ARRAY (visited[] in BFS) ──

unsigned int visited = 0; // 32 nodes!

// Mark node i as visited
visited |= (1u << i);

// Check if node i is visited
if (visited & (1u << i)) { ... }

// Unmark node i
visited &= ~(1u << i);

// Count visited (Kernighan's trick)
int count = 0;
while (visited) {
  visited &= visited - 1; count++;
}

C Prerequisites forData Structures

C Prerequisites for
Data Structures