Stack: push to top, pop from top. Function call stacks, undo operations. Queue: enqueue at back, dequeue from front. Print jobs, breadth-first search.
Linked Lists
Linked List: O(1) insert at head, O(n) search ā no random access
Linked Lists
Fast insertion, slow search ā a chain of nodes
Each node stores data + pointer to next. No contiguous memory. Fast insert/delete at head. Must traverse to find element. Doubly linked: each node has prev and next pointers.
Binary Search Trees
BST: left < root < right ā O(log n) average search
Binary Search Trees
The BST property enables fast search, insert, and delete
In a BST: left subtree < root < right subtree. O(log n) average for search/insert/delete. O(n) worst case when unbalanced. AVL and Red-Black trees self-balance.
Hash Tables
Hash Table: key ā hash function ā index ā O(1) average lookup
Hash Tables
The data structure behind dictionaries, sets, and caches
Hash function converts key to array index. O(1) average for insert, delete, lookup. Collision handling: chaining (linked list) or open addressing. Python dict, Java HashMap.
Graphs model networks ā two fundamental ways to traverse them
Vertices (nodes) connected by edges. BFS (breadth-first search): uses queue, finds shortest path in unweighted graph. DFS (depth-first search): uses stack (or recursion), explores as far as possible before backtracking.
Arrays
Array: O(1) random access by index. O(n) insert/delete in middle. Fixed size (static) or dynamic.
Arrays
The most fundamental data structure ā contiguous memory
Elements stored in contiguous memory ā O(1) random access by index. Insert/delete at end: O(1). Insert/delete in middle: O(n) ā must shift elements. Static array: fixed size. Dynamic array (ArrayList, Python list): doubles when full ā amortized O(1) append.
Complete binary tree stored as array. Max-heap: parent always ā„ children ā root is maximum. Min-heap: parent ā¤ children ā root is minimum. Insert: add at end, bubble up ā O(log n). Extract max/min: swap root with last, remove, bubble down ā O(log n). Heapsort: O(n log n).
Tries
Trie (prefix tree): efficient string storage and retrieval. Each node = one character. Used in autocomplete.
Tries
The data structure that powers autocomplete and spell-check
Each node represents one character. Root ā complete words traced down the tree. Search/insert: O(m) where m = string length ā independent of number of stored strings. Applications: autocomplete, spell-check, IP routing, DNA sequence matching. More memory than hash table but faster prefix lookups.
Balanced Binary Trees
AVL tree: self-balancing BST. Balance factor = height(left) - height(right) must be -1, 0, or 1.
Balanced Binary Trees
Self-balancing trees that guarantee O(log n) operations
BST degenerates to O(n) if elements inserted in sorted order (becomes a linked list). AVL tree: automatically rebalances via rotations when balance factor falls outside [-1, 0, 1]. Red-Black tree: less strictly balanced but faster insertions ā used in Java TreeMap, C++ std::map.
Two ways to store a graph ā choose based on density
Adjacency matrix: 2D array, matrix[i][j]=1 if edge exists. O(1) edge lookup. O(VĀ²) space ā wastes space for sparse graphs. Adjacency list: array of lists, each vertex stores its neighbors. O(V+E) space. Better for sparse graphs (most real graphs). Slower edge lookup O(degree).
Matrix
O(1) edge lookup, O(VĀ²) space ā dense graphs
List
O(V+E) space ā sparse graphs, most algorithms
Circular Buffer
Circular buffer (ring buffer): fixed-size queue using array with wraparound ā efficient for streaming data
Circular Buffer
A queue that reuses space by wrapping around
Fixed-size array with head and tail pointers. Enqueue: add at tail, advance tail (mod size). Dequeue: remove at head, advance head. When tail reaches end, wraps to beginning. O(1) enqueue and dequeue. Used in: audio/video streaming buffers, OS I/O buffers, producer-consumer problems.
Sets
Set: unordered collection of unique elements. O(1) average for add/remove/contains using hashing.
Sets
The data structure for unique collections and membership testing
Set stores unique values ā duplicates ignored. HashSet: O(1) average add/contains/remove, no ordering. TreeSet: O(log n), maintains sorted order. Useful for: removing duplicates from a list, membership testing, finding common elements (intersection), finding differences. Python set(), Java HashSet.