Stack = LIFO (Last In First Out, like a stack of plates). Queue = FIFO (First In First Out, like a line).
Stack vs Queue
Last In First Out vs First In First Out
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 (Adelson-Velsky and Landis) 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.
Mnemonic
What it means
✅ 0❌ 0📚 0 left
No saved cards yet — click ☆ Save on any memory trick.
🎓 Common Exam Questions
Q: Compare arrays, linked lists, and hash tables.
A: Arrays: O(1) random access by index, O(n) insert or delete in middle. Use when random access needed and cache performance matters. Linked Lists: O(1) insert at head, O(n) search, no random access. Use when frequent insert or delete at arbitrary positions. Hash Tables: O(1) average lookup, insert, delete; O(n) worst case. Use when key-value mapping and fast lookup are priorities. Not ordered.
Q: Explain BST, AVL tree, and when BST degrades to O(n).
A: BST: left less than parent less than right for every node. O(log n) in balanced tree. Problem: inserting sorted elements creates a linked list — all O(n). AVL (Adelson-Velsky and Landis) tree: self-balancing BST. Balance factor equals height(left) minus height(right), must be -1, 0, or 1. Rotations restore balance. Guarantees O(log n) worst case. Red-Black trees are another self-balancing BST used in standard libraries.
Q: What is a heap and how does heap sort work?
A: Heap: complete binary tree where every parent is greater than or equal to children (max-heap). Implemented as array: node at index i has left child at 2i+1, right at 2i+2. Insert: add at end, bubble up O(log n). Extract max: remove root, last element to root, bubble down O(log n). Build heap from array: O(n). Heap sort: build max-heap O(n), repeatedly extract max O(log n) each — total O(n log n). In-place, no extra space.
Q: What is a graph and what are the main traversal algorithms?
A: Graph: vertices plus edges. Can be directed or undirected, weighted or unweighted. BFS (Breadth-First Search): queue, level by level, shortest path in unweighted graphs, O(V+E). DFS (Depth-First Search): stack or recursion, deep before backtracking, used for topological sort, cycle detection, connected components, O(V+E). Key algorithms: Dijkstra shortest path weighted, Bellman-Ford handles negative edges, Kruskal and Prim for minimum spanning tree.
Q: What is a Trie and why is it better than a hash table for prefix searches?
A: Trie stores strings as paths — each node is one character. Insert and lookup: O(L) where L is string length. Hash tables also O(L) per lookup but cannot efficiently find all strings with a given prefix. Trie advantage: prefix search is O(prefix length plus results) — naturally supports autocomplete. Find all words starting with a prefix: navigate to last prefix character, then DFS from there. Also used for spell checking and IP routing. Disadvantage: high memory — each node can have up to 26 children.