Revise on one page

A data structure is a way of organising data in memory so the operations you need are fast. Learn how they are classified and what makes a good one.

• ✗Calling a stack "non-linear". Stacks and queues are linear; only trees and graphs are non-linear here.
• ✗Saying an array is dynamic. A C++ array has a fixed size; vector and linked lists are dynamic.
• ✗Confusing a data structure (how data is stored) with an algorithm (the steps that use it).

An Abstract Data Type says WHAT operations exist; a data structure says HOW they are built. Separating the two is the key idea of this course.

• ✗Saying an ADT "is" an array. An ADT has no storage details at all; an array can only implement one.
• ✗Listing implementation details (like top index) as part of the ADT's definition.
• ✗Forgetting error conditions. "pop on an empty stack is an error" IS part of the ADT.

Arrays store items side by side in memory, which is why reading any index is instant. 2-D arrays are stored row by row.

• ✗Using 1-based indexes. C++ arrays start at 0, so the last valid index is n − 1.
• ✗Writing a[n] (out of bounds). C++ does not check, so it silently corrupts memory.
• ✗Using sizeof(a)/sizeof(a[0]) inside a function. There, a is a pointer, so the trick gives the wrong size. Pass n instead.

An algorithm is a finite, unambiguous sequence of steps that solves a problem. Learn the 11 properties every correct algorithm must have.

• ✗Confusing definiteness (each step has one clear meaning) with finiteness (the algorithm stops).
• ✗Saying an algorithm needs at least one input. It needs zero or more inputs but at least one output.
• ✗Treating "a program" and "an algorithm" as the same. A program may run forever (an OS); an algorithm must terminate.

Empirical vs theoretical analysis, qualitative vs quantitative, the three classic avoidable inefficiencies, and the time–space trade-off.

• ✗Saying empirical analysis is useless. It is useful, but its results depend on the machine, compiler, language and inputs.
• ✗Mixing up "redundant computation" (recomputing the same value in a loop) with "repeated array referencing" (reading a[i] many times).
• ✗Thinking the faster algorithm is always better. It may need far more memory.

Turn code into a formula T(n) using the instructor's counting rules. Loops become sums, and nested loops multiply.

• ✗Counting the loop test n times instead of n + 1 (the last, failing test counts too).
• ✗Counting k = k + 1 as 1 unit. It is 2: one addition and one assignment.
• ✗For if/else, adding both branches. Count the condition plus the larger branch only.

The same algorithm can be fast or slow depending on the input. We analyse the best, average and worst case, and usually report the worst.

• ✗"Best case is when n is small." No: best case is about the arrangement of the input for a given n, never about a small n.
• ✗Thinking the average case is (best + worst) / 2. It is an expected value over all inputs.
• ✗Mixing up the case with the notation. "Worst case" is not the same thing as "Big-O".

O, Ω, Θ, o and ω describe how fast T(n) grows for large n. Learn the definitions, the order of growth, and how to prove f(n) = O(g(n)) by finding c and k.

• ✗Forgetting to state c and k explicitly. A proof without numbers gets partial marks.
• ✗Claiming 3n² = O(n). False: no constant c makes 3n² ≤ c·n for all large n.
• ✗Thinking Big-O means "worst case". Big-O is an upper bound on a function; you can give an upper bound for the best case too.

Find the smallest remaining item and swap it to the front. Repeat. Simple, at most n − 1 swaps, but always O(n²) comparisons.

• ✗Swapping inside the inner loop every time a smaller item is found. Swap once, after the inner loop.
• ✗Starting the inner loop at j = i instead of j = i + 1 (compares an item with itself).
• ✗Claiming selection sort has an O(n) best case. It has none; it always scans.

Compare neighbours and swap them if they are out of order. After each pass the biggest remaining item has "bubbled" to the end.

• ✗Looping j up to n - 1 in every pass instead of n - 1 - i. It still works, but does useless comparisons.
• ✗Writing a[j] >= a[j+1]. Swapping equal items breaks stability.
• ✗Reading past the array with j < n and then accessing a[j + 1].

Grow a sorted part on the left by inserting each new item into its correct place, like sorting cards in your hand. Fast on nearly sorted data.

• ✗Writing a[j] >= key in the while loop. That breaks stability.
• ✗Forgetting j >= 0 in the loop condition, which reads a[-1].
• ✗Putting a[j + 1] = key inside the while loop. It goes after the loop.

When records are big, don't move them. Sort an array of pointers (or indices) to the records instead, and only small addresses get swapped.

