Adjacency List vs Adjacency Matrix: When Would You Use Each?
Compare adjacency list vs adjacency matrix by space, time complexity, and when to use each for graph problems.
Expected Interview Answer
An adjacency list stores, for each vertex, only the list of its actual neighbors, using O(V + E) space that scales with how connected the graph really is, while an adjacency matrix stores a fixed V-by-V grid marking every possible pair of vertices, using O(V²) space but giving O(1) edge-existence lookups regardless of how sparse the graph is.
For sparse graphs — where E is much smaller than V², like most real-world social networks, road maps, or dependency graphs — an adjacency list is dramatically more memory-efficient and is also faster to iterate over a vertex's neighbors, since you only visit real edges instead of scanning an entire row of mostly-false entries. For dense graphs, or when the dominant operation is “does an edge exist between u and v”, an adjacency matrix wins because that check is a single array lookup, `matrix[u][v]`, in O(1), versus O(degree(v)) for scanning a list. The matrix also makes certain algorithms simpler to express, like Floyd-Warshall's all-pairs shortest path, which directly indexes matrix cells. In interviews, the deciding factors are graph density (E vs V²), whether edge-existence queries or neighbor-iteration dominate, and whether V² memory is even feasible — a million-vertex graph makes a dense matrix impossible regardless of algorithm needs.
- Adjacency list uses O(V + E) space, ideal for sparse real-world graphs
- Adjacency matrix gives O(1) edge-existence checks regardless of density
- Adjacency list iterates a vertex's neighbors in O(degree(v)), skipping non-edges
- Adjacency matrix simplifies algorithms like Floyd-Warshall that index by vertex pairs
AI Mentor Explanation
An adjacency list is like each team keeping a short personal notebook listing only the teams they have actually played against, so checking “who has Team A played” means flipping straight to their one small notebook. An adjacency matrix is like a giant wall chart with every team listed on both axes, where you mark a tick in every cell for every pair, even the vast majority who never played each other. Checking whether Team A played Team B on the wall chart is one instant glance at a fixed cell, but building and storing that chart for a 500-team tournament wastes huge space on empty cells. Coaches use notebooks for sparse regional leagues and the wall chart only when nearly every team really has played every other team.
Step-by-Step Explanation
Step 1
Estimate graph density
Compare actual edge count E to the maximum possible V²; sparse graphs favor a list, dense graphs favor a matrix.
Step 2
Identify the dominant operation
Frequent “does edge (u,v) exist” checks favor a matrix (O(1)); frequent “iterate all neighbors of v” favors a list (O(degree(v))).
Step 3
Check memory feasibility
A matrix needs O(V²) memory upfront; for large V (millions of vertices) this may simply not fit, forcing a list regardless of other tradeoffs.
Step 4
Match to the algorithm
Floyd-Warshall and dense-graph algorithms often index matrix cells directly; BFS/DFS/Dijkstra on sparse graphs iterate adjacency lists for efficiency.
What Interviewer Expects
- State the space complexity clearly: O(V + E) for a list vs O(V²) for a matrix
- Explain the time tradeoff for edge lookup (O(1) matrix) vs neighbor iteration (O(degree) list)
- Recommend adjacency list as the default for sparse, real-world graphs
- Recognize when a matrix is actually preferable: dense graphs, frequent edge-existence queries, or algorithms like Floyd-Warshall
Common Mistakes
- Defaulting to an adjacency matrix without considering memory blow-up on large sparse graphs
- Forgetting that edge-existence lookup is O(degree(v)) on an adjacency list, not O(1)
- Not mentioning that adjacency matrices make removing all edges of a vertex O(V) but a list makes it O(degree(v))
- Conflating adjacency list representation with the choice of BFS vs DFS (a separate, orthogonal decision)
Best Answer (HR Friendly)
“An adjacency list stores, for each node, just the neighbors it actually has, which is memory-efficient for the sparse, real-world graphs I usually deal with, like social networks or road maps. An adjacency matrix stores every possible pair of nodes in a big grid, which uses much more memory but makes checking whether two specific nodes are connected instant, so I would reach for it only on dense graphs or when that lookup is the main thing I need to do fast.”
Code Example
# Adjacency list: O(V + E) space, iterate neighbors in O(degree(v))
adj_list = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
def has_edge_list(adj, u, v):
return v in adj.get(u, []) # O(degree(u)) worst case
# Adjacency matrix: O(V^2) space, O(1) edge lookup
vertices = ["A", "B", "C"]
index = {v: i for i, v in enumerate(vertices)}
matrix = [[0] * len(vertices) for _ in vertices]
matrix[index["A"]][index["B"]] = 1
matrix[index["B"]][index["A"]] = 1
matrix[index["A"]][index["C"]] = 1
matrix[index["C"]][index["A"]] = 1
def has_edge_matrix(matrix, index, u, v):
return matrix[index[u]][index[v]] == 1 # O(1)Follow-up Questions
- How would memory requirements compare for a graph with 1 million vertices and 2 million edges under each representation?
- How does the choice between adjacency list and matrix affect the runtime of BFS?
- Why is Floyd-Warshall's all-pairs shortest path naturally expressed with an adjacency matrix?
- How would you represent a weighted graph in each of the two structures?
MCQ Practice
1. What is the space complexity of an adjacency list for a graph with V vertices and E edges?
An adjacency list only stores each vertex once and each edge once (or twice for undirected graphs), giving O(V + E) space.
2. What is the time complexity of checking if an edge exists using an adjacency matrix?
An adjacency matrix stores every pair directly, so matrix[u][v] is a single array lookup regardless of graph size.
3. For which scenario is an adjacency list clearly preferable to an adjacency matrix?
For sparse graphs, an adjacency matrix's O(V^2) memory becomes infeasible, while an adjacency list scales with the actual edge count.
Flash Cards
What is the space complexity of an adjacency matrix? — O(V^2), regardless of how many edges actually exist.
What is the space complexity of an adjacency list? — O(V + E), scaling with the actual number of edges.
Which representation gives O(1) edge-existence lookup? — The adjacency matrix.
Which representation is better for iterating a vertex's neighbors? — The adjacency list, in O(degree(v)) instead of scanning a full row.