// STUHUB · C++ DATA STRUCTURES

Data Structures Exam Cheat Sheet (C++ Quick Reference)

Night-before reference for a data structures exam: declarations, complexity tables, the rule that decides each answer, and worked traces in C++.

Introduction

Scannable, not readable. Find a fact, use it, move on. Every code block here was compiled with g++ -std=c++17 -Wall; every printed value is real program output.

The sheet runs in the exam's own order: array, singly linked list, stack, queue (linked and circular), tree and BST, graph, sorting, searching — then three worked traces (infix to postfix, BFT queue state, Dijkstra) and a twelve-item list for the last twenty minutes.

1. Array — declarations

Asked: pointer-arithmetic output, 2D indexing, array length.

cpp

int a[5] = {10, 20, 30, 40, 50};
int* p = a;              // array name decays to &a[0]
int m[2][3] = {{1,2,3},{4,5,6}};
int len = sizeof(a) / sizeof(a[0]);

1. Array — outputs, complexity, and the rule

Expression	Same as	Output
`*(p + 2)`	`a[2]`	`30`
`*(a + 4)`	`a[4]`	`50`
`((m + 1) + 2)`	`m[1][2]`	`6`
`sizeof(a)/sizeof(a[0])`	element count	`5`

Operation	Complexity
Access by index	O(1)
Search (unsorted)	O(n)
Insert / delete at position	O(n) (shifting)

The rule: *(ptr + n) advances by n * sizeof(element), not n bytes. Row-major address: base + (i * COLS + j) * sizeof(element).

Costliest mistake: sizeof(arr)/sizeof(arr[0]) gives the wrong answer inside a function — the parameter is a pointer, so sizeof returns the pointer size. Only valid where the array is declared.

2. Singly linked list — the node

Asked: insert, delete by value, in-place reverse, count nodes.

cpp

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

2. Singly linked list — insert, delete, reverse

Insert at the front, delete by value, and reverse in place.

cpp

void insertFront(Node*& head, int v) {
    Node* n = new Node(v);
    n->next = head;          // link new node first
    head = n;                // then move head
}

bool deleteValue(Node*& head, int v) {
    if (head == nullptr) return false;
    if (head->data == v) {               // deleting the head is a separate case
        Node* t = head; head = head->next; delete t; return true;
    }
    Node* prev = head;
    while (prev->next != nullptr && prev->next->data != v) prev = prev->next;
    if (prev->next == nullptr) return false;
    Node* t = prev->next;
    prev->next = t->next;
    delete t;
    return true;
}

void reverseList(Node*& head) {
    Node* prev = nullptr;
    Node* cur  = head;
    while (cur != nullptr) {
        Node* nxt = cur->next;   // 1. save
        cur->next = prev;        // 2. flip
        prev = cur;              // 3. advance prev
        cur  = nxt;              // 4. advance cur
    }
    head = prev;                 // do not forget this line
}

2. Singly linked list — output and cost table

Real output from the compiled demo:

built:    5 -> 10 -> 20 -> 30
del 20:   5 -> 10 -> 30
reversed: 30 -> 10 -> 5
count = 3

Operation	Singly	Doubly	Array
Insert/delete at head	O(1)	O(1)	O(n)
Insert at tail (with tail ptr)	O(1)	O(1)	O(1) amortised
Delete a given node	O(n) (need prev)	O(1)	O(n)
Access k-th element	O(n)	O(n)	O(1)
Extra memory per node	1 pointer	2 pointers	0

The rule: in reversal, save next before overwriting cur->next. Order is save → flip → advance → advance.

Costliest mistake: forgetting head = prev; at the end of reverse — the list is correctly reversed in memory but head still points at what is now the tail, so printing shows one node.

3. Stack — array implementation

LIFO. Array version, top starts at -1.

Operation	Complexity
push / pop / peek / isEmpty	O(1)

