Adjacency List: Memory Efficiency
What you'll learn: You'll understand why adjacency lists are the memory-efficient choice for sparse graphs, using only O(V+E) space.
The Space Formula Explained
An adjacency list stores exactly what exists in your graph—no more, no redundant empty slots. For each of the V vertices, you maintain a container (array or linked list), and across all vertices combined, you store exactly E edges (or 2E entries for undirected graphs, since each edge appears in both vertices' lists).
This gives us O(V + E) space complexity:
- V for the array of vertex containers
- E (or 2E) for the actual edge entries
Why This Matters: Sparse Graphs
Most real-world graphs are sparse—they have far fewer edges than the theoretical maximum of V². Think of social networks: you might have millions of users (V), but each person only knows hundreds of friends, not millions.
Compare this to an adjacency matrix, which always uses O(V²) space regardless of how many edges actually exist. If you have 10,000 vertices but only 50,000 edges, an adjacency list uses space proportional to ~60,000 items, while a matrix wastes space for 100,000,000 cells!
The Analogy
Imagine tracking friendships in a school:
- Adjacency matrix: Print a giant grid with every student's name on both axes, check or leave blank each cell (wastes paper for non-friends)
- Adjacency list: Each student carries a list with only their actual friends' names (efficient!)
Key Takeaway: Adjacency lists achieve O(V+E) memory efficiency by storing only what exists, making them ideal when E << V², which describes most practical graphs.