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

Concept Flow - Adjacency List vs Matrix When to Choose Which

Start: Need to represent graph

↓

Check graph size and density

↓

Choose Adjacency List

↓

Choose Adjacency Matrix

↓

Use chosen representation for graph operations

Decide graph representation by checking size and density: adjacency list for large sparse graphs, adjacency matrix for small or dense graphs.

Execution Sample

DSA Java

int[][] matrix = new int[4][4];
// Initialize adjacency list for 4 nodes
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i < 4; i++) list.add(new ArrayList<>());

// Add edge 0->1 in matrix
matrix[0][1] = 1;

// Add edge 0->1 in list
list.get(0).add(1);

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

Execution Table

Step	Operation	Graph Size	Graph Density	Representation Chosen	Reasoning
1	Start with graph of 4 nodes	4 nodes	Unknown	None	Need to decide representation
2	Calculate density: edges = 3	4 nodes	3 edges / 12 possible = 0.25	Adjacency List	Density low (0.25), graph is sparse
3	Add edge 0->1	4 nodes	0.25	Adjacency List	Efficient to add edge in list
4	Add edge 1->2	4 nodes	0.5	Adjacency List	Still sparse, list efficient
5	Add edge 2->3	4 nodes	0.75	Adjacency List	Density increasing but still sparse
6	If graph was dense (e.g. 10 edges)	4 nodes	10/12 = 0.83	Adjacency Matrix	Matrix better for dense graphs
7	Add edge 0->1 in matrix	4 nodes	0.83	Adjacency Matrix	Constant time edge check and add
8	Add edge 1->2 in matrix	4 nodes	0.83	Adjacency Matrix	Fast access for dense graph
9	Add edge 2->3 in matrix	4 nodes	0.83	Adjacency Matrix	Matrix uses more memory but fast
10	End	4 nodes	Depends on edges	Chosen based on density	Decision complete

💡 Representation chosen based on graph size and density for efficient operations

Variable Tracker

Variable	Start	After Step 3 (Sparse)	After Step 5 (Sparse)	After Step 7 (Dense)	After Step 9 (Dense)	Final
Graph Size	4	4	4	4	4	4
Graph Density	Unknown	0.25	0.75	0.83	0.83	Depends on edges
Representation	None	Adjacency List	Adjacency List	Adjacency Matrix	Adjacency Matrix	Adjacency List or Matrix
Edges Count	0	1	3	10	10	Depends on edges

Key Moments - 3 Insights

Why choose adjacency list for sparse graphs?

Because adjacency list stores only existing edges, saving memory and making traversal faster for graphs with few edges, as shown in steps 2-5 where density is low.

Why is adjacency matrix better for dense graphs?

Adjacency matrix allows constant time edge checks and updates, which is efficient when many edges exist, as seen in steps 6-9 where density is high.

Does graph size alone decide the representation?

No, both size and density matter. A large dense graph may still use matrix, and a small sparse graph may use list. The decision depends on both factors as shown in the flow and steps.

Visual Quiz - 3 Questions

Look at the execution table, at which step is adjacency list chosen due to low density?

A Step 2

B Step 6

C Step 7

D Step 9

💡 Hint

Check the 'Representation Chosen' and 'Reasoning' columns in execution_table rows

At which step does the graph density reach 0.83, prompting adjacency matrix choice?

A Step 3

B Step 5

C Step 6

D Step 10

💡 Hint

Look at 'Graph Density' and 'Representation Chosen' columns in execution_table

If the graph had only 1 edge, which representation would be best according to the tables?

A Adjacency Matrix

B Adjacency List

C Either works equally

D None

💡 Hint

Refer to low density reasoning in steps 2-5 in execution_table and variable_tracker

Concept Snapshot

Adjacency List vs Matrix Decision:
- Use adjacency list for large, sparse graphs (few edges)
- Use adjacency matrix for small or dense graphs (many edges)
- List saves memory, matrix allows fast edge checks
- Density = edges / (nodes*(nodes-1)) guides choice
- Choose based on graph size and edge density

Full Transcript

This visual execution shows how to choose between adjacency list and adjacency matrix for graph representation. We start with a graph of 4 nodes and calculate its density by counting edges. When density is low, adjacency list is chosen because it stores only existing edges, saving memory and making traversal efficient. When density is high, adjacency matrix is better because it allows constant time edge checks and updates, though it uses more memory. The execution table tracks steps adding edges and shows how representation choice changes with density. Variable tracker follows graph size, density, representation, and edge count. Key moments clarify why density matters more than size alone. The quiz tests understanding of when and why each representation is chosen. The snapshot summarizes the decision rules for quick reference.

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