Precedence (highest first): ^ → * / → + -. ( has lowest precedence once on the stack.

cpp

const int MAX = 100;
class ArrayStack {
    int arr[MAX];
    int top;
public:
    ArrayStack() : top(-1) {}
    bool isEmpty() const { return top == -1; }
    bool isFull()  const { return top == MAX - 1; }
    void push(int v) { if (isFull()) return; arr[++top] = v; }   // pre-increment
    int  pop()       { if (isEmpty()) return -1; return arr[top--]; } // post-decrement
    int  peek() const{ return isEmpty() ? -1 : arr[top]; }
    int  size() const{ return top + 1; }
};

3. Stack — postfix evaluation

Postfix evaluation:

cpp

int evaluatePostfix(const string& exp) {
    stack<int> s;
    for (char c : exp) {
        if (isdigit(c)) {
            s.push(c - '0');
        } else {
            int op2 = s.top(); s.pop();   // RIGHT operand pops first
            int op1 = s.top(); s.pop();   // LEFT operand pops second
            switch (c) {
                case '+': s.push(op1 + op2); break;
                case '-': s.push(op1 - op2); break;
                case '*': s.push(op1 * op2); break;
                case '/': s.push(op1 / op2); break;
            }
        }
    }
    return s.top();
}

3. Stack — the operand-order trap

Compiled output: evaluatePostfix("62/3-42*+") prints 8 (6/2 = 3, 3−3 = 0, 4×2 = 8, 0+8 = 8).

Costliest mistake: popping the operands in the wrong order. The first value popped is the right operand. Gets - and / wrong every time and + and * right, so it hides until it costs marks.

4a. Queue — linked-list queue

FIFO. Insert at rear, remove from front.

cpp

struct QNode { int data; QNode* next; QNode(int v) : data(v), next(nullptr) {} };

class LinkedQueue {
    QNode* qFront; QNode* qRear; int count;
public:
    LinkedQueue() : qFront(nullptr), qRear(nullptr), count(0) {}
    bool isEmpty() const { return qFront == nullptr; }
    void enqueue(int v) {
        QNode* n = new QNode(v);
        if (qRear == nullptr) { qFront = qRear = n; }   // first node: both pointers
        else { qRear->next = n; qRear = n; }
        count++;
    }
    bool dequeue(int& out) {
        if (qFront == nullptr) return false;
        QNode* t = qFront;
        out = t->data;
        qFront = qFront->next;
        if (qFront == nullptr) qRear = nullptr;         // <-- the line people drop
        delete t;
        count--;
        return true;
    }
};

4a. Queue — the dangling rear pointer

Costliest mistake: not resetting qRear = nullptr when the last element leaves. The queue reports empty, but qRear dangles at freed memory and the next enqueue writes through it.

4b. Queue — circular queue

The array version, with every index advance taken modulo capacity.

cpp

class CircularQueue {
    int* arr; int capacity, front, rear;
public:
    CircularQueue(int cap) : capacity(cap), front(0), rear(0) { arr = new int[cap]; }
    ~CircularQueue() { delete[] arr; }
    bool isEmpty() const { return front == rear; }
    bool isFull()  const { return (rear + 1) % capacity == front; }
    int  size()    const { return (rear - front + capacity) % capacity; }
    bool enqueue(int v) {
        if (isFull()) return false;
        arr[rear] = v;
        rear = (rear + 1) % capacity;
        return true;
    }
    bool dequeue(int& out) {
        if (isEmpty()) return false;
        out = arr[front];
        front = (front + 1) % capacity;
        return true;
    }
};

4b. Queue — the four formulas and a real trace

The formulas — memorise these four:

Test	Sacrificed-slot version	Counter version
Empty	`front == rear`	`count == 0`
Full	`(rear + 1) % capacity == front`	`count == capacity`
Advance rear	`rear = (rear + 1) % capacity`	same
Advance front	`front = (front + 1) % capacity`	same
Usable slots	`capacity - 1`	`capacity`

Real trace, capacity = 5:

start             front=0 rear=0 size=0 empty=Y full=N
enq 10,20,30,40   front=0 rear=4 size=4 empty=N full=Y
enqueue(50) accepted? no
deq twice         front=2 rear=4 size=2 empty=N full=N
enq 50,60         front=2 rear=1 size=4 empty=N full=Y

Note rear wrapped from 4 to 1 — that is the whole point.

Why circular at all (the essay answer): a simple linear array queue suffers false overflow. After dequeues, front moves forward and leaves free slots at the start, but once rear reaches MAX - 1 the queue refuses new elements even though the array is mostly empty. Fixing it by shifting everything down is O(n) per dequeue. A circular queue wraps the indices with % capacity and reuses those slots in O(1).

Costliest mistake: if you do not sacrifice a slot and do not keep a counter, front == rear means both "empty" and "full" and the two states are indistinguishable.

5. Tree / BST — terminology

Get these exact.

Term	Definition
Degree of a node	number of children
Degree of the tree	maximum degree of any node
Leaf / external node	degree 0
Internal node	degree ≥ 1
Level of root	0 (some texts use 1 — state your convention)
Depth of a node	edges from root down to that node; root depth = 0
Height of a node	edges on longest path from that node down to a leaf; leaf height = 0
Height of the tree	height of the root = maximum depth of any node
Empty tree	height `-1` (edge convention)
Max nodes at level L	2^L
Max nodes in tree of height h	2^(h+1) − 1

Depth counts downward from the root, height counts upward from the leaves. They are equal only at the root.

cpp

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : data(v), left(nullptr), right(nullptr) {}
};

