Adjacency Matrix vs Adjacency List: A Detailed Comparison

Graphs are fundamental data structures widely used in computer science, especially in applications like social networks, navigation systems, and recommendation engines. But before we start performing operations like traversal or shortest path search on graphs, it’s crucial to choose the right graph representation. Two of the most popular representations are:

• Adjacency Matrix
• Adjacency List

In this blog, we’ll dive deep into the difference between Adjacency Matrix and Adjacency List, including definitions, examples, memory usage, performance, and use cases. Let’s get started.

What is an Adjacency Matrix?

An Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in the graph. The element at row i and column j is:

• 1 or the edge weight if there is an edge from vertex i to vertex j
• 0 if there is no edge

Example (Unweighted Undirected Graph)

Graph:

A -- B
|    
C

Let’s label vertices as A=0, B=1, C=2. The adjacency matrix will look like:

What is an Adjacency List?

An Adjacency List represents a graph as a list of lists. Every vertex has a list of adjacent vertices (connected nodes).

Example (Unweighted Undirected Graph)

Graph:

A -- B
|    
C

Adjacency List:

A: B → C  
B: A  
C: A

In code, it may look like:

List<List<Integer>> graph = new ArrayList<>();
graph.add(Arrays.asList(1, 2)); // A
graph.add(Arrays.asList(0));    // B
graph.add(Arrays.asList(0));    // C

Key Differences Between Adjacency Matrix and Adjacency List

Performance Comparison

🔎 Note: In a dense graph, E ≈ V², and in a sparse graph, E << V².

When to Use Which?

✅ Use Adjacency Matrix when:

• The graph is dense (many edges).
• You need to check for the existence of an edge very frequently.
• Memory is not a major concern.
• You are implementing graph algorithms like Floyd-Warshall (which benefits from matrix form).

✅ Use Adjacency List when:

• The graph is sparse (few edges).
• You want to save space.
• You often need to iterate over neighbors.
• You are implementing DFS, BFS, or Dijkstra’s Algorithm.

Real-life Analogies

• Adjacency Matrix: Like a city map with every street marked, even if some cities aren’t directly connected.
• Adjacency List: Like a contact list where each person only has their actual friends’ names—not everyone.

Sample Code in Java

Adjacency Matrix:

int V = 3;
int[][] matrix = new int[V][V];

// Edge A-B
matrix[0][1] = 1;
matrix[1][0] = 1;

// Edge A-C
matrix[0][2] = 1;
matrix[2][0] = 1;

Adjacency List:

List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < 3; i++) {
    adjList.add(new ArrayList<>());
}

// Edge A-B
adjList.get(0).add(1);
adjList.get(1).add(0);

// Edge A-C
adjList.get(0).add(2);
adjList.get(2).add(0);

Summary Table

Conclusion

Choosing the right graph representation can significantly impact your program’s efficiency. The Adjacency Matrix is best when you need fast edge lookups and work with dense graphs whereas the Adjacency List is ideal for sparse graphs where memory efficiency and fast traversals are needed.