Data Structures Cheat Sheet

Time & space complexity — Big-O quick reference

* O(1) insert/delete at head only, for a singly linked list. Tail insert is O(1) only with a tail pointer.

Arrays

Key properties

Sorting algorithms

Stable sort = equal elements keep their original relative order. Merge and Insertion sort are stable.

Binary search — must know

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;  // avoid overflow!
    if (arr[mid] == key) return mid;
    else if (arr[mid] < key) lo = mid + 1;
    else hi = mid - 1;
}
return -1;  // not found

Linked lists

Node structure

// Singly linked list node
struct Node {
    int data;
    struct Node *next;
};

// Doubly linked list node
struct DNode {
    int data;
    struct DNode *prev, *next;
};

Types comparison

Insert at head — O(1)

struct Node* insertHead(struct Node* head, int d) {
    struct Node* n = malloc(sizeof(struct Node));
    n->data = d;
    n->next = head;
    return n;  // new head
}

Floyd's cycle detection

// Slow & fast pointer (Tortoise & Hare)
struct Node *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return 1;  // cycle found
}
return 0;  // no cycle

Reverse a linked list — O(n)

struct Node *prev = NULL, *curr = head, *nxt;
while (curr) {
    nxt = curr->next;
    curr->next = prev;
    prev = curr;
    curr = nxt;
}
return prev;  // new head

Find middle of list — O(n)

// When fast reaches the end, slow is at the middle
struct Node *slow = head, *fast = head;
while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow = middle node

Stacks — LIFO

Stack operations

Key applications

Array-based stack in C

#define MAX 100
int stack[MAX], top = -1;

void push(int x) {
    if (top == MAX - 1) { printf("Overflow"); return; }
    stack[++top] = x;
}

int pop() {
    if (top == -1) { printf("Underflow"); return -1; }
    return stack[top--];
}

int peek() { return stack[top]; }

Infix → Postfix rules

Precedence: ^ > * / > + -
1. Operand           → send to output directly
2. (                 → push
3. )                 → pop until (
4. Operator          → pop while stack top has higher/equal precedence, then push
5. End of expression  → pop all remaining operators

Example: A+B*C   → ABC*+
Example: A*(B+C) → ABC+*

Queues — FIFO

Queue operations

Types of queues

Circular queue (fixes wasted space)

#define MAX 5
int q[MAX], front = -1, rear = -1;

void enqueue(int x) {
    if ((rear + 1) % MAX == front) { printf("Full"); return; }
    if (front == -1) front = 0;
    rear = (rear + 1) % MAX;
    q[rear] = x;
}

int dequeue() {
    if (front == -1) return -1;  // empty
    int x = q[front];
    if (front == rear) front = rear = -1;
    else front = (front + 1) % MAX;
    return x;
}

Applications

Trees — binary trees & BST

Key tree terminology

BST properties & operations

// BST property: left < root < right
Node* search(Node* r, int k) {
    if (!r || r->data == k) return r;
    if (k < r->data) return search(r->left, k);
    return search(r->right, k);
}

// Inorder of a BST = sorted ascending order
// BST insert: like search, add at the NULL spot found
// BST delete has 3 cases:
//   1. Leaf              → just remove
//   2. One child          → replace node with its child
//   3. Two children        → replace with inorder successor
//                            (smallest value in the right subtree)

Tree traversals

// Inorder (Left → Root → Right) → sorted order for a BST
void inorder(Node *r) {
    if (!r) return;
    inorder(r->left);
    printf("%d ", r->data);
    inorder(r->right);
}

// Preorder (Root → Left → Right)  → used to copy a tree
// Postorder (Left → Right → Root) → used to delete a tree
// Level order                     → uses a queue (BFS)

Important formulas

Heaps & priority queues

Heap properties

Heap sort steps

Step 1: Build a max heap from the array — O(n)
        heapify from the last internal node (index n/2 - 1) down to the root

Step 2: Extract the max repeatedly — O(n log n)
        swap root with the last element
        reduce heap size by 1
        heapify the root

Result: ascending sorted array
Space:  O(1) — in-place
Stable: No

Array representation

For a node at index i (1-based):
  Left child  = 2*i
  Right child = 2*i + 1
  Parent      = i/2

For a node at index i (0-based):
  Left child  = 2*i + 1
  Right child = 2*i + 2
  Parent      = (i-1)/2

Applications

Graphs

Representations

Use a matrix for dense graphs; a list for sparse graphs.

DFS — cycle detection, topological sort

bool visited[V] = {false};

void DFS(int u, int adj[][V]) {
    visited[u] = true;
    printf("%d ", u);
    for (int v = 0; v < V; v++)
        if (adj[u][v] && !visited[v])
            DFS(v, adj);
}

BFS — level order, shortest path (unweighted)

void BFS(int src, int adj[][V]) {
    bool visited[V] = {false};
    int queue[V], front = 0, rear = 0;
    visited[src] = true;
    queue[rear++] = src;

    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (int v = 0; v < V; v++)
            if (adj[u][v] && !visited[v]) {
                visited[v] = true;
                queue[rear++] = v;
            }
    }
}

Shortest path algorithms

Spanning tree algorithms

Hashing

Hash table operations

Worst case O(n) occurs when all keys hash to the same slot (all collisions).

Collision resolution

Hash functions

Division method:
  h(k) = k % m   (m should be prime)

Multiplication method:
  h(k) = floor(m * (k*A mod 1))   where A ≈ 0.618 (golden ratio)

For strings (djb2):
  hash = 5381;
  while (*str) hash = hash*33 ^ *str++;

Load factor & rehashing

Load factor α = n / m
  n = number of elements
  m = number of slots

When α > 0.7 (typical threshold):
  → rehash into a larger table (2x)
  → re-insert all elements

Chaining:       works even when α > 1
Open addressing: α must stay < 1

CDAC C-CAT — top DS exam traps

PYQs are indicative of exam style, not guaranteed exact repeats.