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

Mental Model

Graphs can be stored in two main ways: adjacency lists store neighbors for each node, adjacency matrices store connections in a grid.

Analogy: Think of a city map: adjacency list is like a list of friends each person has, adjacency matrix is like a big table showing if two people know each other.

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

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

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0-1, 0-2, 1-3

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

Step 1: Create adjacency list for each node

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

Why: Lists store only neighbors, saving space for sparse graphs

Step 2: Create adjacency matrix grid

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

Why: Matrix stores all possible edges, easy to check if edge exists

Step 3: Check if edge exists between 0 and 3 using list

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

Why: Must scan neighbors of 0 to find 3, slower for large lists

Step 4: Check if edge exists between 0 and 3 using matrix

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

Why: Direct lookup at matrix[0][3] is fast and simple

Result:

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

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adjList;
    vector<vector<int>> adjMatrix;

    Graph(int vertices) {
        V = vertices;
        adjList.resize(V);
        adjMatrix.resize(V, vector<int>(V, 0));
    }

    void addEdge(int u, int v) {
        adjList[u].push_back(v); // add v to u's list
        adjList[v].push_back(u); // add u to v's list (undirected)
        adjMatrix[u][v] = 1;     // mark edge in matrix
        adjMatrix[v][u] = 1;     // symmetric for undirected
    }

    void printAdjList() {
        for (int i = 0; i < V; i++) {
            cout << i << ": ";
            for (int neighbor : adjList[i]) {
                cout << neighbor << " -> ";
            }
            cout << "null" << endl;
        }
    }

    void printAdjMatrix() {
        cout << "   ";
        for (int i = 0; i < V; i++) cout << i << " ";
        cout << endl;
        for (int i = 0; i < V; i++) {
            cout << i << " [";
            for (int j = 0; j < V; j++) {
                cout << adjMatrix[i][j];
                if (j != V - 1) cout << " ";
            }
            cout << "]" << endl;
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);

    cout << "Adjacency List:" << endl;
    g.printAdjList();
    cout << endl;
    cout << "Adjacency Matrix:" << endl;
    g.printAdjMatrix();

    return 0;
}

adjList[u].push_back(v); // add v to u's list adjList[v].push_back(u); // add u to v's list (undirected)

Add neighbors to adjacency list for both nodes

adjMatrix[u][v] = 1; // mark edge in matrix adjMatrix[v][u] = 1; // symmetric for undirected

Mark edges in adjacency matrix for both directions

for (int neighbor : adjList[i]) { cout << neighbor << " -> "; }

Print all neighbors in adjacency list for node i

for (int j = 0; j < V; j++) { cout << adjMatrix[i][j]; if (j != V - 1) cout << " "; }

Print each row of adjacency matrix

Output

Adjacency List:

0: 1 -> 2 -> null

1: 0 -> 3 -> null

2: 0 -> null

3: 1 -> null



Adjacency Matrix:

   0 1 2 3

0 [0 1 1 0]

1 [1 0 0 1]

2 [1 0 0 0]

3 [0 1 0 0]

Complexity Analysis

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

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

vs Alternative: Adjacency list is better for sparse graphs with fewer edges, adjacency matrix is better for dense graphs or quick edge lookups

Edge Cases

Empty graph (no edges)

Adjacency list stores empty lists; adjacency matrix is all zeros

DSA C++

adjList.resize(V);

Graph with one node and no edges

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

DSA C++

adjMatrix.resize(V, vector<int>(V, 0));

Graph with self-loop edge (node connected to itself)

Adjacency list includes node itself in its list; adjacency matrix has 1 on diagonal

DSA C++

adjList[u].push_back(v);

When to Use This Pattern

When a problem involves graph representation and you need to choose storage, think about graph density and operations needed to pick adjacency list or matrix.

Common Mistakes

Mistake: Using adjacency matrix for very large sparse graphs causing memory waste
Fix: Use adjacency list to save space by storing only existing edges

Mistake: Assuming adjacency list lookup for edge existence is always fast
Fix: Remember adjacency list requires scanning neighbors, so use matrix for fast edge checks

Summary

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

Use adjacency list for sparse graphs and adjacency matrix for dense graphs or fast edge queries.

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

Practice

1. Which data structure is generally better for representing a graph with very few edges compared to the number of vertices?

easy

A. Adjacency List

B. Adjacency Matrix

C. Edge List

D. Incidence Matrix

Solution

