Dynamic array backed by contiguous memory. O(1) random access and amortized O(1) append. The default Python container — use it as a list, stack, or combine with slicing for prefix sums.
Unordered key→value store backed by a hash table. O(1) average get/set/delete and membership check. Python's dict preserves insertion order since 3.7. Use defaultdict and Counter for frequency counting.
Unordered collection of unique elements. O(1) average add/remove/membership. Use when you need fast deduplication or O(1) "have I seen this?" checks — the set's superpower over lists.
Last-In-First-Out. Push and pop from the same end (the top). Python's list works perfectly — append() to push, pop() to pop. Monotonic stacks are the key interview pattern.
First-In-First-Out. Enqueue at the back, dequeue from the front. Always use collections.deque — list.pop(0) is O(n). The BFS traversal pattern lives here.
O(1) append and pop at both ends. Generalizes stack and queue. Key pattern: monotonic deque for sliding window maximum. Also use maxlen for a bounded window that auto-evicts old elements.
Nodes linked by next pointers. O(1) head insert/delete, O(n) search. The dummy head pattern eliminates edge cases. Two-pointer tricks (fast/slow) detect cycles and find midpoints.
Each node has at most two children. BST property: left subtree < node < right subtree. In-order traversal yields a sorted sequence. O(log n) operations on a balanced tree, O(n) worst case (degenerate).
Complete binary tree where every parent ≤ its children. heap[0] is always the minimum. Python's heapq is a min-heap. For max-heap: negate values. O(log n) push/pop, O(1) peek, O(n) heapify.
Nodes (vertices) connected by edges. Represent as an adjacency list with defaultdict(list). BFS finds shortest paths (unweighted). DFS explores depth-first and powers cycle detection, topological sort, and connected components.
Tree for storing strings character by character. Common prefixes share nodes. O(m) insert/search/startsWith where m = word length. Best structure for prefix matching, autocomplete, and word existence checks.
Tracks which elements belong to the same connected component. Near-O(1) per operation with path compression and union by rank. Essential for Kruskal's MST, cycle detection in undirected graphs, and grid connectivity problems.