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

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to use adjacency list over adjacency matrix?

Which situation is best suited for using an adjacency list instead of an adjacency matrix?

A When the graph has a fixed small number of vertices and many edges

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

C When you need to quickly check if an edge exists between two vertices

D When the graph is sparse with relatively few edges compared to vertices

💡 Hint

Think about memory usage and efficiency for graphs with few edges.

An adjacency list is more memory efficient for sparse graphs because it stores only existing edges. Adjacency matrix uses space for all possible edges regardless of presence.

❓ Predict Output

intermediate

Output of adjacency matrix representation

What is the printed adjacency matrix after adding edges (0->1), (1->2), and (2->0) in a graph with 3 vertices?

DSA Javascript

const vertices = 3;
const matrix = Array(vertices).fill(null).map(() => Array(vertices).fill(0));
matrix[0][1] = 1;
matrix[1][2] = 1;
matrix[2][0] = 1;
console.log(matrix);

A [[0,1,0],[0,0,1],[1,0,0]]

B [[0,0,1],[1,0,0],[0,1,0]]

C [[1,0,0],[0,1,0],[0,0,1]]

D [[0,1,1],[1,0,1],[1,1,0]]

💡 Hint

Check which indices are set to 1 for edges.

The matrix rows represent source vertices and columns represent destination vertices. Setting matrix[0][1] = 1 means edge from 0 to 1.

🔧 Debug

advanced

Identify error in adjacency list edge addition

What error will this code cause when adding an edge to an adjacency list for a graph with 3 vertices?

DSA Javascript

const vertices = 3;
const adjList = Array(vertices).fill([]);
adjList[0].push(1);
console.log(adjList);

A All adjacency lists share the same array, so pushing to one affects all

B SyntaxError due to missing semicolon

C TypeError because adjList[0] is undefined

D No error, adjacency list updated correctly

💡 Hint

Consider how Array.fill works with objects or arrays.

Using fill([]) assigns the same array reference to all positions, so pushing to one affects all lists.

🚀 Application

advanced

Choosing representation for a social network graph

You are designing a social network with millions of users but each user connects to only a few others. Which graph representation is best and why?

A Adjacency list, because it stores all possible edges regardless of presence

B Adjacency matrix, because it allows quick edge lookup between any two users

C Adjacency list, because it uses less memory and efficiently stores sparse connections

D Adjacency matrix, because it is simpler to implement for large graphs

💡 Hint

Think about memory and typical number of connections per user.

Social networks are usually sparse graphs. Adjacency lists save memory by storing only actual connections.

❓ Predict Output

expert

Resulting adjacency list after multiple edge additions

What is the printed adjacency list after these operations on a graph with 4 vertices? const adjList = Array(4).fill(null).map(() => []); adjList[0].push(1); adjList[0].push(2); adjList[1].push(2); adjList[2].push(3); console.log(adjList);

DSA Javascript

const adjList = Array(4).fill(null).map(() => []);
adjList[0].push(1);
adjList[0].push(2);
adjList[1].push(2);
adjList[2].push(3);
console.log(adjList);

A [[2,1], [2], [3], []]

B [[1,2], [2], [3], []]

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

D [[], [1,2], [2], [3]]

💡 Hint

Check the order of pushes and which vertex each list belongs to.

Each array index holds neighbors of that vertex. Vertex 0 has neighbors 1 and 2, vertex 1 has neighbor 2, vertex 2 has neighbor 3, vertex 3 has none.

Practice

1. Which data structure is generally better for representing a graph with many nodes but few edges?

easy

A. Adjacency Matrix

B. Adjacency List

C. Array

D. Stack

Solution

1. Step 1: Understand graph density

   A graph with many nodes but few edges is called a sparse graph.

2. Step 2: Choose efficient representation for sparse graphs

   Adjacency lists store only existing edges, saving space for sparse graphs.

