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

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to use adjacency list over adjacency matrix?

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

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

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

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. An adjacency matrix uses memory proportional to the square of vertices regardless of edges.

❓ Predict Output

intermediate

Output of adjacency matrix representation

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

DSA Java

int[][] matrix = new int[3][3];
matrix[0][1] = 1;
matrix[1][2] = 1;
matrix[2][0] = 1;
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        System.out.print(matrix[i][j] + " ");
    }
    System.out.println();
}

A

0 0 1 
1 0 0 
0 1 0 

B

1 0 0 
0 1 0 
0 0 1 

C

0 1 0 
0 0 1 
1 0 0 

D

0 1 1 
1 0 1 
1 1 0 

💡 Hint

Check which indices are set to 1 for edges.

The adjacency matrix has 1 at positions where edges exist: (0,1), (1,2), and (2,0). All other positions are 0.

🔧 Debug

advanced

Why does this adjacency list code cause a NullPointerException?

Given the code below, why does it throw a NullPointerException when adding edges?

DSA Java

List<Integer>[] adjList = new ArrayList[3];
adjList[0].add(1);
adjList[1].add(2);
adjList[2].add(0);

A The add method is not valid for List<Integer> type

B The array adjList is not initialized with ArrayList objects before adding elements

C The array size is too small for the number of vertices

D The indices used for adding edges are out of bounds

💡 Hint

Think about what happens when you try to call a method on a null reference.

The array adjList is created but each element is null. You must initialize each element with new ArrayList<>() before adding.

🚀 Application

advanced

Choosing representation for a social network graph

You are designing a social network with millions of users but each user has on average 200 friends. Which graph representation is best and why?

A Adjacency list, because it uses less memory for sparse connections

B Adjacency matrix, because it allows quick edge existence checks

C Adjacency matrix, because it is simpler to implement

D Adjacency list, because it stores all possible edges explicitly

💡 Hint

Consider the number of edges compared to possible edges.

With millions of users, the graph is very sparse since each user connects to only a small fraction of all users. Adjacency list saves memory and is efficient.

❓ Predict Output

expert

Memory usage difference between adjacency list and matrix

Given a graph with 1000 vertices and 1500 edges, which statement about memory usage is true?

A Adjacency matrix uses about 1,000,000 units of memory, adjacency list uses about 1,500 units

B Adjacency matrix uses about 1,500 units of memory, adjacency list uses about 1,000,000 units

C Both adjacency matrix and list use about the same memory

D Adjacency list uses more memory because it stores pointers for each vertex

💡 Hint

Calculate memory based on vertices squared vs edges.

Adjacency matrix memory is proportional to vertices squared (1000*1000=1,000,000). Adjacency list memory is proportional to edges (1500).

Practice

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

easy

A. Adjacency List

B. Adjacency Matrix

C. Array

D. Linked List

Solution

1. Step 1: Understand graph density

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

2. Step 2: Choose efficient representation for sparse graphs

   Adjacency List stores only existing edges, saving space for sparse graphs.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graph? Use adjacency list for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing adjacency list with linked list
• Ignoring graph density when choosing representation

2. Which of the following is the correct way to declare an adjacency matrix for a graph with 4 vertices in Java?

easy

A. int[][] adjMatrix = new int[4][4];

B. int adjMatrix = new int[4][4];

C. int[] adjMatrix = new int[4];

D. int[][] adjMatrix = new int[4];

Solution

1. Step 1: Understand adjacency matrix structure

   An adjacency matrix for 4 vertices is a 4x4 2D array.

2. Step 2: Check Java syntax for 2D arrays

   Correct declaration uses int[][] with new int[4][4].

3. Final Answer:

   int[][] adjMatrix = new int[4][4]; -> Option A

4. Quick Check:

   2D array syntax = int[][] adjMatrix = new int[4][4]; [OK]

Hint: Adjacency matrix needs 2D array: int[][] arr = new int[n][n]; [OK]

Common Mistakes:

• Using single brackets for 2D array
• Missing array type brackets
• Declaring as single dimension array

3. Consider the following Java code snippet for an undirected graph with 3 vertices:

int[][] matrix = new int[3][3];
matrix[0][1] = 1;
matrix[1][0] = 1;
matrix[1][2] = 1;
matrix[2][1] = 1;
System.out.println(matrix[0][2]);

What is the output?

medium

A. 1

B. null

C. ArrayIndexOutOfBoundsException

D. 0

Solution

1. Step 1: Analyze matrix initialization and assignments

   Matrix is 3x3 initialized with zeros. Edges set between 0-1 and 1-2.

2. Step 2: Check value at matrix[0][2]

   No edge assigned between 0 and 2, so matrix[0][2] remains 0.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   matrix[0][2] = 0 (no edge) [OK]

Hint: Unassigned edges in matrix default to 0 [OK]

Common Mistakes:

• Assuming symmetric edges without assignment
• Expecting 1 for indirect connections
• Confusing output with exceptions

4. The following code attempts to add an edge in an adjacency list representation for a graph with 3 vertices:

List<Integer>[] adjList = new ArrayList[3];
adjList[0].add(1);

What is the error and how to fix it?

medium

A. No error; code runs fine

B. NullPointerException; initialize each list before adding

C. SyntaxError; use curly braces instead of brackets

D. ArrayIndexOutOfBoundsException; increase array size

Solution

1. Step 1: Identify cause of NullPointerException

   Array created but each element is null; no ArrayList objects initialized.

2. Step 2: Fix by initializing each list

   Use a loop to assign new ArrayList() to each adjList[i] before adding edges.

3. Final Answer:

   NullPointerException; initialize each list before adding -> Option B

4. Quick Check:

   NullPointerException = uninitialized lists [OK]

Hint: Initialize each list in array before adding elements [OK]

Common Mistakes:

• Forgetting to create ArrayList objects
• Assuming array creation initializes lists
• Ignoring runtime exceptions

5. You have a graph with 1000 vertices and about 10,000 edges. You need to perform frequent edge existence checks between any two vertices. Which representation is best and why?

hard

A. Adjacency Matrix, because it uses less space for sparse graphs

B. Adjacency List, because it uses less space and edge checks are O(1)

C. Adjacency Matrix, because it allows O(1) edge checks despite higher space

D. Adjacency List, because it allows O(1) edge checks for dense graphs

Solution

1. Step 1: Analyze graph density

   1000 vertices and 10,000 edges means graph is sparse (max edges ~ 499,500).

2. Step 2: Consider edge existence check speed

   Adjacency matrix allows O(1) edge existence check by direct index access.

3. Step 3: Balance space vs speed

   Though matrix uses more space, frequent edge checks favor adjacency matrix for speed.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge checks despite higher space -> Option C

5. Quick Check:

   Frequent edge checks = adjacency matrix [OK]

Hint: Frequent edge checks? Use adjacency matrix for O(1) lookup [OK]

Common Mistakes:

• Choosing adjacency list for O(1) edge checks (it's O(k))
• Ignoring space vs time tradeoff
• Confusing sparse and dense graph definitions