Adjacency Matrix vs. Adjacency List

When working with graphs in computer science, one of the first decisions you need to make is how to store them efficiently. The two most common representations are the Adjacency Matrix and the Adjacency List. Each has its advantages and trade-offs, making them suitable for different scenarios.

In this article, we’ll compare these two data structures in terms of memory usage, performance, and real-world applications to help you decide which one to use for your projects.

1. Adjacency Matrix

An adjacency matrix is a 2D array where each cell [i][j] indicates whether there is an edge between vertex i and vertex j.

Structure

For a graph with n vertices, we use an n × n matrix:

• matrix[i][j] = 1 (or weight w) if there is an edge from i to j
• matrix[i][j] = 0 if there is no edge

Example

For a graph with 4 vertices:

   0  1  2  3  
0 [0, 1, 0, 1]  
1 [1, 0, 1, 1]  
2 [0, 1, 0, 0]  
3 [1, 1, 0, 0]  

Time Complexity

• Checking if an edge exists: O(1)
• Adding an edge: O(1)
• Removing an edge: O(1)
• Iterating over all neighbors of a node: O(n)

Space Complexity

• O(n²) – Since we store n × n values, this is inefficient for large, sparse graphs.

Pros & Cons

✅ Fast lookups – Checking if an edge exists is constant time O(1).
✅ Simple implementation – Easy to code and understand.
❌ Memory-intensive – Always requires O(n²) space, even for sparse graphs.
❌ Slow iteration – Iterating over neighbors takes O(n) time.

2. Adjacency List

An adjacency list represents a graph as an array of linked lists or vectors. Each vertex stores a list of adjacent nodes.

Structure

For n vertices, we store an array where each index corresponds to a list of neighbors.

Example

For the same graph as above:

0 → {1, 3}  
1 → {0, 2, 3}  
2 → {1}  
3 → {0, 1}  

Time Complexity

• Checking if an edge exists: O(degree of node) (worst case O(n), average case O(1) for sparse graphs)
• Adding an edge: O(1)
• Removing an edge: O(degree of node)
• Iterating over all neighbors of a node: O(degree of node) (much faster for sparse graphs)

Space Complexity

• O(n + m), where m is the number of edges – more efficient for sparse graphs.

Pros & Cons

✅ Efficient for sparse graphs – Uses much less memory than an adjacency matrix.
✅ Faster iteration – Traversing neighbors is efficient for small-degree nodes.
❌ Slower edge lookup – Checking if an edge exists can take O(n) in the worst case.

3. When to Use Which?

Use Adjacency Matrix When:

• The graph is dense (m ≈ n²).
• You need fast edge lookups.
• The graph size is small to moderate.

Use Adjacency List When:

• The graph is sparse (m << n²).
• Memory efficiency is important.
• You frequently iterate over neighbors.

4. Conclusion

Choosing between an Adjacency Matrix and an Adjacency List depends on your graph’s characteristics and the operations you need to perform.

• Use an adjacency matrix for small, dense graphs where fast edge lookups are needed.
• Use an adjacency list for large, sparse graphs where memory efficiency and fast traversal are important.