Programming & Data Structures

Subject 3 of 10 · C fundamentals, pointers, the classic data structures, and the complexity table that ties them together.

1. C Programming Basics

Data types and variables

A variable is a named storage location; its data type decides how many bytes it occupies and what operations are legal. Declaration introduces the variable, definition allocates storage, initialization gives it a value. A const qualifier makes a variable read-only after initialization.

Storage classes

Scope is where a name is visible; lifetime is how long its storage exists. A static local keeps its value between calls — the classic function-call counter. Block scope: a variable declared inside { } dies at the closing brace. Shadowing: an inner declaration hides an outer one with the same name.

2. Operators & Expressions

The operator families

Short-circuit evaluation: in a && b, if a is false, b is never evaluated. Same idea for ||. This makes guards like if (p && p->data) safe.

3. Control Flow

if / else if / else for branching, switch for multi-way dispatch on an integer or character constant (every case needs its own break unless fall-through is intended). Loops: while (test first), do-while (runs at least once), for (init; condition; update). break exits the loop, continue skips to the next iteration.

switch (grade) {
    case 'A': printf("Excellent"); break;
    case 'B': printf("Good"); break;
    default:  printf("Keep trying");
}

4. Recursion

Recursion solves a problem by solving smaller instances of itself. Every recursive function needs a base case (stops the recursion) and a recursive case (shrinks toward the base). Each call gets its own stack frame — that's why deep recursion can overflow the stack.

// Factorial
int fact(int n) {
    if (n <= 1) return 1;          // base case
    return n * fact(n - 1);        // recursive case
}

// Fibonacci
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Tower of Hanoi: move n disks from source to destination using an auxiliary peg. Move n−1 disks aside, move the largest, move n−1 back on top — total moves = 2ⁿ − 1.

GCD (Euclid): gcd(a, b) = gcd(b, a % b), base case gcd(a, 0) = a.

5. Pointers & Memory

Pointer basics

A pointer holds a memory address. & takes an address, * dereferences it. Pointer arithmetic moves in units of the pointed-to type: p + 1 jumps one whole element, not one byte.

Dynamic memory allocation

int *p = malloc(n * sizeof(int));   // uninitialized block
int *q = calloc(n, sizeof(int));    // zero-initialized block
p = realloc(p, m * sizeof(int));    // resize (may move the block)
free(p); p = NULL;                  // release and null out

A memory leak is allocated memory never freed — the program slowly bleeds RAM until it dies or gets killed.

6. Arrays & Strings

An array is a contiguous block of same-type elements with O(1) random access. In C, a string is just a char array terminated by '\0'.

2D arrays: row-major vs column-major

Row-major lays each row contiguously, so iterating row-by-row is cache-friendly in C. Get the order wrong and performance falls off a cliff on large matrices.

7. Linked Lists

Singly linked list

Each node holds data plus a pointer to the next node. Memory is allocated per node at runtime (no fixed capacity), but there's no random access — reaching element k costs O(k).

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

Doubly linked list

Adds a prev pointer to each node, so traversal runs both directions and deletion is O(1) once you hold the node. The price: extra memory per node and more pointer updates on every insert/delete (four pointer fixes for a middle insertion).

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

8. Stacks

LIFO — last in, first out. You only ever touch the top: push adds, pop removes and returns, peek looks without removing, isEmpty checks.

void push(int x) {
    if (top == MAX - 1) { /* stack overflow */ return; }
    stack[++top] = x;
}
int pop(void) {
    if (top == -1) { /* stack underflow */ return -1; }
    return stack[top--];
}

Applications: function call management (the call stack), expression evaluation and infix→postfix conversion, undo/redo, backtracking (DFS is a stack in disguise).

9. Queues

FIFO — first in, first out. enqueue adds at the rear, dequeue removes from the front.

Circular queue

Wraps the array around so freed front slots get reused — no shifting needed. Indices advance with modulo arithmetic:

• Empty: front == -1
• Full: (rear + 1) % size == front
• Enqueue: rear = (rear + 1) % size; dequeue: front = (front + 1) % size

Double-ended queue (Deque)

Insert and delete at both ends. Variants: input-restricted (insert at one end only) and output-restricted (delete at one end only). Powers sliding-window algorithms and work-stealing schedulers.

Applications: BFS traversal, process scheduling (ready queue), buffering (I/O queues, print spooling), resource management.

10. Trees

Terminology

Binary tree properties

• Max nodes at level l: 2^l
• Max nodes in a tree of height h: 2^h+1 − 1
• Minimum height of n nodes: ⌊log₂ n⌋

Traversals

Binary Search Tree (BST)

The ordering invariant: left subtree < root < right subtree, recursively. Search, insert, and delete all run in O(h) where h is the height — O(log n) on average, O(n) if insertions arrive sorted and the tree degenerates into a line. Deletion cases: leaf (just remove), one child (bypass), two children (replace with inorder successor, then delete it).

11. Balanced BSTs & AVL

Balance is what keeps tree operations at O(log n). Two families: height-balanced trees (AVL, Red-Black) and multiway trees (B-trees).

B-trees

A B-tree of order m: every node holds at most m−1 keys and m children; every node except the root holds at least ⌈m/2⌉−1 keys; the root has at least 2 children unless it's a leaf; all leaves sit at the same level. That's what makes them the backbone of databases and filesystems — one node = one disk block.

AVL trees

A BST with a strict balance rule: for every node, |height(left) − height(right)| ≤ 1. The balance factor is stored per node; insertions and deletions that violate it trigger rotations:

AVL keeps the height at ~1.44 log n, so every operation stays O(log n) with slightly costlier inserts than Red-Black trees — pick AVL for read-heavy workloads.

12. Heaps

A binary heap is a complete binary tree (every level full except possibly the last, filled left to right) with the heap property: in a min-heap every parent ≤ its children (root is the minimum); in a max-heap every parent ≥ its children. Stored compactly in an array: children of index i at 2i+1, 2i+2.

Uses: priority queues, heap sort (O(n log n), in-place), scheduling. Note: a heap is not a BST — only the root is ordered; siblings are unrelated.

13. Hashing

Hashing maps keys to table indices with a hash function, giving average O(1) search, insert, and delete. Common functions: division (h(k) = k mod m), multiplication (multiply by a constant, take the fractional part), and universal hashing (randomized family to defeat adversarial keys).

Lower α → fewer collisions → better performance. When α crosses a threshold (commonly ~0.7 for open addressing), the table rehashes into a bigger one. Hard constraint: with open addressing, α can never exceed 1 — everything must fit inside the table.

Collision resolution: chaining

Each slot holds a linked list of all keys that hash there — colliding elements simply join the chain. No table-overflow problem (chains grow indefinitely), simple to implement, and performance degrades gracefully as α rises.

14. Graphs

A graph is vertices plus edges. Adjacency matrix: a V×V matrix with a 1 where an edge exists — O(1) edge lookup, but O(V²) space even for sparse graphs. Adjacency list: each vertex stores its neighbors — O(V + E) space, the default for sparse graphs.

Traversal

• BFS (queue): explores level by level — finds shortest paths in unweighted graphs. O(V + E).
• DFS (stack/recursion): dives deep first — used for topological sort, cycle detection, connected components. O(V + E).

15. Complexity Cheat Sheet

Average-case access / search / insert / delete, worst case, and space — the table every exam draws from:

← Back to all subjects