Skip to content
dsa/roadmap
Glossary

81 terms, plain English

Grouped by phase. Press ⌘K to search any of them.

01 Foundations

Abstraction
Hiding implementation details behind an interface so users only see what they need. Learn β†’
ADT (Abstract Data Type)
A description of data plus the operations on it, saying what they do but not how they are implemented. Learn β†’
Algorithm
A finite, well-defined sequence of steps that turns input into the desired output. Learn β†’
Base case
The input a recursive function answers directly, without recursing. Learn β†’
Best / average / worst case
The running time on the most favourable, typical, and least favourable input of size n. Learn β†’
Big-O (O)
Upper bound: f(n) = O(g(n)) if f(n) ≀ cΒ·g(n) for all n β‰₯ k, for some constants c > 0 and k. Learn β†’
Big-Omega (Ξ©)
Lower bound: f(n) β‰₯ cΒ·g(n) for all n β‰₯ k. Learn β†’
Big-Theta (Θ)
Tight bound: f(n) is both O(g(n)) and Ξ©(g(n)). Learn β†’
Call stack
Memory where each active function call keeps its parameters and local variables. Learn β†’
Dangling pointer
A pointer to memory that has already been freed. Learn β†’
Data structure
A way of organising data in memory so that the operations you need are efficient. Learn β†’
Definiteness
Every step is precise and unambiguous. Learn β†’
Empirical analysis
Measuring an algorithm by running it and timing it. Depends on the machine and the input. Learn β†’
Finiteness
An algorithm must stop after a finite number of steps. Learn β†’
Heap (memory)
Memory for dynamic allocation with new/delete. Lives until you free it. Learn β†’
Linear data structure
Items form a sequence, each with at most one predecessor and one successor: arrays, linked lists, stacks, queues. Learn β†’
Little-o / little-omega
Strict bounds: f grows strictly slower (o) or strictly faster (Ο‰) than g. Learn β†’
Memory leak
Heap memory that is no longer reachable but was never deleted. Learn β†’
Non-linear data structure
Items branch or connect freely: trees and graphs. Learn β†’
Pointer
A variable that stores a memory address. Learn β†’
Primitive data structure
Built-in types operated on directly by the machine: int, char, float, bool, pointers. Learn β†’
Recursion
A function that calls itself on a smaller input, stopping at a base case. Learn β†’
Static vs dynamic
Static structures have a size fixed when they are created (arrays); dynamic ones grow and shrink at run time (linked lists). Learn β†’
T(n)
The running time of an algorithm as a function of input size n, in time units. Learn β†’
Theoretical analysis
Counting basic operations as a function of input size n. Machine-independent. Learn β†’
Time unit
One basic operation (assignment, single I/O, Boolean or arithmetic op, return) counted as 1 in T(n). Learn β†’
Time/space trade-off
Using more memory to save time (or the reverse), e.g. storing results instead of recomputing them. Learn β†’

02 Linear Structures

Circular queue
Array queue whose indices wrap around with % N so freed slots are reused. Learn β†’
Deque
Double-ended queue: insert and remove at both ends in O(1). Learn β†’
Doubly linked list
Each node has both next and prev pointers, allowing backward traversal and O(1) delete given a node. Learn β†’
Dummy (sentinel) node
A fake node placed before the head so every real node has a predecessor. Learn β†’
FIFO
First In, First Out. Learn β†’
LIFO
Last In, First Out. Learn β†’
Node
One element of a linked structure: data plus pointer(s) to other nodes. Learn β†’
Overflow / underflow
Pushing onto a full stack / popping from an empty one. Learn β†’
Queue
FIFO collection: enqueue at the rear, dequeue from the front. Learn β†’
Row-major order
How C++ stores a 2-D array: row 0 first, then row 1. Address of a[i][j] = base + (iΒ·cols + j)Β·size. Learn β†’
Stack
LIFO collection: push and pop at the top only. Learn β†’

03 Searching & Sorting

