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

Recall & Review

beginner

What is an adjacency list in graph representation?

An adjacency list stores each node and a list of its neighbors. It uses less space for sparse graphs and is efficient for iterating over neighbors.

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array where each cell shows if there is an edge between two nodes. It uses more space but allows quick edge checks.

intermediate

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

Use adjacency list when the graph is sparse (few edges) because it saves space and is faster to traverse neighbors.

intermediate

When is an adjacency matrix preferred over an adjacency list?

Use adjacency matrix when the graph is dense (many edges) or when you need to quickly check if an edge exists between two nodes.

intermediate

What is the space complexity difference between adjacency list and adjacency matrix?

Adjacency list uses O(V + E) space, where V is vertices and E is edges. Adjacency matrix uses O(V²) space regardless of edges.

Which graph representation is more space efficient for a graph with 1000 nodes and 10 edges?

A None of the above

B Adjacency Matrix

C Both use the same space

D Adjacency List

Adjacency list is more space efficient for sparse graphs like this one with few edges.

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

A Both

B Adjacency List

C Adjacency Matrix

D Neither

Adjacency matrix allows constant time edge existence check by direct indexing.

For a dense graph, which representation is generally better?

A Adjacency List

B Adjacency Matrix

C Depends on the programming language

D Depends on the number of nodes only

Adjacency matrix is better for dense graphs because it stores all edges explicitly.

What is the space complexity of an adjacency matrix for a graph with V vertices?

A O(V²)

B O(V + E)

C O(E)

D O(log V)

Adjacency matrix always uses O(V²) space regardless of edges.

Which representation is faster to iterate over all neighbors of a node?

A Adjacency List

B Adjacency Matrix

C Both are equally fast

D Depends on the number of nodes

Adjacency list stores neighbors directly, making iteration faster especially in sparse graphs.

Explain when you would choose an adjacency list over an adjacency matrix for graph representation.

Think about graphs with few edges compared to nodes.

Describe the advantages and disadvantages of using an adjacency matrix.

Consider time and space trade-offs.