Adjacency List vs Matrix When to Choose Which in DSA Java - Build Both Approaches

Adjacency List vs Matrix: When to Choose Which

📖 Scenario: You are working on a simple social network app where users are connected as friends. You want to represent these connections using graphs. There are two common ways to represent graphs: adjacency lists and adjacency matrices. Each has its own advantages depending on the number of users and connections.

🎯 Goal: Build two graph representations for the same set of users and their friendships: one using an adjacency list and one using an adjacency matrix. Learn when to use each representation by comparing their structures.

📋 What You'll Learn

Create an adjacency list for 4 users with given friendships

Create an adjacency matrix for the same 4 users and friendships

Use a variable to store the number of users

Print both graph representations to see their structure

💡 Why This Matters

🌍 Real World

Social networks, recommendation systems, and network routing often use graph representations to model connections between entities.

💼 Career

Understanding graph representations is essential for software engineers working on network analysis, social media platforms, and algorithms involving relationships.

1

Create the adjacency list for the graph

Create a variable called adjList as a List<List<Integer>> and initialize it for 4 users (0 to 3). Add these friendships: user 0 connected to 1 and 2, user 1 connected to 2, user 2 connected to 0 and 3, user 3 connected to 3.

DSA Java

// Create adjacency list for 4 users
// Your code here

Hint

Use a loop to create 4 empty lists inside adjList. Then add the connections using adjList.get(user).add(friend).

2

Create a variable for the number of users

Create an integer variable called numUsers and set it to 4 to represent the total number of users.

DSA Java

import java.util.ArrayList;
import java.util.List;

public class GraphRepresentation {
    public static void main(String[] args) {
        List> adjList = new ArrayList();
        for (int i = 0; i ());
        }
        adjList.get(0).add(1);
        adjList.get(0).add(2);
        adjList.get(1).add(2);
        adjList.get(2).add(0);
        adjList.get(2).add(3);
        adjList.get(3).add(3);
        // Create numUsers variable below
        // Your code here
    }
}

Hint

Just create an integer variable numUsers and assign it the value 4.

3

Create the adjacency matrix for the graph

Using the variable numUsers, create a 2D integer array called adjMatrix of size numUsers x numUsers. Fill it with 0s initially. Then add the same friendships by setting adjMatrix[from][to] = 1 for these edges: 0 to 1, 0 to 2, 1 to 2, 2 to 0, 2 to 3, and 3 to 3.

DSA Java

        int[][] adjMatrix = new int[numUsers][numUsers];
        adjMatrix[0][1] = 1;
        adjMatrix[0][2] = 1;
        adjMatrix[1][2] = 1;
        adjMatrix[2][0] = 1;
        adjMatrix[2][3] = 1;
        adjMatrix[3][3] = 1;
        // Print adjacency list and matrix below

Hint

Create a 2D array with new int[numUsers][numUsers]. Then assign 1 to the positions representing edges.

4

Print both graph representations

Print the adjacency list and adjacency matrix to the console. For the adjacency list, print each user and their list of connected users. For the adjacency matrix, print each row on a new line with spaces between numbers.

DSA Java

Hint

Use nested loops to print the adjacency matrix row by row. For the adjacency list, print each user followed by their friends separated by spaces.

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