A strong answer
An adjacency list stores, for each vertex, the list of its neighbors: O(V + E) memory, O(degree) to list a vertex's neighbors, and O(degree) to test a specific edge (O(1) on average if neighbors are kept in hash sets). An adjacency matrix stores a V × V table: O(V²) memory, O(1) to test an edge, but O(V) to list neighbors, because the whole row must be scanned.
Most graph algorithms, BFS, DFS, Dijkstra and topological sort, spend their time listing neighbors and touch each edge a constant number of times, so with lists they run in O(V + E). With a matrix they become O(V²) regardless of how many edges exist. Since almost all real graphs are sparse, with E far below V², lists are the default: a network of 100 million users with a few hundred friends each needs tens of billions of list entries but 10¹⁶ matrix cells.
A matrix makes sense for small or dense graphs, when constant-time edge checks matter, or for algorithms built on it, such as Floyd-Warshall for all-pairs shortest paths, or matrix-based methods for counting paths. Edge lists are how graphs usually arrive and suit algorithms that sort edges, such as Kruskal's.
In practice, vertices with arbitrary keys use a hash map from vertex to a set of neighbors, and large static graphs use compressed sparse row: one array of all neighbors and one of offsets, which removes per-list overhead and reads neighbors contiguously, which is good for the cache.
What the interviewer is listening for
- Memory and the cost of the two key operations for each.
- Sparse versus dense, with the consequence for algorithm running time.
- Concrete cases for each, and awareness of practical variants.
Common mistakes
- Choosing a matrix for large sparse graphs.
- Forgetting that undirected edges are stored twice in lists.
- Claiming lists are always better, even for dense graphs or constant-time edge queries.