5. Tree / BST — operations

Insert, search, height, leaf count, the three depth-first traversals, and level order.

cpp

TreeNode* insertBST(TreeNode* root, int v) {
    if (root == nullptr) return new TreeNode(v);       // base case creates the node
    if (v < root->data) root->left  = insertBST(root->left, v);
    else                root->right = insertBST(root->right, v);
    return root;                                       // re-attach on the way back up
}

bool searchBST(TreeNode* root, int target) {
    if (root == nullptr) return false;
    if (root->data == target) return true;
    if (target < root->data) return searchBST(root->left, target);
    return searchBST(root->right, target);
}

int height(TreeNode* r) {                    // edge convention
    if (r == nullptr) return -1;
    return 1 + max(height(r->left), height(r->right));
}

int countLeaves(TreeNode* r) {
    if (r == nullptr) return 0;
    if (r->left == nullptr && r->right == nullptr) return 1;
    return countLeaves(r->left) + countLeaves(r->right);
}

void inorder(TreeNode* r)  { if (!r) return; inorder(r->left);  cout << r->data << " "; inorder(r->right); }
void preorder(TreeNode* r) { if (!r) return; cout << r->data << " "; preorder(r->left); preorder(r->right); }
void postorder(TreeNode* r){ if (!r) return; postorder(r->left); postorder(r->right); cout << r->data << " "; }

