Adjacency List vs Matrix When to Choose Which in DSA Java - Trade-offs & Analysis

Mental Model

Graphs can be stored in two main ways: adjacency lists save neighbors only, adjacency matrices save all connections in a grid.

Analogy: Think of a city map: adjacency list is like a list of direct roads from each city, adjacency matrix is like a big table showing if any road exists between every pair of cities.

Adjacency List:
City 0: 1 -> 3 -> null
City 1: 0 -> 2 -> null
City 2: 1 -> null
City 3: 0 -> null

Adjacency Matrix:
    0 1 2 3
0 [ 0 1 0 1 ]
1 [ 1 0 1 0 ]
2 [ 0 1 0 0 ]
3 [ 1 0 0 0 ]

Dry Run Walkthrough

Input: Graph with 4 cities (0,1,2,3) and roads: 0-1, 0-3, 1-2

Goal: Show how adjacency list and matrix represent the same graph and when each is better

Step 1: Create adjacency list for each city with its direct roads

City 0: 1 -> 3 -> null
City 1: 0 -> 2 -> null
City 2: 1 -> null
City 3: 0 -> null

Why: Lists only store neighbors, saving space for cities with few roads

Step 2: Create adjacency matrix grid marking 1 where roads exist

    0 1 2 3
0 [ 0 1 0 1 ]
1 [ 1 0 1 0 ]
2 [ 0 1 0 0 ]
3 [ 1 0 0 0 ]

Why: Matrix shows all possible city pairs, easy to check any connection quickly

Step 3: Compare space used: list stores only existing roads, matrix stores all pairs

List stores 6 pointers total, matrix stores 16 entries

Why: List is better for few roads, matrix wastes space but is faster for dense graphs

Result:

Adjacency List:
City 0: 1 -> 3 -> null
City 1: 0 -> 2 -> null
City 2: 1 -> null
City 3: 0 -> null

Adjacency Matrix:
    0 1 2 3
0 [ 0 1 0 1 ]
1 [ 1 0 1 0 ]
2 [ 0 1 0 0 ]
3 [ 1 0 0 0 ]

Use list for sparse graphs, matrix for dense graphs.

Annotated Code

DSA Java

import java.util.*;

public class GraphRepresentation {
    static class GraphList {
        List<List<Integer>> adjList;
        int vertices;

        GraphList(int v) {
            vertices = v;
            adjList = new ArrayList<>();
            for (int i = 0; i < v; i++) {
                adjList.add(new LinkedList<>());
            }
        }

        void addEdge(int src, int dest) {
            adjList.get(src).add(dest); // add dest to src's list
            adjList.get(dest).add(src); // add src to dest's list (undirected)
        }

        void printGraph() {
            for (int i = 0; i < vertices; i++) {
                System.out.print("City " + i + ": ");
                for (int node : adjList.get(i)) {
                    System.out.print(node + " -> ");
                }
                System.out.println("null");
            }
        }
    }

    static class GraphMatrix {
        int[][] adjMatrix;
        int vertices;

        GraphMatrix(int v) {
            vertices = v;
            adjMatrix = new int[v][v];
        }

        void addEdge(int src, int dest) {
            adjMatrix[src][dest] = 1; // mark road exists
            adjMatrix[dest][src] = 1; // undirected
        }

        void printGraph() {
            System.out.print("    ");
            for (int i = 0; i < vertices; i++) {
                System.out.print(i + " ");
            }
            System.out.println();
            for (int i = 0; i < vertices; i++) {
                System.out.print(i + " [ ");
                for (int j = 0; j < vertices; j++) {
                    System.out.print(adjMatrix[i][j] + " ");
                }
                System.out.println("]");
            }
        }
    }

    public static void main(String[] args) {
        int v = 4;
        int[][] edges = {{0,1},{0,3},{1,2}};

        System.out.println("Adjacency List:");
        GraphList graphList = new GraphList(v);
        for (int[] edge : edges) {
            graphList.addEdge(edge[0], edge[1]);
        }
        graphList.printGraph();

        System.out.println("\nAdjacency Matrix:");
        GraphMatrix graphMatrix = new GraphMatrix(v);
        for (int[] edge : edges) {
            graphMatrix.addEdge(edge[0], edge[1]);
        }
        graphMatrix.printGraph();
    }
}

adjList.get(src).add(dest); // add dest to src's list

add neighbor to source city list to record direct road

adjList.get(dest).add(src); // add src to dest's list (undirected)

add source to destination list for undirected road

adjMatrix[src][dest] = 1; // mark road exists

mark road presence in matrix for src to dest

adjMatrix[dest][src] = 1; // undirected

mark road presence in matrix for dest to src

Output

Adjacency List:

City 0: 1 -> 3 -> null

City 1: 0 -> 2 -> null

City 2: 1 -> null

City 3: 0 -> null



Adjacency Matrix:

    0 1 2 3 

0 [ 0 1 0 1 ]

1 [ 1 0 1 0 ]

2 [ 0 1 0 0 ]

3 [ 1 0 0 0 ]

Complexity Analysis

Time: O(V + E) to build adjacency list because we add each edge once to lists; O(V^2) to build adjacency matrix because we initialize full grid

Space: O(V + E) for adjacency list as it stores only existing edges; O(V^2) for adjacency matrix as it stores all possible pairs

vs Alternative: Adjacency list is space efficient for sparse graphs with few edges; adjacency matrix is simpler and faster for dense graphs where many edges exist

Edge Cases

Empty graph with no edges

Adjacency list has empty lists for each city; adjacency matrix is all zeros

DSA Java

for (int i = 0; i < v; i++) { adjList.add(new LinkedList<>()); }

Graph with one city and no roads

Adjacency list has one empty list; adjacency matrix is 1x1 zero

DSA Java

int[][] adjMatrix = new int[v][v];

Graph with all cities connected to each other (complete graph)

Adjacency list stores all neighbors for each city; adjacency matrix is full of ones except diagonal zeros

DSA Java

adjMatrix[src][dest] = 1;

When to Use This Pattern

When a problem involves graph representation and you must choose storage, think about graph density: use adjacency list for few edges to save space, adjacency matrix for many edges to speed up edge checks.

Common Mistakes

Mistake: Using adjacency matrix for very large sparse graphs causing memory waste
Fix: Switch to adjacency list to store only existing edges and save space

Mistake: Forgetting to add edges in both directions for undirected graphs
Fix: Add edge from src to dest and from dest to src explicitly

Summary

Stores graph connections either as lists of neighbors or a full grid of connections.

Use adjacency list for graphs with few edges, adjacency matrix for dense graphs.

Adjacency list saves space by storing only existing edges; adjacency matrix allows quick edge lookup.

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