Divide and conquer
Split a problem into smaller parts, solve them recursively, combine the results. Learn β†’
Gap (shell sort)
The distance between compared items in a shell sort pass; shrinks to 1. Learn β†’
In-place
Uses only O(1) extra memory besides the input (recursion stack aside). Learn β†’
Partition
Rearranging a range so items smaller than the pivot come before it and bigger ones after. Learn β†’
Pass
One full sweep of the outer loop of a sort. Learn β†’
Pivot
The item quick sort partitions around. Learn β†’
Pointer sort
Sorting an array of pointers (or indices) to records instead of moving the records themselves. Learn β†’
Stable sort
A sort that keeps equal keys in their original relative order. Learn β†’

04 Trees

Binary tree
A tree in which every node has at most two children, left and right. Learn β†’
BST
Binary search tree: for every node, left subtree < node < right subtree. Learn β†’
Depth / height
Depth: edges from the root down to a node. Height: edges from a node down to its deepest leaf. Learn β†’
Full / complete / perfect
Full: 0 or 2 children everywhere. Complete: all levels full except the last, filled from the left. Perfect: all levels full. Learn β†’
General tree
A tree whose nodes may have any number of children. Learn β†’
Heapify
Sift a node down until the heap property holds below it. O(log n). Learn β†’
Inorder successor
The next value in sorted order; for a node with a right child, the minimum of its right subtree. Learn β†’
Left-child, right-sibling
Stores a general tree with two pointers per node: first child and next sibling. Learn β†’
Level-order traversal
Visit a tree level by level using a queue (BFS on a tree). Learn β†’
Max-heap
A complete binary tree where every parent is β‰₯ its children; stored in an array. Learn β†’
Preorder / inorder / postorder
Depth-first traversals: Node-Left-Right / Left-Node-Right / Left-Right-Node. Learn β†’
Root / leaf
The top node (no parent) / a node with no children. Learn β†’

05 Hashing

Collision
Two different keys hashing to the same index. Learn β†’
Hash function
Maps a key to an index of the hash table, e.g. h(k) = k mod M. Learn β†’
Linear probing
On a collision, try the next slot (h + i) % M until an empty one. Learn β†’
Load factor
Ξ± = n / M, how full a hash table is. Learn β†’
Separate chaining
Each table slot holds a list of all keys that hash there. Learn β†’

06 Graphs

Adjacency list
For each vertex, a list of its neighbours. O(V + E) space. Learn β†’
Adjacency matrix
V×V table where m[u][v] = 1 (or the weight) if there is an edge u→v. O(V²) space. Learn →
BFS
Breadth-first search: explore neighbours in waves using a queue. Finds fewest-edge paths. Learn β†’
Connected graph
There is a path between every pair of vertices. Learn β†’
DAG
Directed acyclic graph: a digraph with no directed cycles. Learn β†’
Degree
Number of edges at a vertex. In a digraph, split into in-degree and out-degree. Learn β†’
DFS
Depth-first search: go as deep as possible, then backtrack, using recursion or a stack. Learn β†’
Directed graph (digraph)
A graph whose edges are one-way arrows. Learn β†’
Graph
G = (V, E): a set of vertices and a set of edges between them. Learn β†’
Path / cycle
A sequence of vertices joined by edges / a path that returns to its start. Learn β†’

LU Level Up: Problem Patterns

Floyd's cycle detection
Slow pointer moves 1, fast moves 2; they meet if and only if there is a cycle. Learn β†’
Monotonic stack
A stack kept in increasing or decreasing order; answers next-greater/smaller queries in O(n). Learn β†’
Prefix sum
p[i] = sum of the first i items; any range sum is p[r+1] βˆ’ p[l]. Learn β†’
Sliding window
Maintain an answer for a contiguous range while it moves, adding and removing one item per step. Learn β†’
Two pointers
Two indices moving through data to replace a pair search with one pass. Learn β†’

Keyboard shortcuts

⌘K /
Search topics, glossary, cheat sheets
space
Play / pause the visualizer
← β†’
Step back / forward
r
Reset the visualizer
?
Show this help