Graph Adjacency List vs Adjacency Matrix
Choosing the right graph representation — adjacency list or adjacency matrix — directly impacts algorithm efficiency and is a core concept in CS courses, FAANG interviews, and graph algorithm design. This set covers space complexity, lookup speed, and when each representation is optimal for sparse vs. dense graphs.
Interactive Deck
5 CardsWhen to use an adjacency list?
When to use an adjacency matrix?
Master this topic effortlessly.
Study G helps you master any topic effortlessly using proven learning algorithms and smart review timing
Download Study GFrequently Asked Questions
What is the difference between adjacency list and adjacency matrix?
An adjacency matrix is a V×V grid storing all edge relationships in O(1), using O(V²) space. An adjacency list stores only existing edges, using O(V+E) space and O(degree) lookup time.
- Matrix: fast lookup, high memory
- List: low memory, slower lookup
Which graph representation is better for BFS and DFS?
Adjacency lists are preferred for BFS and DFS because they allow efficient iteration over only existing neighbors. With a matrix, you must scan an entire row (O(V)) even when most edges do not exist.
How much memory does an adjacency matrix use?
An adjacency matrix requires O(V²) space, storing a value for every possible vertex pair. For a graph with 1000 nodes, that means 1,000,000 entries regardless of actual edge count.