void levelOrder(TreeNode* root) {            // uses a QUEUE, not recursion
    if (!root) return;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        cout << cur->data << " ";
        if (cur->left)  q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

5. Tree / BST — insert rule, real output, complexity

BST insert rule: value < node->data → go left, otherwise go right. New nodes always become leaves; nothing already in the tree moves.

Inserting 50, 30, 70, 20, 40, 60, 80, 35 gives this real output:

inorder:    20 30 35 40 50 60 70 80
preorder:   50 30 20 40 35 70 60 80
postorder:  20 35 40 30 60 80 70 50
levelorder: 50 30 70 20 40 60 80 35
height(edges)=3  leaves=4  search(40)=found  search(45)=not found

Operation	Balanced BST	Degenerate (sorted input)
Search / insert / delete	O(log n)	O(n)
Any traversal	O(n)	O(n)

The check that catches errors: in-order on a BST must come out in ascending order. If it does not, your tree is wrong — redo it before answering anything else.

Costliest mistake: mixing up height and depth, and off-by-one from the two conventions. Say which one you are using ("height in edges, empty tree = −1") and stay consistent across the whole answer.

6. Graph — representation

Representation	Space	Edge exists?	List neighbours
Adjacency matrix	O(V²)	O(1)	O(V)
Adjacency list	O(V + E)	O(deg v)	O(deg v)

cpp

// adjacency list — preferred for sparse graphs
vector<vector<int>> adj(V);
void addEdgeUndirected(vector<vector<int>>& adj, int u, int w) {
    adj[u].push_back(w);
    adj[w].push_back(u);        // BOTH directions
}
void addArcDirected(vector<vector<int>>& adj, int u, int w) {
    adj[u].push_back(w);        // one direction only
}

6. Graph — degree

Graph	Rule
Undirected	degree(v) = edges touching v; a self-loop counts 2; Σ degrees = 2E
Directed	in-degree = arcs arriving; out-degree = arcs leaving; total = in + out
Directed sum	Σ in-degrees = Σ out-degrees = E

For the directed graph A→B, A→C, C→B, B→D, C→D, C→E, D→E (7 arcs):

Vertex	In	Out	Total
A	0	2	2
B	2	1	3
C	1	3	4
D	2	1	3
E	2	0	2
Σ	7	7	14

Use Σin = Σout = E as your instant self-check.

6. Graph — breadth-first traversal

Breadth-first traversal is driven by a queue.

cpp

vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;      // mark WHEN ENQUEUEING
q.push(start);
while (!q.empty()) {
    int u = q.front(); q.pop();
    cout << u << " ";
    for (int w : adj[u]) {
        if (!visited[w]) { visited[w] = true; q.push(w); }
    }
}

6. Graph — the BFT marking trap

Costliest mistake: marking a vertex visited when you dequeue it instead of when you enqueue it. A vertex with two unvisited-at-the-time neighbours then gets pushed twice and appears twice in the output.

DFS is the same code with a stack instead of a queue (or recursion).

6. Graph — Dijkstra

Relaxation step — the one line the whole question turns on:

if dist[u] + weight(u, v) < dist[v] then dist[v] = dist[u] + weight(u, v) and parent[v] = u

Loop: pick the unsettled vertex with the smallest dist, mark it settled (its distance is now final), relax all its outgoing edges, repeat.

cpp

vector<int> dist(V, INT_MAX), parent(V, -1);
vector<bool> done(V, false);
dist[src] = 0;
for (int it = 0; it < V; it++) {
    int u = -1;
    for (int i = 0; i < V; i++)
        if (!done[i] && dist[i] != INT_MAX && (u == -1 || dist[i] < dist[u])) u = i;
    if (u == -1) break;
    done[u] = true;
    for (auto& e : adj[u]) {                 // e = {neighbour, weight}
        int v = e.first, w = e.second;
        if (!done[v] && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; parent[v] = u; }
    }
}

6. Graph — Dijkstra complexity and limits

Version	Complexity
Array scan for the minimum	O(V²)
Binary heap / priority queue	O((V + E) log V)

Costliest mistake: using Dijkstra on a graph with a negative edge weight. Once a vertex is settled its distance is never revisited, so a negative edge can produce a wrong answer. Say "Bellman-Ford" if negative weights appear.

6. Graph — Kruskal (MST)

Sort all edges by weight, ascending.
Take the next cheapest edge; keep it only if it joins two different components (no cycle).
Stop at V − 1 edges.

Cycle detection with union-find. Contrast: Prim's grows one tree from a start vertex (vertex-based); Kruskal's picks globally cheapest edges (edge-based). Both give the same total weight.

7. Sorting

Bubble, selection and insertion, written the way they are marked.

cpp

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; }
        if (!swapped) break;                 // makes best case O(n)
    }
}

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) swap(a[i], a[minIdx]);
    }
}

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

7. Sorting — comparison table and a real trace

Algorithm	Best	Average	Worst	Space	Stable
Bubble (with flag)	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	No

Real bubble-sort passes on 5 1 4 2 8:

pass 1: 1 4 2 5 8
pass 2: 1 2 4 5 8
pass 3: 1 2 4 5 8      (no swap -> stop early)

Costliest mistake: the inner bound. It is j < n - 1 - i, not j < n - 1. Without - i you re-compare the already-sorted tail; with j <= n - 1 you read a[n] off the end.

8. Searching

Binary search, in the form that survives marking.

cpp

