Adjacency List vs Matrix When to Choose Which in DSA Javascript - Visual Comparison

Concept Flow - Adjacency List vs Matrix When to Choose Which

Start: Need to represent graph

↓

Check graph size and density

↓

Use List

↓

Less space

↓

Efficient for

↓

iterating edges

↓

Perform graph ops accordingly

Choose adjacency list for large, sparse graphs to save space and iterate edges efficiently. Choose adjacency matrix for dense graphs or when quick edge checks are needed.

Execution Sample

DSA Javascript

const graphList = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
};

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

Shows a graph with 4 nodes represented as adjacency list and adjacency matrix.

Execution Table

Step	Operation	Graph Type	Memory Used	Edge Check Efficiency	Visual State
1	Create graph with 4 nodes	Adjacency List	O(V + E) space (6 edges total)	Edge check requires traversal	{0: [1,2], 1: [2], 2: [0,3], 3: [3]}
2	Create graph with 4 nodes	Adjacency Matrix	O(V^2) space (16 cells)	Edge check O(1) by index	[[0,1,1,0],[0,0,1,0],[1,0,0,1],[0,0,0,1]]
3	Check if edge 0->2 exists	Adjacency List	N/A	Traverse list at 0: found 2	Edge exists
4	Check if edge 0->2 exists	Adjacency Matrix	N/A	Check matrix[0][2]: 1	Edge exists
5	Add edge 3->1	Adjacency List	Add 1 to list at 3	N/A	{0: [1,2], 1: [2], 2: [0,3], 3: [3,1]}
6	Add edge 3->1	Adjacency Matrix	Set matrix[3][1] = 1	N/A	[[0,1,1,0],[0,0,1,0],[1,0,0,1],[0,1,0,1]]
7	Iterate edges from node 2	Adjacency List	N/A	Direct iteration over [0,3]	Edges: 2->0, 2->3
8	Iterate edges from node 2	Adjacency Matrix	N/A	Check row 2 for 1s	Edges: 2->0, 2->3
9	Graph is large and sparse	Adjacency List	Efficient space	Edge checks slower	Preferred
10	Graph is dense or needs fast edge check	Adjacency Matrix	More space	Edge checks fast	Preferred
11	End	N/A	N/A	N/A	Decision based on graph properties

💡 Decision depends on graph size and density; adjacency list for sparse, matrix for dense or fast edge queries

Variable Tracker

Variable	Start	After Step 5	After Step 6	Final
graphList	{0:[],1:[],2:[],3:[]}	{0:[1,2],1:[2],2:[0,3],3:[3,1]}	{0:[1,2],1:[2],2:[0,3],3:[3,1]}	{0:[1,2],1:[2],2:[0,3],3:[3,1]}
graphMatrix	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,1,1,0],[0,0,1,0],[1,0,0,1],[0,0,0,1]]	[[0,1,1,0],[0,0,1,0],[1,0,0,1],[0,1,0,1]]	[[0,1,1,0],[0,0,1,0],[1,0,0,1],[0,1,0,1]]

Key Moments - 3 Insights

Why does adjacency list use less memory for sparse graphs?

Because adjacency list stores only existing edges, so memory grows with edges (E), not all possible pairs (V^2). See execution_table rows 1 and 2 comparing space.

Why is edge existence check faster in adjacency matrix?

Because adjacency matrix uses direct indexing to check if edge exists in O(1) time, unlike adjacency list which requires searching the list. See execution_table rows 3 and 4.

When should I prefer adjacency matrix despite higher memory?

When the graph is dense or you need very fast edge checks, adjacency matrix is better. See execution_table rows 9 and 10 for decision points.

Visual Quiz - 3 Questions

Look at the execution_table row 3, how does adjacency list check if edge 0->2 exists?

A By checking all nodes in the graph

B By checking matrix[0][2]

C By traversing the list at node 0

D By checking matrix[2][0]

💡 Hint

Refer to execution_table row 3 under 'Edge Check Efficiency' and 'Operation'

At which step does the adjacency matrix add edge 3->1?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look at execution_table rows 5 and 6 for adding edges in both graph types

If the graph is very large but has few edges, which representation is preferred?

A Adjacency List

B Adjacency Matrix

C Either one is fine

D Neither works well

💡 Hint

See execution_table rows 9 and 10 about graph size and density decisions

Concept Snapshot

Adjacency List stores edges as lists per node, saving space for sparse graphs.
Adjacency Matrix uses a 2D array, good for dense graphs and fast edge checks.
Use List when edges are few, Matrix when graph is dense or quick edge lookup is needed.
List edge check is O(E), Matrix edge check is O(1).
List uses O(V+E) space, Matrix uses O(V^2) space.
Choose based on graph size and density.

Full Transcript

This concept compares adjacency list and adjacency matrix for graph representation. Adjacency list stores only existing edges per node, saving memory for sparse graphs. Adjacency matrix uses a 2D array representing all possible edges, using more memory but allowing quick edge existence checks. The execution table shows creating both representations for a 4-node graph, checking edges, adding edges, and iterating edges. Key moments clarify why lists save space and matrices allow fast edge checks. The visual quiz tests understanding of these differences. Choose adjacency list for large, sparse graphs and adjacency matrix for dense graphs or when fast edge queries are needed.

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