1. Step 1: Understand graph density

   A graph with very few edges compared to vertices 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 graphs use adjacency lists for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing edge list with adjacency matrix
• Assuming adjacency matrix is always better

2. Which of the following is the correct way to declare an adjacency matrix for a graph with 5 vertices in C++?

easy

A. int graph[5][5];

B. vector graph(5, vector<int>(5));

C. vector<int> graph(5);

D. int graph[5];

Solution

1. Step 1: Understand adjacency matrix structure

   An adjacency matrix is a 2D structure with size V x V for V vertices.

2. Step 2: Choose correct C++ declaration

   Using vector of vectors initializes a 5x5 matrix properly.

3. Final Answer:

   vector graph(5, vector<int>(5)); -> Option B

4. Quick Check:

   2D vector for adjacency matrix = vector graph(5, vector<int>(5)); [OK]

Hint: Adjacency matrix needs 2D structure, use vector [OK]

Common Mistakes:

• Using 1D array for adjacency matrix
• Not initializing inner vectors
• Confusing adjacency list syntax with matrix

3. Consider the following C++ code snippet for a graph with 3 vertices using adjacency list:

vector adj(3);
adj[0].push_back(1);
adj[1].push_back(2);
adj[2].push_back(0);
for (int i = 0; i < 3; i++) {
    cout << i << ": ";
    for (int v : adj[i]) cout << v << " ";
    cout << endl;
}

What is the output of this code?

medium

A. 0: 1 2
1: 0
2:

B. 0: 2
1: 0
2: 1

C. 0: 1
1: 2
2: 0

D. 0:
1: 2
2: 0 1

Solution

1. Step 1: Trace adjacency list insertions

   adj[0] has 1, adj[1] has 2, adj[2] has 0.

2. Step 2: Print adjacency list contents

   Loop prints each vertex and its adjacency: 0:1, 1:2, 2:0.

3. Final Answer:

   0: 1 1: 2 2: 0 -> Option C

4. Quick Check:

   Adjacency list print matches 0: 1 1: 2 2: 0 [OK]

Hint: Follow push_back calls to trace adjacency list output [OK]

Common Mistakes:

• Mixing up indices and values
• Assuming adjacency matrix output
• Forgetting to print spaces or newlines correctly

4. The following code attempts to create an adjacency matrix for a graph with 4 vertices but has a bug:

int graph[4][4];
for (int i = 0; i <= 4; i++) {
    for (int j = 0; j <= 4; j++) {
        graph[i][j] = 0;
    }
}

What is the main issue in this code?

medium

A. The inner loop should start from 1 instead of 0

B. The matrix is not initialized to zero

C. The graph size should be 5 instead of 4

D. The loops use <= causing out-of-bounds access

Solution

1. Step 1: Analyze loop bounds

   Loops run from 0 to 4 inclusive, which means 5 iterations each.

2. Step 2: Check array size and access

   Array size is 4x4, valid indices are 0 to 3. Index 4 causes out-of-bounds error.

3. Final Answer:

   The loops use <= causing out-of-bounds access -> Option D

4. Quick Check:

   Loop bounds exceed array size causing error [OK]

Hint: Use < instead of <= for array indices [OK]

Common Mistakes:

• Assuming array size is 5
• Thinking initialization is missing
• Changing loop start instead of end condition

5. You have a graph with 1000 vertices and about 10,000 edges. You need to perform frequent edge existence checks (i.e., is there an edge between vertex u and v?). Which representation is best and why? Choose the best option.

hard

A. Adjacency Matrix, because it allows O(1) edge existence checks despite higher space

B. Adjacency List, because it uses less space and edge checks are O(1)

C. Edge List, because it is simplest and fastest for edge checks

D. Adjacency Matrix, because it uses less space for sparse graphs

Solution

1. Step 1: Understand graph size and density

   1000 vertices and 10,000 edges is a sparse graph but with many edges.

2. Step 2: Compare edge existence check times

   Adjacency matrix allows O(1) edge check by direct index access; adjacency list requires searching neighbors.

3. Step 3: Consider space vs speed tradeoff

   Matrix uses more space but is faster for edge queries, which is needed here.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge existence checks despite higher space -> Option A

5. Quick Check:

   Fast edge check needs adjacency matrix [OK]

Hint: For fast edge checks, adjacency matrix is best despite space [OK]

Common Mistakes:

• Assuming adjacency list gives O(1) edge checks
• Choosing edge list for fast queries
• Ignoring space vs time tradeoff