Graph Representations: Adjacency List and Edge List
You'll learn two memory-efficient ways to store graphs and when to use them instead of adjacency matrices.
Beyond Matrices: List-Based Representations
While adjacency matrices offer fast lookups, they waste space for sparse graphs (graphs with few edges relative to possible connections). Two list-based alternatives trade some lookup speed for dramatic memory savings.
Adjacency List
An adjacency list stores each node with a list of its neighbors:
Node 0: [1, 3]
Node 1: [0, 2]
Node 2: [1, 3]
Node 3: [0, 2]
Think of it like a contact list on your phone—you only record people you actually know, not every person on Earth with "no connection" entries.
Storage: O(V + E) space, where V = nodes, E = edges
Access: Finding all neighbors of node i is O(1), but checking if edge (i,j) exists takes O(degree(i))
Edge List
An edge list is simply a list of all edges as pairs:
[(0, 1), (0, 3), (1, 2), (2, 3)]
This is the most compact representation—just the connections, nothing else.
Storage: O(E) space
Access: Finding neighbors requires scanning the entire list O(E)
Comparing the Three
- Adjacency matrix: Fast lookups, heavy memory (O(V²))—best for dense graphs
- Adjacency list: Balanced—best for most real-world sparse graphs and when you frequently traverse neighbors
- Edge list: Minimal storage—best when you just need to iterate all edges once (e.g., loading data)
Most Graph Neural Network libraries (like PyTorch Geometric) use edge lists internally for efficiency, converting to other forms only when needed.
Key Takeaway: Adjacency lists and edge lists save massive memory on sparse graphs; choose adjacency lists for neighbor traversal or edge lists for pure storage and batch processing.