Adjacency list vs adjacency matrix — when to use which?

Deep dive

The choice is mostly about density and the operations you care about.

Adjacency list:

• Memory: O(V + E)
• Iterate neighbors of u: O(deg(u))
• Check edge (u, v): O(deg(u)) unless you store a set per node

Adjacency matrix:

• Memory: O(V^2)
• Iterate neighbors of u: O(V) (scan the row)
• Check edge (u, v): O(1)

When to choose which

• Sparse graphs (E much smaller than V^2): adjacency list.
• Dense graphs, or you do tons of edge-existence queries: matrix.
• Algorithms:
• BFS/DFS/Dijkstra: list is usually best.
• Floyd–Warshall / transitive closure: matrix is natural (often optimized with bitsets).

Examples

// Adjacency list
const adj: number[][] = Array.from({ length: n }, () => [])
adj[u].push(v)

// Adjacency matrix
const mat: boolean[][] = Array.from({ length: n }, () => Array(n).fill(false))
mat[u][v] = true