3. Final Answer:

   Adjacency List -> Option B

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graphs use adjacency lists for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing adjacency list with adjacency matrix
• Thinking arrays or stacks represent graphs directly

2. Which of the following is the correct syntax to initialize an empty adjacency list for a graph with 3 nodes in JavaScript?

easy

A. const graph = [[], [], []];

B. const graph = [[0,0,0],[0,0,0],[0,0,0]];

C. const graph = new Array(3).fill([]);

D. const graph = {};

Solution

1. Step 1: Understand adjacency list structure

   An adjacency list is an array where each element is an array of neighbors.

2. Step 2: Check each option

   const graph = [[], [], []]; creates separate empty arrays for each node. const graph = new Array(3).fill([]); fills with the same array reference, causing bugs.

3. Final Answer:

   const graph = [[], [], []]; -> Option A

4. Quick Check:

   Separate empty arrays = const graph = [[], [], []]; [OK]

Hint: Use separate empty arrays, not fill with one array [OK]

Common Mistakes:

• Using fill([]) which shares the same array reference
• Using adjacency matrix syntax for adjacency list
• Using an object instead of array for adjacency list

3. What will be the output of the following JavaScript code snippet?

const graph = [
  [1, 2],
  [0],
  [0]
];
console.log(graph[0]);

medium

A. [0, 1, 2]

B. [0]

C. [1, 2]

D. undefined

Solution

1. Step 1: Understand the adjacency list structure

   graph[0] contains the neighbors of node 0, which are nodes 1 and 2.

2. Step 2: Check the console.log output

   Logging graph[0] prints the array [1, 2].

3. Final Answer:

   [1, 2] -> Option C

4. Quick Check:

   graph[0] = [1, 2] [OK]

Hint: Access adjacency list by index to get neighbors [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix output
• Expecting all nodes instead of neighbors
• Mistaking graph[0] as undefined

4. Identify the error in this adjacency matrix initialization code for a graph with 3 nodes:

const graph = new Array(3).fill(new Array(3).fill(0));
graph[0][1] = 1;
console.log(graph);

medium

A. The inner arrays are shared references causing all rows to change

B. The graph array is not initialized with zeros

C. The syntax for new Array is incorrect

D. The assignment graph[0][1] = 1 is invalid

Solution

1. Step 1: Analyze array initialization

   Using fill with new Array(3).fill(0) creates one inner array shared by all rows.

2. Step 2: Effect of modifying graph[0][1]

   Changing graph[0][1] changes the same element in all rows because they reference the same array.

3. Final Answer:

   The inner arrays are shared references causing all rows to change -> Option A

4. Quick Check:

   Shared inner arrays cause unexpected changes [OK]

Hint: Use loop or map to create separate inner arrays [OK]

Common Mistakes:

• Assuming fill creates independent arrays
• Ignoring shared reference problem
• Thinking syntax is wrong instead of logic

5. You have a graph with 1000 nodes and about 10,000 edges. Which representation is more efficient in terms of memory and why? Choose the best option.

hard

A. Adjacency Matrix, because it allows O(1) edge checks

B. Adjacency List, because it stores all possible edges

C. Adjacency Matrix, because it is simpler to implement

D. Adjacency List, because it uses memory proportional to edges

Solution

1. Step 1: Calculate graph density

   Maximum edges for 1000 nodes is 1,000,000 (1000*1000). 10,000 edges is sparse.

2. Step 2: Compare memory usage

   Adjacency matrix uses memory for all possible edges (1,000,000). Adjacency list uses memory proportional to actual edges (10,000).

3. Step 3: Choose efficient representation

   Adjacency list is more memory efficient for sparse graphs.

4. Final Answer:

   Adjacency List, because it uses memory proportional to edges -> Option D

5. Quick Check:

   Sparse graph = Adjacency List memory efficient [OK]

Hint: Sparse large graph? Use adjacency list for memory [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes memory
• Confusing simplicity with efficiency
• Thinking adjacency list stores all possible edges