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 use a grid to mark connections.

Analogy: Think of a city map: adjacency list is like a list of friends each person calls, 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 entries for each node

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

Why: Lists show only connected nodes, saving space for sparse graphs

Step 2: Create adjacency matrix grid marking edges

   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 shows all possible connections, easy to check if edge exists

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

List: 0's neighbors are 1 and 2, no 3
Matrix: cell[0][3] = 0 means no edge

Why: Matrix allows O(1) edge check, list requires scanning neighbors

Step 4: Add edge 2-3 to both structures

List:
2: 0 -> 3 -> null
3: 1 -> 2 -> null
Matrix:
   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 1]
3 [0 1 1 0]

Why: Shows how both structures update differently

Result:

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

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    public int Vertices;
    public List<int>[] AdjList;
    public int[,] AdjMatrix;

    public Graph(int v) {
        Vertices = v;
        AdjList = new List<int>[v];
        for (int i = 0; i < v; i++) {
            AdjList[i] = new List<int>();
        }
        AdjMatrix = new int[v, v];
    }

    public void AddEdgeList(int src, int dest) {
        AdjList[src].Add(dest);
        AdjList[dest].Add(src);
    }

    public void AddEdgeMatrix(int src, int dest) {
        AdjMatrix[src, dest] = 1;
        AdjMatrix[dest, src] = 1;
    }

    public void PrintAdjList() {
        for (int i = 0; i < Vertices; i++) {
            Console.Write(i + ": ");
            foreach (var node in AdjList[i]) {
                Console.Write(node + " -> ");
            }
            Console.WriteLine("null");
        }
    }

    public void PrintAdjMatrix() {
        Console.Write("   ");
        for (int i = 0; i < Vertices; i++) {
            Console.Write(i + " ");
        }
        Console.WriteLine();
        for (int i = 0; i < Vertices; i++) {
            Console.Write(i + " [");
            for (int j = 0; j < Vertices; j++) {
                Console.Write(AdjMatrix[i, j] + " ");
            }
            Console.WriteLine("]");
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(4);
        g.AddEdgeList(0, 1);
        g.AddEdgeList(0, 2);
        g.AddEdgeList(1, 3);
        g.AddEdgeMatrix(0, 1);
        g.AddEdgeMatrix(0, 2);
        g.AddEdgeMatrix(1, 3);

        Console.WriteLine("Adjacency List:");
        g.PrintAdjList();
        Console.WriteLine();

        Console.WriteLine("Adjacency Matrix:");
        g.PrintAdjMatrix();

        // Add edge 2-3
        g.AddEdgeList(2, 3);
        g.AddEdgeMatrix(2, 3);

        Console.WriteLine();
        Console.WriteLine("After adding edge 2-3:");
        Console.WriteLine("Adjacency List:");
        g.PrintAdjList();
        Console.WriteLine();
        Console.WriteLine("Adjacency Matrix:");
        g.PrintAdjMatrix();
    }
}

AdjList[src].Add(dest); AdjList[dest].Add(src);

Add edge to adjacency list for both nodes to keep undirected graph

AdjMatrix[src, dest] = 1; AdjMatrix[dest, src] = 1;

Mark edges in adjacency matrix for both directions

foreach (var node in AdjList[i]) { Console.Write(node + " -> "); }

Print neighbors in adjacency list format

for (int j = 0; j < Vertices; j++) { Console.Write(AdjMatrix[i, j] + " "); }

Print 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 ]



After adding edge 2-3:

Adjacency List:

0: 1 -> 2 -> null

1: 0 -> 3 -> null

2: 0 -> 3 -> null

3: 1 -> 2 -> null



Adjacency Matrix:

   0 1 2 3 

0 [0 1 1 0 ]

1 [1 0 0 1 ]

2 [1 0 0 1 ]

3 [0 1 1 0 ]

Complexity Analysis

Time: O(V + E) to build adjacency list because we add neighbors only for edges; O(V^2) to build adjacency matrix because we fill a V by V 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 edges

vs Alternative: Adjacency list is better for sparse graphs with fewer edges; adjacency matrix is better for dense graphs or when quick edge lookup is needed

Edge Cases

Empty graph with no edges

Adjacency list has empty lists; adjacency matrix is all zeros

DSA C#

for (int i = 0; i < v; i++) { AdjList[i] = new List<int>(); }

Graph with one node and no edges

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

DSA C#

for (int i = 0; i < v; i++) { AdjList[i] = new List<int>(); }

Adding duplicate edges

Adjacency list adds duplicates; adjacency matrix stays 1 for edge

DSA C#

AdjMatrix[src, dest] = 1;

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 high memory use
Fix: Use adjacency list to save space by storing only existing edges

Mistake: Assuming adjacency list allows O(1) edge existence check
Fix: Remember adjacency list requires scanning neighbors, so edge check is O(k) where k is neighbors count

Summary

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

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

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

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