int binarySearch(const int a[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {                       // <=, not <
        int mid = low + (high - low) / 2;       // overflow-safe form
        if (a[mid] == target) return mid;
        else if (a[mid] < target) low  = mid + 1;
        else                      high = mid - 1;
    }
    return -1;
}

8. Searching — comparison and the loop-bound trap

Algorithm	Best	Worst	Requires
Linear search	O(1)	O(n)	nothing
Binary search	O(1)	O(log n)	sorted array, random access

On 2 5 8 12 16 23 38 56 72 91 the compiled program prints: index of 23 = 5, index of 24 = -1, linear index of 56 = 7.

Costliest mistake: while (low < high) or low = mid / high = mid. The first misses the last candidate; the second loops forever when low and high are adjacent.

Worked trace A — infix to postfix: P - Q / (R + S) * T

Rules: operand → output. ( → push. ) → pop to output until (, discard (. Operator → while the stack top is an operator of higher or equal precedence, pop it to output; then push. End → pop everything.

Read	Action	Stack (bottom→top)	Output
`P`	operand	—	`P`
`-`	stack empty, push	`-`	`P`
`Q`	operand	`-`	`PQ`
`/`	`-` is lower, push	`-/`	`PQ`
`(`	push	`-/(`	`PQ`
`R`	operand	`-/(`	`PQR`
`+`	top is `(`, push	`-/(+`	`PQR`
`S`	operand	`-/(+`	`PQRS`
`)`	pop `+`, discard `(`	`-/`	`PQRS+`
`*`	`/` equal precedence → pop it; `-` lower → push `*`	`-*`	`PQRS+/`
`T`	operand	`-*`	`PQRS+/T`
end	pop `*`, then `-`	—	`PQRS+/T*-`

Answer: PQRS+/T*- (verified by the compiled program).

Two traps: ( is never sent to the output, and equal precedence pops (left-associative), which is what makes / come out before *.

Worked trace B — BFT queue state, start = 0

Undirected graph: 0–1, 0–2, 1–3, 1–4, 2–4, 3–5, 4–5.

Step	Dequeue	Newly visited (enqueued)	Queue after (front→back)
0	—	0	`0`
1	0	1, 2	`1 2`
2	1	3, 4	`2 3 4`
3	2	— (4 already visited)	`3 4`
4	3	5	`4 5`
5	4	—	`5`
6	5	—	empty

Visit order: 0 1 2 3 4 5. Step 3 is the mark: 2's neighbour 4 was already marked at step 2, so it is not enqueued again.

Worked trace C — Dijkstra table, source A

Directed, weighted: A→B 4, A→C 2, C→B 1, B→D 5, C→D 7, C→E 10, D→E 3.

Settle	B	C	D	E	What changed
init	∞	∞	∞	∞
A (0)	4	2	∞	∞	B←4 via A, C←2 via A
C (2)	3	2	9	12	B improved 4→3 via C, D←9, E←12
B (3)	3	2	8	12	D improved 9→8 via B
D (8)	3	2	8	11	E improved 12→11 via D
E (11)	3	2	8	11	nothing left

Shortest path A→E = A→C→B→D→E, cost 11 (2+1+5+3). All values are real program output.

The teaching point is row 2: the direct arc A→B cost 4, but going through C cost 3. Always pick the smallest unsettled distance next, and always re-check whether a shorter route just appeared.

If you only have twenty minutes

Circular queue tests. Empty front == rear; full (rear + 1) % capacity == front; advance with % capacity; capacity − 1 usable.
Postfix operand order. First pop = right operand. Second pop = left.
Height vs depth. Depth counts down from the root (root = 0); height counts up from the leaves (leaf = 0, empty = −1).
BST insert rule. < goes left, otherwise right; new nodes are always leaves; in-order must come out ascending.
Mark visited on enqueue in BFT, never on dequeue.
Dijkstra relaxation. if (dist[u] + w < dist[v]) dist[v] = dist[u] + w; and settle the smallest unsettled vertex each round.
Reset rear = nullptr when a linked queue empties.
head = prev; at the end of an in-place list reverse.
Degree checks. Undirected Σdeg = 2E; directed Σin = Σout = E.
Complexities worth memorising cold. Array access O(1); list search O(n); stack/queue ops O(1); balanced BST O(log n) but degenerate O(n); binary search O(log n) and it needs a sorted array; bubble/selection/insertion O(n²), merge O(n log n).
Precedence. ^ > * / > + -; ( is never output; equal precedence pops.
Write the struct first. In a code question the node declaration and the null checks are marks on their own — put them down even if the algorithm body stalls.

Good luck. Sleep beats one more re-read.

Published and updated 2026-08-09 · DUOCODE TECHNOLOGY