Adjacency List vs Matrix When to Choose Which in DSA C - Key Differences

Recall & Review

beginner

What is an adjacency list in graph representation?

An adjacency list stores each vertex's neighbors in a list or array. It shows which nodes are directly connected to each vertex.

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array where each cell (i, j) shows if there is an edge between vertex i and vertex j, usually with 1 for edge and 0 for no edge.

intermediate

When is it better to use an adjacency list over an adjacency matrix?

Use adjacency list when the graph is sparse (few edges). It saves space and is faster to iterate neighbors.

intermediate

When is an adjacency matrix preferred?

Use adjacency matrix when the graph is dense (many edges) or when you need quick edge lookup between any two vertices.

intermediate

What is the space complexity difference between adjacency list and matrix for a graph with V vertices and E edges?

Adjacency list uses O(V + E) space, while adjacency matrix uses O(V²) space regardless of edges.

Which graph representation uses less space for a graph with very few edges?

A Both use the same space

B Adjacency List

C Adjacency Matrix

D Depends on the number of vertices only

Adjacency list uses space proportional to vertices plus edges, so it is more space efficient for sparse graphs.

Which representation allows O(1) time to check if an edge exists between two vertices?

A Adjacency Matrix

B Adjacency List

C Both take O(V) time

D Neither can do it in O(1)

Adjacency matrix stores edges in a 2D array, so checking an edge is a direct index lookup.

For a graph with 1000 vertices and 10,000 edges, which representation is generally better?

A Adjacency Matrix

B Use edge list instead

C Either is fine

D Adjacency List

Since 10,000 edges is much less than 1,000² = 1,000,000 possible edges, adjacency list is more space efficient.

Which representation is easier to implement for dense graphs?

A Both are equally easy

B Adjacency List

C Adjacency Matrix

D Neither is suitable

Adjacency matrix is simpler for dense graphs because it uses a fixed-size 2D array.

What is the main disadvantage of adjacency matrix for large sparse graphs?

A High space usage

B Cannot represent directed edges

C Complex implementation

D Slow edge lookup

Adjacency matrix uses O(V²) space, which is large for sparse graphs with many vertices but few edges.

Explain when to choose adjacency list over adjacency matrix for graph representation.

Think about how many edges compared to vertices.

Describe the advantages and disadvantages of adjacency matrix.

Consider time and space trade-offs.