Fundamentals · Medium · Free
Adjacency matrix vs adjacency list — space/time trade-offs.
FresherFundamentalsData Structures & Algorithms
Adjacency matrix vs list
Choose how you store edges—impacts memory and time to iterate neighbors.
| Matrix | List | |
|---|---|---|
| Space | O(V²) | O(V+E) |
| Edge lookup | O(1) | O(degree) |
| Best for | Dense graphs | Sparse social/web graphs |
java
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(u).add(v); // undirected: also adj.get(v).add(u)Most interview graphs are sparse—adjacency list default.