Data Structures¶
Choosing the right data structure is half the battle. This guide helps you understand when and why to use each structure, with complexity analysis and practice links.
-
Linear Structures
Arrays, Linked Lists, Stacks, Queues. Foundation for everything else.
-
Associative Structures
Hash Tables and Sets for O(1) lookups and membership tests.
-
Hierarchical Structures
Trees, Heaps, and Tries for ordered data and prefix operations.
-
Graph Structures
Adjacency lists and matrices for modeling relationships.
Linear Structures¶
Sequential data with defined ordering and position-based access.
| Structure | Best For | Operations | Links |
|---|---|---|---|
| Arrays | Random access, iteration, prefix sums | Index O(1), Search O(n) | LC 238 |
| Linked Lists | Frequent insertions, no reallocation | Insert O(1), Access O(n) | LC 206 |
| Stacks | LIFO, undo/redo, parentheses matching | Push/Pop O(1) | LC 20 |
| Queues | FIFO, BFS traversal, scheduling | Enqueue/Dequeue O(1) | LC 933 |
Associative Structures¶
Key-value mappings and membership testing with constant-time operations.
| Structure | Best For | Operations | Links |
|---|---|---|---|
| Hash Tables | Counting, deduplication, lookups | Get/Set O(1) avg | LC 1 |
| Hash Sets | Unique elements, membership tests | Add/Contains O(1) avg | LC 217 |
Hierarchical Structures¶
Tree-based structures for ordered access and hierarchical relationships.
| Structure | Best For | Operations | Links |
|---|---|---|---|
| Binary Trees | Traversals, depth calculations | Varies by balance | LC 104 |
| Binary Search Trees | Ordered data, range queries | O(log n) balanced | LC 98 |
| Heaps | Top-k, scheduling, priority queues | Insert/Extract O(log n) | LC 347 |
| Tries | Prefix matching, autocomplete | O(m) where m=key length | LC 208 |
Graph Structures¶
Model relationships and connections between entities.
| Structure | Best For | Space | Links |
|---|---|---|---|
| Adjacency List | Sparse graphs, traversals | O(V + E) | LC 200 |
| Adjacency Matrix | Dense graphs, edge lookups | O(V^2) | LC 547 |
Specialized Structures¶
Advanced structures for specific problem domains.
Complexity Reference¶
Master this table for interviews.
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1)* | O(1)* | O(n) |
| Hash Table | - | O(1) | O(1) | O(1) | O(n) |
| BST (balanced) | - | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(1) top | O(n) | O(log n) | O(log n) | O(n) |
| Trie | - | O(m) | O(m) | O(m) | O(n*m) |
* At known position. m = key length, n = number of elements
Decision Guide¶
