Data Structures & Algorithms
Big-O, arrays to graphs, sorting and searching, and dynamic programming: choosing a shape for the data and a way to walk it.
Topics in this field: 16
- Big-O and Complexity — How an algorithm's cost grows with input size, ignoring constants. The language for comparing solutions before you run them.
- Arrays — A contiguous block of same-sized elements. Constant-time indexing, cache-friendly scans, and costly middle inserts.
- Linked Lists — Nodes that each hold a value and a pointer to the next. Cheap splicing, no random access.
- Stacks — Last in, first out. Push and pop at one end in constant time — the structure behind calls, undo, and depth-first search.
- Queues — First in, first out. Enqueue at the back and dequeue at the front — the shape of fairness, buffers, and breadth-first search.
- Hash Tables — Turn a key into an array index with a hash function. Average constant-time lookup, insert, and delete.
- Sorting — Arrange items in order. Comparison sorts cannot beat O(n log n); merge sort and quicksort get there by dividing the problem.
- Binary Search — Halve a sorted search space each step. O(log n) lookups — and a template for searching on any monotonic condition.
- Binary Search Trees — A tree where left descendants are smaller and right descendants are larger. Ordered data with O(log n) operations — when balanced.
- Heaps and Priority Queues — A tree stored in an array where every parent is smaller (min-heap) than its children. Constant-time min and logarithmic push/pop.
- Tries — A tree keyed by characters or bits that shares prefixes. Prefix search and longest-prefix match in time proportional to the key length.
- Graphs — Vertices connected by edges. The general model for networks, maps, dependencies, and relationships.
- Breadth-First Search — Explore a graph level by level using a queue. Finds shortest paths in unweighted graphs.
- Depth-First Search — Follow one path as far as it goes, then backtrack. The basis for cycle detection, topological sort, and exhaustive search.
- Dijkstra's Algorithm — Shortest paths from one vertex in a graph with non-negative weights, by repeatedly settling the closest unsettled vertex.
- Dynamic Programming — Solve a problem by combining solutions to overlapping subproblems, computed once each. Recursion plus a table.