Data Structures Overview#
This section covers implementations and complexity of core structures used in interviews. For pattern-based problem solving, see DSA Patterns. For curated practice lists, use the DSA Venn Explorer or Programming Overview.
When to use what#
| Need | Prefer | Why |
|---|---|---|
| Fast index access, sequential scan | Array / Python list |
O(1) random access; cache-friendly |
| Frequent insert/delete at ends only | collections.deque |
O(1) append/pop both ends |
| Frequent insert/delete in the middle | Linked list (conceptually) | O(1) splice if you already have the node; Python lists are O(n) for middle inserts |
| LIFO processing (undo, parsing, DFS stack) | Stack (list or linked) |
O(1) push/pop at one end |
| FIFO processing (BFS, scheduling) | Queue (collections.deque) |
O(1) enqueue/dequeue; never use list.pop(0) |
| O(1) average lookup / deduplication | Hash map / set (dict, set) |
Expected O(1) membership and update |
| Sorted order + O(log n) search | Binary search tree (balanced in theory) | In-order traversal yields sorted sequence |
| Always-min or always-max | Heap (heapq) |
O(log n) insert/extract; O(1) peek |
| Prefix on strings / autocomplete | Trie | Shared prefixes stored once |
| Relationships / dependencies / grids | Graph (adjacency list) | Models networks, paths, connectivity |
Complexity at a glance#
| Structure | Access | Search | Insert | Delete | Notes |
|---|---|---|---|---|---|
| Array / list | O(1) | O(n) | O(1)* append | O(1)* pop end | *Amortized for dynamic arrays |
| Linked list | O(n) | O(n) | O(1) at known node | O(1) at known node | No random access |
| Stack | O(n) | O(n) | O(1) push | O(1) pop | Top only |
| Queue (deque) | O(n) | O(n) | O(1) enqueue | O(1) dequeue | FIFO |
| Hash table | — | O(1)* avg | O(1)* avg | O(1)* avg | *Worst case O(n) |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | Unbalanced → O(n) worst |
| Heap | O(n) | O(n) | O(log n) | O(log n) extract | O(1) min/max peek |
| Trie (length L) | — | O(L) | O(L) | O(L) | Alphabet size matters |
| Graph (adj list) | — | O(V+E) BFS/DFS | O(1) add edge | O(E) remove edge | V = vertices, E = edges |
How the pages in this section are organized#
- Linear structures — List, Linked List, Stack, Queue, Deque
- Associative structures — Hashing
- Hierarchical structures — Tree, Binary Search Tree, Heap, Trie
- Network structures — Graph
Each page includes: when to use it, operation complexities, Python standard-library options, and a from-scratch implementation for interview whiteboards.
Pattern recognition (problem → approach)#
FAANG interviews usually test patterns on top of structures, not the structures alone. When you see a signal, reach for the matching technique:
| Signal | Pattern / structure | Examples |
|---|---|---|
| Sorted array + pair / triple sum | Two pointers | Two Sum II, 3Sum |
| Subarray sum equals K | Prefix sum + hash map | LC 560 |
| Longest/shortest subarray with constraint | Sliding window | LC 3, 76, 424 |
| Linked list cycle / middle | Fast & slow pointers | LC 141, 142, 876 |
| Next greater / histogram area | Monotonic stack | LC 739, 84 |
| Sliding window min/max | Monotonic deque | LC 239 |
| K-th largest / merge K lists | Heap (heapq) |
LC 215, 23 |
| Shortest path unweighted / levels | BFS + deque |
LC 127, 994 |
| Connectivity / redundant edge | Union-Find | LC 684, 547 |
| Sorted answer + feasibility check | Binary search on answer | LC 875, 1011 |
| Overlapping intervals | Sort + merge | LC 56, 57 |
| Grid as graph | BFS/DFS + directions array | LC 200, 695 |
Full problem lists: DSA Patterns · DSA Sheets · Programming Overview
Python basics vs programming implementations#
- Python Basics → Data Structures — built-in
list,tuple,dict,set, and everyday usage. - This section — how those abstractions work internally and how to implement them manually when asked in interviews.