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

Concept Flow - Adjacency List vs Matrix When to Choose Which

Start: Need to represent graph

↓

Check graph size and density

↓

Sparse

↓

Use Adjacency List

↓

Efficient memory

↓

Good for large graphs

↓

End

Decide graph representation by size and density: sparse graphs use adjacency lists for memory efficiency; dense graphs use adjacency matrices for fast edge checks.

Execution Sample

DSA C#

bool[,] matrix = new bool[4,4];
List<int>[] list = new List<int>[4];
for(int i = 0; i < 4; i++) {
    list[i] = new List<int>();
}
// Add edge 0->1
matrix[0,1] = true;
list[0].Add(1);

Shows adding an edge from node 0 to 1 in both adjacency matrix and adjacency list.

Execution Table

Step	Operation	Graph Type	Memory Used	Edge Check Time	Visual State
1	Initialize graph with 4 nodes	Adjacency Matrix	16 bools (4x4)	O(1)	[0,0,0,0] [0,0,0,0] [0,0,0,0] [0,0,0,0]
2	Add edge 0->1	Adjacency Matrix	16 bools (4x4)	O(1)	[0,1,0,0] [0,0,0,0] [0,0,0,0] [0,0,0,0]
3	Initialize graph with 4 nodes	Adjacency List	4 lists (empty)	O(k) where k is neighbors	[[], [], [], []]
4	Add edge 0->1	Adjacency List	4 lists	O(k)	[[1], [], [], []]
5	Check edge 0->1	Adjacency Matrix	16 bools	O(1)	matrix[0,1] == true
6	Check edge 0->1	Adjacency List	4 lists	O(k)	1 in list[0] == true
7	Graph is dense (many edges)	Decision	-	-	Choose adjacency matrix for speed
8	Graph is sparse (few edges)	Decision	-	-	Choose adjacency list for memory efficiency
9	End	-	-	-	-

💡 Decision based on graph density and size; adjacency list for sparse, adjacency matrix for dense graphs.

Variable Tracker

Variable	Start	After Step 2	After Step 4	Final
matrix	[all false]	[[false,true,false,false],[false,false,false,false],[false,false,false,false],[false,false,false,false]]	-	[[false,true,false,false],[false,false,false,false],[false,false,false,false],[false,false,false,false]]
list	[[],[],[],[]]	-	[[1],[],[],[]]	[[1],[],[],[]]

Key Moments - 3 Insights

Why does adjacency matrix use more memory for large graphs?

Because it stores a fixed-size 2D array for all possible edges (n x n), even if many edges don't exist, as shown in execution_table rows 1 and 3.

Why is edge check faster in adjacency matrix than list?

Matrix allows direct access with O(1) time (row and column index), while list requires searching neighbors, which can take O(k) time, as seen in execution_table rows 5 and 6.

When should you choose adjacency list over matrix?

When the graph is sparse (few edges), adjacency list saves memory by storing only existing edges, shown in execution_table row 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the visual state of the adjacency matrix?

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

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

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

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

💡 Hint

Check execution_table row 2 under Visual State column.

At which step does the adjacency list first contain the edge 0->1?

A Step 5

B Step 2

C Step 4

D Step 6

💡 Hint

Look at execution_table row 4 showing adjacency list after adding edge.

If the graph is very dense, which representation is better according to the execution_table?

A Adjacency List

B Adjacency Matrix

C Either one works the same

D Use no representation

💡 Hint

See execution_table rows 7 and 8 for decision based on graph density.

Concept Snapshot

Adjacency List vs Matrix:
- Use adjacency list for sparse graphs (few edges) to save memory.
- Use adjacency matrix for dense graphs (many edges) for fast edge checks.
- Matrix uses O(n²) memory; list uses O(n + e) memory.
- Edge check in matrix is O(1), in list is O(k) neighbors.
- Choose based on graph size and density for best performance.

Full Transcript

This visual guide compares adjacency list and adjacency matrix graph representations. It shows how each stores edges and their memory use. The adjacency matrix uses a fixed 2D array, making edge checks very fast but using more memory, especially for large graphs. The adjacency list stores only existing edges in lists, saving memory for sparse graphs but making edge checks slower. The decision flow depends on graph size and density: sparse graphs favor adjacency lists, dense graphs favor adjacency matrices. Examples show adding an edge and checking edges in both structures. Key moments clarify why memory and speed differ. Quizzes test understanding of visual states and choices.

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