Book 12 · Cheat sheet

Data Structures

The shapes programs use to organize data, from lists and stacks to trees and graphs, and the classic ways to search and sort them.

01Adjacency List: An adjacency list is a way of storing a graph in which each node keeps a list of the nodes it connects to, using memory in proportion to its nodes and edges.
An adjacency list maps each node to the list of nodes it has edges to.
It uses O(V + E) memory, which suits sparse graphs.
Iterating over a node's neighbors is fast, but checking for one specific edge takes O(degree).
02B-Tree: A B-tree is a self-balancing search tree whose nodes hold many sorted keys and children, which keeps it shallow so lookups need very few disk or page reads.
A B-tree node holds many sorted keys and child pointers, so the tree is wide and shallow.
All leaves are at the same depth, so search, insert, and delete are O(log n).
Nodes split when they overflow and merge when they get too empty, keeping the tree balanced.
03Backtracking: Backtracking is a search technique that builds a solution one choice at a time and undoes the latest choice when it hits a dead end, then tries another option.
Backtracking builds a solution incrementally and undoes choices that lead to dead ends.
It is usually recursive and follows a choose, explore, unchoose pattern.
Pruning invalid partial solutions early is what makes it practical.
04Balanced Tree: A balanced tree is a tree that keeps its height close to log n by rebalancing after changes, so search, insert, and delete stay O(log n) even in the worst case.
A balanced tree keeps its height proportional to log n.
Search, insert, and delete are guaranteed O(log n), even when data arrives in sorted order.
AVL trees and red-black trees rebalance themselves using rotations.
05Binary Search: Binary search is an algorithm that finds a value in a sorted list by repeatedly halving the search range, taking O(log n) time instead of checking every item.
Binary search requires the data to be sorted.
It runs in O(log n) time, compared with O(n) for a linear search.
Each comparison eliminates half of the remaining items.
06Binary Search Tree: A binary search tree is a binary tree in which each node's left subtree holds smaller values and its right subtree larger ones, enabling fast ordered lookups.
Every node's left subtree holds smaller values and its right subtree holds larger ones.
Search, insert, and delete take O(h) time, where h is the height of the tree.
A balanced BST has a height of about log n, so operations are O(log n); a degenerate one is O(n).
07Bloom Filter: A Bloom filter is a compact probabilistic data structure that tells you an item is definitely not in a set or probably is, while using very little memory.
A Bloom filter answers either definitely not or probably yes for set membership.
It never gives false negatives, but it can give false positives.
It stores only a bit array, never the items, so it uses very little memory.
08Breadth-First Search: Breadth-first search is a graph traversal algorithm that visits nodes in order of their distance from the start, exploring all neighbors before going deeper.
BFS explores a graph level by level, visiting the closest nodes first.
It uses a queue, plus a visited set so that no node is processed twice.
It runs in O(V + E) time with an adjacency list and uses O(V) extra memory.
09Bubble Sort: Bubble sort is a simple sorting algorithm that keeps swapping out-of-order neighbors, so each pass carries the largest remaining value to the end.
Bubble sort repeatedly swaps neighboring elements that are out of order.
Each pass moves the largest remaining element to the end.
It is O(n²) on average, O(n) on sorted input with early exit.
10Depth-First Search: Depth-first search is a graph traversal algorithm that follows one path as far as it can go before backtracking to explore the next unvisited branch.
DFS follows one path as deep as possible, then backtracks.
It uses recursion or an explicit stack, plus a visited set to handle cycles.
It runs in O(V + E) time with an adjacency list.
11DequeDouble-Ended Queue: A deque is a double-ended queue that lets you add and remove items at both the front and the back in constant time, so it can act as both a stack and a queue.
A deque supports adding and removing at both the front and the back in O(1) time.
It can act as a stack, a queue, or both at once.
It is typically built on a doubly linked list or a circular buffer.
12Dijkstra's Algorithm: Dijkstra's algorithm is a graph algorithm that finds the shortest paths from a starting node to every other node when all edge weights are zero or positive.
Dijkstra's algorithm finds the shortest paths from one source to all other nodes in a weighted graph.
It requires every edge weight to be zero or positive.
It repeatedly finalizes the closest unvisited node and relaxes that node's edges.
13Divide and Conquer: Divide and conquer is an algorithm design technique that splits a problem into smaller independent parts, solves each recursively, and combines the results.
Divide and conquer splits a problem into independent subproblems, solves each recursively, and combines the answers.
Merge sort, quicksort, binary search, and the fast Fourier transform are classic examples.
Running times are described by recurrences such as T(n) = 2T(n/2) + O(n), which gives O(n log n).
14Dynamic Programming: Dynamic programming is a technique for solving problems by breaking them into overlapping subproblems and storing each answer so none is solved twice.
DP works when a problem has overlapping subproblems and optimal substructure.
Each distinct subproblem is solved once, and its result is stored for reuse.
Top-down DP uses recursion with memoization; bottom-up DP fills a table from the smallest cases.
15Graph: A graph is a data structure made of nodes, called vertices, connected by edges, and is used to model relationships such as roads, friendships, and dependencies.
A graph is a set of nodes (vertices) connected by edges.
Edges can be directed or undirected, and weighted or unweighted.
An adjacency list uses O(V + E) memory and is the usual choice for sparse graphs, which have relatively few edges.
16Greedy Algorithm: A greedy algorithm builds a solution step by step, always taking the choice that looks best right now, without going back to reconsider earlier decisions.
A greedy algorithm always takes the choice that looks best right now and never backtracks.
It is optimal only when the problem has the greedy choice property and optimal substructure.
Examples include Dijkstra's algorithm, Huffman coding, and Kruskal's and Prim's minimum spanning tree algorithms.
17Hash Collision: A hash collision is two different inputs sharing a hash value or bucket, which hash tables must handle and cryptographic hashes must make infeasible to find.
A collision is when different inputs share a hash value or bucket.
Collisions are unavoidable and come early, as the birthday paradox shows.
Hash tables handle them with chaining or open addressing and resize by load factor.
18Hash Table: A hash table is a data structure that stores key-value pairs and uses a hash function to find the value for any key in constant time on average.
A hash table maps keys to values using a hash function.
Lookup, insert, and delete are O(1) on average and O(n) in the worst case.
A collision happens when two keys map to the same bucket; chaining and open addressing resolve it.
19Heap: A heap is a tree-based data structure that keeps the smallest or largest item at its root, so you can read it in O(1) and remove it in O(log n) time.
A min-heap keeps the smallest item at the root; a max-heap keeps the largest.
Peeking at the top is O(1), while inserting and removing the top are O(log n).
Building a heap from n items takes O(n) time.
20Insertion Sort: Insertion sort builds a sorted list one element at a time, putting each new one in its place among those already sorted, like sorting cards in your hand.
Insertion sort inserts each element into place within a sorted prefix.
It is O(n²) in the worst case but close to O(n) on nearly sorted data.
It is in-place, stable and can sort items as they arrive.
21Linear Search: Linear search finds a value by checking each element of a list one by one from the start until it finds a match or reaches the end, taking O(n) time.
Linear search checks elements one by one until it finds a match.
It takes O(n) time and needs no sorting or index.
It works on linked lists, streams and any search condition.
22Linked List: A linked list is a data structure that stores items in separate nodes, where each node holds a value and a reference to the next node in the chain.
Each node holds a value and a reference to the next node.
Inserting or removing at the head takes O(1) time.
Accessing an item by index or searching takes O(n) time, because you must walk the chain.
23LRU CacheLeast Recently Used Cache: An LRU (least recently used) cache holds a fixed number of items and, when full, evicts the one unused the longest, betting that recent data will be reused.
An LRU cache evicts the item unused for the longest time when it is full.
It assumes recently used data will be needed again soon.
A hash map plus a doubly linked list gives O(1) get and put.
24Merge Sort: Merge sort is a divide and conquer sorting algorithm that splits a list in half, sorts each half recursively, and merges the sorted halves in O(n log n) time.
Merge sort splits a list in half, sorts each half recursively, and merges the results.
It runs in O(n log n) time in the best, average, and worst case.
The array version needs O(n) extra memory.
25Priority Queue: A priority queue is a collection in which every item has a priority, and the highest-priority item is always removed first, no matter when it was added.
A priority queue always removes the highest-priority item first, not the oldest.
It is an abstract data type, most often implemented with a binary heap.
With a heap, insert and remove take O(log n), and peek takes O(1).
26Queue: A queue is a data structure that stores items in first in, first out (FIFO) order, so the item that has waited longest is always the next one removed.
A queue follows FIFO order: first in, first out.
Enqueue adds to the back and dequeue removes from the front, each in O(1) time when implemented well.
In Python, use collections.deque with append() and popleft() instead of list.pop(0).
27Quicksort: Quicksort is a divide and conquer sorting algorithm that partitions items around a chosen pivot, then sorts the smaller and larger groups the same way.
Quicksort partitions items around a pivot, then sorts each side recursively.
It averages O(n log n) time, but its worst case is O(n^2).
A random or median-of-three pivot makes the worst case very unlikely.
28Set: A Set is a collection that stores each distinct value at most once and can check whether a value is present very quickly, usually in constant time.
A set stores each distinct value only once, so duplicates are ignored.
Hash-based sets add, remove, and check membership in O(1) time on average.
Tree-based sets, such as Java's TreeSet, keep values sorted at O(log n) per operation.
29Sliding Window: The sliding window technique solves problems on contiguous parts of an array or string by updating a window as it slides instead of recomputing each subarray.
A sliding window tracks a contiguous range and updates it step by step.
Each element enters and leaves once, so scans are O(n).
Fixed windows keep size k; variable windows grow and shrink by a condition.
30Sorting Algorithm: A sorting algorithm is a step-by-step method for arranging items in a defined order, such as numbers from smallest to largest or names alphabetically.
Simple sorts like bubble, selection, and insertion sort run in O(n^2) time.
Merge sort and heap sort run in O(n log n) time even in the worst case; quicksort averages O(n log n) but can hit O(n^2).
Sorting by comparisons alone can't beat O(n log n) in the worst case.
31Stack: A stack is a data structure that stores items in last in, first out (LIFO) order, so the most recently added item is always the first one removed.
A stack follows LIFO order: last in, first out.
The core operations are push, pop, and peek, and each takes O(1) time.
In Python, a list with append() and pop() works as a stack; in JavaScript, an array with push() and pop() does.
32Topological Sort: Topological sort is an algorithm that orders the nodes of a directed acyclic graph so that for every edge from A to B, A comes before B in the resulting list.
A topological sort orders a directed graph's nodes so that every edge points forward in the list.
It exists only for directed acyclic graphs (DAGs).
Kahn's algorithm and the DFS-based method both run in O(V + E) time.
33Tree: A tree is a hierarchical data structure made of nodes connected by edges, with a single root node at the top and child nodes branching out below it.
A tree has one root, and every other node has exactly one parent.
Nodes without children are called leaves.
A balanced binary search tree supports search, insert, and delete in O(log n) time; an unbalanced one can degrade to O(n).
34Trie: A trie is a tree-shaped data structure that stores strings character by character, so all words that share a prefix also share the same path from the root.
A trie stores strings one character per level, and words with a common prefix share nodes.
Insert and lookup take O(m) time, where m is the length of the word, regardless of how many words are stored.
Finding all words with a prefix takes O(m) to reach the prefix, plus time proportional to the matches collected.
35Two Pointers: The two pointers technique walks an array or list with two indexes moved by simple rules, turning many problems that seem to need nested loops into one pass.
Two pointers scan a sequence with two indexes in one pass.
Opposite-end pointers solve pair problems in sorted arrays in O(n).
Fast and slow pointers find cycles and the middle of linked lists.
36Union-FindDisjoint Set Union: Union-find, or disjoint set union, is a data structure that tracks which elements share a group and can merge groups or check connectivity almost instantly.
Union-find tracks which elements belong to the same group.
find returns a group's root; union merges two groups.
Path compression and union by rank make operations nearly O(1).