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

Challenge - 5 Problems

🧠 Conceptual

intermediate

When is an adjacency list preferred over an adjacency matrix?

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

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

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

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

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

💡 Hint

Think about memory usage and how many edges exist compared to vertices.

An adjacency list uses less memory for sparse graphs because it stores only existing edges. An adjacency matrix always uses memory proportional to the square of vertices, which is inefficient for sparse graphs.

❓ Predict Output

intermediate

Output of adjacency matrix for a small graph

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

DSA C#

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++) {
        Console.Write(matrix[i,j] + " ");
    }
    Console.WriteLine();
}

A

0 1 1 
1 0 1 
1 1 0 

B

1 0 0 
0 1 0 
0 0 1 

C

0 0 1 
1 0 0 
0 1 0 

D

0 1 0 
0 0 1 
1 0 0 

💡 Hint

Check which indices are set to 1 in the matrix.

The matrix rows represent source vertices and columns represent destination vertices. Only the specified edges are set to 1.

❓ Predict Output

advanced

Adjacency list representation output

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

DSA C#

List<int>[] adjList = new List<int>[3];
for (int i = 0; i < 3; i++) adjList[i] = new List<int>();
adjList[0].Add(1);
adjList[0].Add(2);
adjList[1].Add(2);
adjList[2].Add(0);
for (int i = 0; i < 3; i++) {
    Console.Write(i + ": ");
    foreach (int v in adjList[i]) {
        Console.Write(v + " -> ");
    }
    Console.WriteLine("null");
}

A

0: 2 -> 1 -> null
1: 2 -> null
2: 0 -> null

B

0: 1 -> 2 -> null
1: 2 -> null
2: 0 -> null

C

0: 1 -> null
1: 2 -> null
2: 0 -> null

D

0: 1 -> 2 -> null
1: null
2: 0 -> null

💡 Hint

Look at the order edges were added to each list.

The adjacency list stores neighbors in the order they were added. Vertex 0 has edges to 1 and 2, vertex 1 to 2, and vertex 2 to 0.

🧠 Conceptual

advanced

Memory usage comparison for large sparse graph

For a graph with 10,000 vertices and 20,000 edges, which data structure uses less memory?

A Both use about the same memory for this graph size

B Adjacency matrix because it uses fixed size memory regardless of edges

C Adjacency list because it stores only existing edges, saving memory

D Neither, a different data structure is needed for large graphs

💡 Hint

Consider how many edges exist compared to the total possible edges.

An adjacency matrix for 10,000 vertices requires 100 million entries, which is large. An adjacency list stores only 20,000 edges, much less memory.

🚀 Application

expert

Choosing data structure for fast edge existence queries

You need to frequently check if an edge exists between two vertices in a graph with 500 vertices and 100,000 edges. Which data structure is best?

A Adjacency matrix because it allows constant time edge existence checks

B Adjacency list because it uses less memory and is faster for edge checks

C Adjacency list with sorting for binary search edge checks

D Edge list storing all edges and searching linearly

💡 Hint

Think about the time complexity of checking if an edge exists.

An adjacency matrix allows O(1) time to check if an edge exists by direct indexing. Adjacency lists require searching neighbors, which can be slower.

Practice

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

easy

A. Adjacency List

B. Adjacency Matrix

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 data structure for sparse graph

   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 sparse with dense graphs
• Thinking arrays or stacks represent graphs directly

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

easy

A. int[][] adjacencyMatrix = new int[4][]; for(int i=0; i<4; i++) adjacencyMatrix[i] = new int[4];

B. int adjacencyMatrix = new int[4];

C. List<int>[] adjacencyMatrix = new List<int>[4];

D. int[,] adjacencyMatrix = new int[4,4];

Solution

1. Step 1: Identify adjacency matrix type

   An adjacency matrix is a 2D array representing edges between nodes.

2. Step 2: Check C# syntax for 2D arrays

   In C#, 2D arrays use syntax like int[,] array = new int[rows, columns];

3. Final Answer:

   int[,] adjacencyMatrix = new int[4,4]; -> Option D

4. Quick Check:

   2D array syntax = int[,] [OK]

Hint: Adjacency matrix uses 2D array syntax int[,] [OK]

Common Mistakes:

• Using jagged arrays instead of 2D arrays for matrix
• Declaring adjacencyMatrix as a single int
• Using List<int>[] which is adjacency list, not matrix

3. Given the following adjacency list representation of a graph in C#:

var graph = new List<int>[] {
  new List<int>{1, 2},
  new List<int>{2},
  new List<int>{0}
};
Console.WriteLine(graph[0][1]);

What will be the output?

medium

A. 0

B. 1

C. 2

D. IndexOutOfRangeException

Solution

1. Step 1: Understand the adjacency list structure

   graph[0] = List<int>{1, 2}, so graph[0][1] accesses the second element which is 2.

2. Step 2: Identify the output of Console.WriteLine(graph[0][1])

   It prints the value 2 from the list at index 1 of graph[0].

3. Final Answer:

   2 -> Option C

4. Quick Check:

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

Hint: Indexing starts at 0; graph[0][1] is second element in first list [OK]

Common Mistakes:

• Confusing indices and printing 1 instead of 2
• Expecting an error due to nested lists
• Thinking graph[0][1] accesses graph[1]

4. Consider this adjacency matrix code snippet in C#:

int[,] matrix = new int[3,3];
matrix[0,1] = 1;
matrix[1,2] = 1;
matrix[2,0] = 1;
Console.WriteLine(matrix[1,0]);

What is the output and why?

medium

A. 1 because matrix is symmetric

B. 0 because matrix[1,0] was never set

C. Runtime error due to invalid index

D. 1 because of default initialization

Solution

1. Step 1: Analyze matrix assignments

   Only matrix[0,1], matrix[1,2], and matrix[2,0] are set to 1; matrix[1,0] remains 0.

2. Step 2: Understand default values in int[] arrays

   Unassigned int elements default to 0 in C#.

3. Final Answer:

   0 because matrix[1,0] was never set -> Option B

4. Quick Check:

   Unset matrix elements = 0 [OK]

Hint: Unset matrix cells default to 0, not symmetric [OK]

Common Mistakes:

• Assuming adjacency matrix is symmetric by default
• Expecting runtime error for valid indices
• Confusing default values with assigned values

5. You need to represent a social network graph with 10,000 users where each user has on average 10 friends. Which representation is best and why? Choose between adjacency list and adjacency matrix.

hard

A. Adjacency list, because it uses less memory for sparse graphs

B. Adjacency matrix, because it allows quick edge checks

C. Adjacency matrix, because it is simpler to implement

D. Adjacency list, because it stores all possible edges

Solution

1. Step 1: Calculate graph density

   10,000 users with 10 friends each means about 100,000 edges, which is sparse compared to 100 million possible edges.

2. Step 2: Choose data structure for sparse graph

   Adjacency list stores only existing edges, saving huge memory compared to adjacency matrix.

3. Final Answer:

   Adjacency list, because it uses less memory for sparse graphs -> Option A

4. Quick Check:

   Sparse large graph = adjacency list [OK]

Hint: Large sparse graph? Use adjacency list for memory efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix despite huge memory waste
• Thinking adjacency matrix is always simpler
• Misunderstanding adjacency list stores only existing edges