Adjacency List vs Matrix When to Choose Which in DSA Typescript - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When is an adjacency list better than an adjacency matrix?

Choose the best scenario where using an adjacency list is more efficient than an adjacency matrix.

A When the graph is dense with many edges close to the maximum possible.

B When you need to quickly check if an edge exists between any two nodes.

C When the graph is sparse with relatively few edges compared to the number of nodes.

D When the graph has a fixed small number of nodes and many edges.

💡 Hint

Think about memory usage and how many edges are stored.

An adjacency list stores only existing edges, so it uses less memory for sparse graphs. An adjacency matrix always uses space for all possible edges, which is inefficient for sparse graphs.

❓ Predict Output

intermediate

Output of adjacency matrix edge check

What is the output of the following TypeScript code that uses an adjacency matrix to check for an edge?

DSA Typescript

const graph = [
  [0, 1, 0],
  [1, 0, 1],
  [0, 1, 0]
];

console.log(graph[0][2]);

A 1

B TypeError

C undefined

D 0

💡 Hint

Look at the value stored at row 0, column 2.

The adjacency matrix uses 0 to represent no edge and 1 to represent an edge. graph[0][2] is 0, meaning no edge between node 0 and node 2.

❓ Predict Output

advanced

Output of adjacency list traversal

What will be printed by this TypeScript code that uses an adjacency list to print neighbors of node 1?

DSA Typescript

const graph: number[][] = [
  [1],       // neighbors of node 0
  [0, 2],    // neighbors of node 1
  [1]        // neighbors of node 2
];

for (const neighbor of graph[1]) {
  console.log(neighbor);
}

A 0\n2

B 1\n2

C 1

D 0

💡 Hint

Look at the neighbors stored for node 1.

Node 1 has neighbors 0 and 2, so the loop prints 0 and then 2 on separate lines.

🧠 Conceptual

advanced

Why is adjacency matrix better for dense graphs?

Select the main reason adjacency matrix is preferred over adjacency list for dense graphs.

A Because adjacency matrix is easier to implement for sparse graphs.

B Because adjacency matrix allows faster edge existence checks between any two nodes.

C Because adjacency matrix uses less memory for dense graphs.

D Because adjacency matrix stores neighbors as lists.

💡 Hint

Think about how quickly you can check if an edge exists.

Adjacency matrix allows O(1) time to check if an edge exists between any two nodes, which is useful in dense graphs where many edges exist.

🚀 Application

expert

Choosing data structure for a social network graph

You are designing a social network with millions of users but each user has only a few friends on average. Which data structure is best to represent the friendship connections and why?

A Use an adjacency list because it saves memory by storing only existing friendships.

B Use a 2D array with all zeros because most users have no friends.

C Use an adjacency matrix because it allows quick checks if two users are friends.

D Use a linked list for each user storing all users in the network.

💡 Hint

Consider memory usage and average number of connections per user.

Since each user has few friends compared to total users, adjacency list saves memory by storing only actual friendships instead of all possible pairs.