There are two standard ways to store a graph, and the choice comes down to density and which operation you run most.
Adjacency list
Each vertex maps to a list of its neighbors — in Java, Map<Node, List<Node>> or List<List<Integer>> for 0..V-1 vertices.
Map<Integer, List<Integer>> g = new HashMap<>();
g.computeIfAbsent(u, k -> new ArrayList<>()).add(v); // edge u -> v- Space O(V + E) — you store exactly what exists. For a sparse graph (
E ≈ V) this is dramatically smaller than a matrix. - Iterating a vertex's neighbors is O(deg(v)) — optimal, since BFS/DFS do exactly that.
- "Is there an edge u→v?" is O(deg(u)) — you scan the list. Slower than a matrix.
Adjacency matrix
A boolean[V][V] (or int[V][V] for weights) where m[u][v] flags the edge.
- Space O(V²) — fixed, regardless of how few edges exist. Wasteful for sparse graphs.
- Edge query O(1) — a single array read; its one real advantage.
- Iterating neighbors is O(V) — you scan a whole row even if the vertex has two neighbors.
The trade-off
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| Space | List: O(V+E) | Matrix: O(V²) | — | list wins on sparse graphs |
| Edge exists? | List: O(deg) | Matrix: O(1) | — | matrix wins |
| Iterate neighbors | List: O(deg) | Matrix: O(V) | — | list wins |
| Add edge | List: O(1) | Matrix: O(1) | — | tie |
Use a list for sparse graphs (the common case — road networks, dependency graphs, social graphs) and whenever you traverse. Use a matrix when the graph is dense (E ≈ V²), the vertex count is small and fixed, or you do many O(1) edge-existence checks (e.g., Floyd-Warshall, which is inherently V³).