• ✗Swapping the records (swap(*p[i], *p[min])) instead of the pointers (swap(p[i], p[min])). That defeats the purpose.
• ✗Comparing the pointers themselves (p[j] < p[min]) instead of what they point to (p[j]->score).
• ✗Forgetting to initialise p[i] = &s[i] before sorting.

Check every item from left to right until you find the key or run out. Works on any array, sorted or not, but costs O(n).

• ✗Returning -1 inside the loop (in an else), which stops after checking only the first item.
• ✗Looping with i <= n, one past the end.
• ✗Forgetting that an unsorted array cannot use binary search.

On a sorted array, check the middle, then throw away the half that cannot contain the key. Each step halves the problem, so it takes O(log n).

• ✗Using while (low < high) instead of low <= high. That misses a key when one item is left.
• ✗Setting low = mid or high = mid instead of mid ± 1, which can loop forever.
• ✗Running it on unsorted data. The result is meaningless.

A function that calls itself on a smaller problem until it reaches a base case. You need this for trees (Ch 6) and merge/quick sort (Ch 8).

• ✗No base case, or a base case that is never reached (e.g. factorial(n + 1)).
• ✗Forgetting to return the recursive call's result (bs(...) instead of return bs(...)).
• ✗Thinking recursion is always slower or always better. It trades stack memory for simpler code.

A pointer holds an address. new asks the heap for memory that lives until you delete it. Master this and linked lists become easy.

• ✗Dereferencing nullptr or an uninitialised pointer, which crashes (segmentation fault).
• ✗Using memory after delete (dangling pointer). Set the pointer to nullptr right after.
• ✗new[] paired with delete instead of delete[].

Nodes on the heap, each pointing to the next. Insert at front, end or a position, delete by value, search and traverse, plus the dummy-node trick and the classic pitfalls.

• ✗Losing the list by updating head before linking the new node (head = n; first).
• ✗Dereferencing temp->next without checking temp != nullptr.
• ✗Forgetting the empty-list and delete-the-head special cases.

Each node points both forward and backward. You can walk in both directions and delete a node knowing only its address, at the cost of one extra pointer per node.

• ✗Updating next but forgetting prev (or the reverse). Each insert or delete touches both directions.
• ✗Forgetting cur->next->prev when cur->next is nullptr (deleting the tail) → crash.
• ✗Not updating tail when deleting the last node.

Last in, first out. The stack ADT (push, pop, peek, isEmpty, isFull) built on a fixed array with a top index, plus overflow and underflow.

• ✗Writing st[top++] = x with top = -1 (writes to index −1). Use st[++top] = x.
• ✗Popping without checking isEmpty() (underflow).
• ✗Pushing without checking isFull() (writes past the array).

The same stack ADT, but the top is the head of a linked list. No fixed capacity, push and pop stay O(1), and the bracket-matching application.

• ✗Using the tail as the top, making pop O(n).
• ✗Forgetting delete in pop (memory leak).
• ✗Reading top->data after deleting the node. Save the value first.

First in, first out. Why a naive array queue makes dequeue O(n), how a front index makes it O(1), and the wasted-slot problem that leads to the circular queue.

• ✗Confusing front and rear (items enter at the rear, leave at the front).
• ✗Dequeuing without checking for empty.
• ✗With a front index, testing rear == -1 for empty. The correct test is front > rear.

Keep two pointers, front and rear. Enqueue at the rear and dequeue at the front, both O(1), with no capacity limit.

• ✗Dequeuing from the tail (needs the previous node, so O(n)).
• ✗Forgetting rear = nullptr when the queue becomes empty. The next enqueue then writes through a dangling pointer.
• ✗Enqueue into an empty queue without setting both front and rear.

Let front and rear wrap around with the modulo operator, so freed slots are reused. All operations O(1) on a fixed array.

• ✗Writing rear++ instead of rear = (rear + 1) % N.
• ✗Testing front == rear for both empty and full. Without a count (or one spare slot) they look the same.
• ✗Printing from 0 to rear instead of starting at front and wrapping.

The standard library versions you will use in real code and on LeetCode, their method names, and the classic traps (pop returns void, empty checks).

• ✗Writing int x = s.pop();. It does not compile; pop() returns void. Read top() first.
• ✗Calling top() / front() / pop() on an empty container (undefined behaviour). Check empty().
• ✗Using q.top() on a queue (it is front()), or s.front() on a stack (it is top()).

Root, parent, child, leaf, sibling, depth, height, level, subtree; full, complete and perfect binary trees; and the Node struct with recursive count and height.

