Adjacency list vs matrix
easyA matrix costs V² whatever the edge count. For a social graph with a million users and fifty friends each, lists win by four orders of magnitude - and nearly every algorithm here wants a list.
O(1) matrix edge testWorst O(V) matrix neighboursSpace O(V²) matrix, O(V + E) listSaved in this browser - no sign-up, nothing sent anywhere.
How adjacency list vs matrix works
A graph is just vertices and edges, but the container you pick decides the cost of every question you ask it. An adjacency matrix is a V by V table of booleans: cell [u][v] answers 'is there an edge?' in one array access. An adjacency list keeps one bucket per vertex holding only its neighbours - for the 8-node graph here, that is 20 references instead of 64 cells.
The decision is driven by density, and real graphs are sparse. A social network with a million users and fifty friends each has fifty million edges; a matrix would allocate a trillion cells to store them, and lists win by four orders of magnitude. Road networks, dependency graphs and web graphs all sit in the same regime - E close to V, nowhere near the V² a matrix budgets for.
The traversal algorithms in this category settle the choice. BFS, DFS, Dijkstra and topological sort all ask 'give me the neighbours of u' over and over. A list answers in O(deg u); a matrix scans a whole O(V) row even when u has one neighbour, which quietly turns an O(V + E) traversal into O(V²).
Step by step
- The default graph has 8 vertices A through H and 10 undirected edges. Both structures start empty: an 8 by 8 matrix of zeros, and eight empty lists.
- Edge A-B arrives. The matrix sets two cells, matrix[A][B] and matrix[B][A], because an undirected edge must be readable from both ends.
- The list version appends once per endpoint: B joins A's bucket and A joins B's. Two references, no matter how many vertices exist.
- Nine more edges repeat the pattern. After all 10, the matrix has flipped 20 of its 64 cells; the other 44 stay zero forever.
- The lists hold exactly 20 references across 8 buckets - one per edge direction - so storage tracks the edge count, not the vertex count squared.
- Final tally: this graph is 36% dense and already favours the list. At real-world scale the gap becomes decisive.
Complexity
| Best case time | O(1) matrix edge test |
|---|---|
| Worst case time | O(V) matrix neighbours |
| Space | O(V²) matrix, O(V + E) list |
Reference implementation
Python
# Adjacency list - the default choice for sparse graphs.
from collections import defaultdict
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # omit for a directed graph
# Adjacency matrix - constant-time edge tests, quadratic memory.
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = matrix[v][u] = 1
# Rule of thumb: E is O(V) for most real graphs (road networks,
# social graphs, dependency graphs), so a matrix wastes almost
# all of its V^2 cells on zeros.JavaScript
// Adjacency list
const adj = new Map();
for (const [u, v] of edges) {
if (!adj.has(u)) adj.set(u, []);
if (!adj.has(v)) adj.set(v, []);
adj.get(u).push(v);
adj.get(v).push(u);
}
// Adjacency matrix
const m = Array.from({ length: n }, () => new Array(n).fill(0));
for (const [u, v] of edges) { m[u][v] = 1; m[v][u] = 1; }Worth noticing
The choice is decided by density
A matrix costs V² regardless of how many edges exist. For a social graph with a million users and fifty friends each, that is a trillion cells to store fifty million edges. Lists win by four orders of magnitude.
Matrices win when you ask 'is there an edge?' constantly
Floyd-Warshall, dense flow networks and small fixed graphs all favour the matrix: one array access instead of a scan. Below a few hundred vertices the memory difference stops mattering.
Almost every algorithm here wants a list
BFS, DFS, Dijkstra and topological sort all iterate over a vertex's neighbours. With a list that is O(deg u); with a matrix it is O(V) even for a vertex with one neighbour - which turns an O(V+E) traversal into O(V²).
Common pitfalls
- Reaching for a matrix on a sparse graph. At 100,000 vertices that is 10 billion cells - it will not fit in memory, while the list needs a few megabytes.
- Scanning matrix rows inside BFS or DFS. Each neighbour query costs O(V) instead of O(deg u), which silently turns an O(V + E) traversal into O(V²).
- Forgetting to mirror undirected edges. Store A-B in only one direction and half your traversals will not see the edge - a bug that only shows on some start nodes.
- Ignoring the third option. Kruskal and Bellman-Ford iterate over raw edges, so a plain edge list - no per-vertex indexing at all - is the natural fit for both.
Where it is used
- Social networks and web graphs - millions of vertices, sparse by nature, always adjacency lists.
- Floyd-Warshall and dense flow networks, where constant-time edge tests justify the V² memory.
- Edge lists feed Kruskal's sort and Bellman-Ford's relaxation loop directly.
- Interviews: stating which representation you will use, and why, is the expected first line of any graph answer.
Frequently asked questions
What are the time and space costs of an adjacency matrix versus an adjacency list?
A matrix answers hasEdge(u, v) in O(1) but takes O(V) to list a vertex's neighbours and O(V²) space regardless of edge count. A list stores O(V + E) and returns neighbours in O(deg u), which is why traversal algorithms prefer it.
Which graph representation should I use in a coding interview?
Default to an adjacency list - a map from vertex to neighbour array, built in a few lines. Nearly every interview graph is sparse, and BFS, DFS, Dijkstra and topological sort all iterate neighbours, which lists serve in O(deg u).
When is an adjacency matrix actually better?
When the graph is dense, when you test specific edges constantly, or when the algorithm is matrix-shaped - Floyd-Warshall reads and writes d[i][j] directly. Below a few hundred vertices the O(V²) memory stops mattering, so convenience can win.
How do I store a weighted graph?
In a list, keep (neighbour, weight) pairs instead of bare ids. In a matrix, store the weight in the cell and a sentinel like infinity where no edge exists - zero is a bad sentinel, because real edges can weigh zero.