• ✗Mixing up depth (from the root down to a node) and height (from a node down to its deepest leaf).
• ✗Not stating your height convention. Here, a single node has height 0 and an empty tree −1. Some books count nodes instead of edges.
• ✗Thinking "complete" and "full" mean the same thing.

Left is smaller, right is bigger. Insert, search, find min and max by walking one path, and why the tree's shape decides whether that is O(log n) or O(n).

• ✗Writing insert(root->left, x); without assigning the result back to root->left.
• ✗Checking only a node's children, not the whole subtree, when asked "is this a BST?".
• ✗Forgetting the nullptr check before reading root->data.

Deleting a leaf, a node with one child, and a node with two children by copying the inorder successor. The most-asked BST exam question.

• ✗Case 3: copying the successor value but forgetting to delete the successor node itself (you get a duplicate).
• ✗Case 3: searching for the successor in the left subtree. Successor = min of the right subtree.
• ✗Not returning the new subtree root, so the parent still points at the deleted node.

Preorder, inorder and postorder (depth-first, recursive) and level order (breadth-first, with a queue). Know them by hand and in code.

• ✗Mixing the orders. Remember where the Node goes - pre = N L R, in = L N R, post = L R N.
• ✗Forgetting that "left before right" is the same in all three.
• ✗Using a stack for level order (that gives a DFS order instead).

Trees where a node can have any number of children, stored with only two pointers per node using the left-child/right-sibling representation.

• ✗Linking a node's second child to the parent instead of to the first child's nextSibling.
• ✗Drawing siblings as "right child of the parent".
• ✗Forgetting that the root has no siblings.

Vertices and edges, adjacency, degree, paths, cycles, connected graphs, weighted graphs, and how a tree is a special graph.

• ✗Counting path length in vertices instead of edges.
• ✗Saying every graph is connected.
• ✗Forgetting that a cycle must not reuse an edge.

Two ways to store a graph in memory, what each costs, and when to choose which.

• ✗Setting only m[u][v] for an undirected edge. Set m[v][u] too.
• ✗Saying the list is always better. Edge lookup is O(1) only in the matrix.
• ✗Forgetting that an undirected edge appears twice in the list.

One-way edges, in-degree and out-degree, directed paths and cycles, and how the matrix and list change.

• ✗Adding both m[u][v] and m[v][u] for a directed edge.
• ✗Following an arrow backwards when tracing a path.
• ✗Mixing up in-degree (arrows coming in) and out-degree (arrows going out).

Breadth-first search with a queue, depth-first search with recursion or a stack, the visited array, and O(V + E).

• ✗No visited array, so the search loops forever around a cycle.
• ✗In BFS, marking a vertex visited when it is dequeued instead of enqueued (it can be enqueued twice).
• ✗Visiting neighbours in a different order from the one the question uses (usually ascending).

Insertion sort on items a gap apart, with the gap shrinking to 1. Far-away items move in big jumps, so the final insertion sort has little work left.

• ✗Comparing neighbours (gap 1) in every pass, which is just insertion sort.
• ✗Forgetting that the last pass must use gap = 1, or the array may not be sorted.
• ✗Claiming it is stable. Jumps over a gap can reorder equal keys.

Pick a pivot, partition so smaller items go left and bigger items go right, then sort each side recursively. Average O(n log n), worst O(n²).

• ✗Recursing on (lo, p) instead of (lo, p − 1). The pivot is already in place.
• ✗Forgetting the final swap(a[i + 1], a[hi]) that puts the pivot in place.
• ✗Saying quick sort is always O(n log n).

Split the array in half, sort each half recursively, then merge the two sorted halves. Always O(n log n), stable, but needs O(n) extra space.

• ✗Forgetting to copy the leftover items after one half runs out.
• ✗Using < instead of <= in merge, which breaks stability.
• ✗Base case lo > hi only. A single item (lo == hi) must also stop the recursion.

Build a max-heap in the array, then repeatedly swap the root (the largest item) to the end and sift down. O(n log n) in every case, in-place.

• ✗Using 1-based formulas (2i, 2i+1) with a 0-based array. With 0-based it is 2i+1 and 2i+2.
• ✗Starting the build loop at i = 0 instead of n/2 − 1, going down to 0.
• ✗Calling heapify on the whole array instead of the shrinking heap size end.

A hash function turns a key into an array index, so search is O(1) on average. Collisions, separate chaining, linear probing and the load factor.

• ✗With linear probing, stopping a search at a slot holding a different key. Only an empty slot means "not found".
• ✗Forgetting to wrap around with % M when probing.
• ✗Claiming hashing is always O(1). The worst case is O(n).