Adjacency List vs Matrix When to Choose Which in DSA Typescript - 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: edges 0-1, 0-2, 1-3

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

Step 1: Build adjacency list by adding neighbors for each node

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

Why: Lists store only existing edges, saving space for sparse graphs

Step 2: Build adjacency matrix by marking 1 where edges exist

   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 at 0: 1 -> 2 -> null (no 3)
Matrix[0][3] = 0

Why: List requires scanning neighbors, matrix is direct lookup

Step 4: Add edge 2-3 in 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: Both structures updated to keep graph consistent

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 Typescript

class Graph {
  adjacencyList: Map<number, number[]>;
  adjacencyMatrix: number[][];
  size: number;

  constructor(size: number) {
    this.size = size;
    this.adjacencyList = new Map();
    this.adjacencyMatrix = Array.from({ length: size }, () => Array(size).fill(0));
    for (let i = 0; i < size; i++) {
      this.adjacencyList.set(i, []);
    }
  }

  addEdgeList(u: number, v: number) {
    this.adjacencyList.get(u)!.push(v); // add v to u's list
    this.adjacencyList.get(v)!.push(u); // add u to v's list
  }

  addEdgeMatrix(u: number, v: number) {
    this.adjacencyMatrix[u][v] = 1; // mark edge u->v
    this.adjacencyMatrix[v][u] = 1; // mark edge v->u
  }

  printList() {
    for (let i = 0; i < this.size; i++) {
      const neighbors = this.adjacencyList.get(i)!.join(' -> ');
      console.log(`${i}: ${neighbors} -> null`);
    }
  }

  printMatrix() {
    console.log('   ' + [...Array(this.size).keys()].join(' '));
    for (let i = 0; i < this.size; i++) {
      console.log(i + ' [' + this.adjacencyMatrix[i].join(' ') + ']');
    }
  }
}

// Driver code
const graph = new Graph(4);
// Add edges 0-1, 0-2, 1-3
graph.addEdgeList(0, 1);
graph.addEdgeList(0, 2);
graph.addEdgeList(1, 3);

graph.addEdgeMatrix(0, 1);
graph.addEdgeMatrix(0, 2);
graph.addEdgeMatrix(1, 3);

console.log('Adjacency List:');
graph.printList();

console.log('\nAdjacency Matrix:');
graph.printMatrix();

// Check edge 0-3
console.log('\nCheck edge 0-3:');
const listHasEdge = graph.adjacencyList.get(0)!.includes(3);
const matrixHasEdge = graph.adjacencyMatrix[0][3] === 1;
console.log(`List: ${listHasEdge}`);
console.log(`Matrix: ${matrixHasEdge}`);

// Add edge 2-3
graph.addEdgeList(2, 3);
graph.addEdgeMatrix(2, 3);

console.log('\nAfter adding edge 2-3:');
console.log('Adjacency List:');
graph.printList();

console.log('\nAdjacency Matrix:');
graph.printMatrix();

this.adjacencyList.get(u)!.push(v); // add v to u's list this.adjacencyList.get(v)!.push(u); // add u to v's list

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

this.adjacencyMatrix[u][v] = 1; // mark edge u->v this.adjacencyMatrix[v][u] = 1; // mark edge v->u

Mark edges in adjacency matrix for both directions

const listHasEdge = graph.adjacencyList.get(0)!.includes(3); const matrixHasEdge = graph.adjacencyMatrix[0][3] === 1;

Check if edge exists using list scan and direct matrix lookup

graph.addEdgeList(2, 3); graph.addEdgeMatrix(2, 3);

Add new edge 2-3 in both structures

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]



Check edge 0-3:

List: false

Matrix: false



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(1) to add edge in adjacency matrix, O(1) amortized to add in adjacency list; O(n) to check edge in list, O(1) in matrix

Space: O(n^2) for adjacency matrix because it stores all possible edges; O(n + e) for adjacency list storing only existing edges

vs Alternative: Adjacency list is better for sparse graphs with fewer edges, saving space; adjacency matrix is better for dense graphs or when quick edge checks are needed

Edge Cases

Empty graph (no edges)

Adjacency list has empty arrays; adjacency matrix is all zeros

DSA Typescript

for (let i = 0; i < size; i++) { this.adjacencyList.set(i, []); }

Graph with one node and no edges

List has one empty array; matrix is 1x1 zero

DSA Typescript

constructor(size: number) { ... }

Adding duplicate edges

List will have duplicates; matrix stays 1 for edge

DSA Typescript

No explicit guard; duplicates allowed in list

When to Use This Pattern

When a problem involves graph representation and you need to choose storage, think about graph density and operation speed 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 when edges are few

Mistake: Checking edge existence in adjacency list without scanning neighbors
Fix: Scan the neighbor list or use a set for faster lookup

Summary

Stores graph edges either as lists of neighbors or a full grid of 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 allows instant edge lookup.

Practice

1. Which data structure is generally more space-efficient 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

   Sparse graphs have few edges compared to vertices, so storing all possible edges wastes space.

2. Step 2: Compare space usage of adjacency list and matrix

   Adjacency list stores only existing edges, using less space for sparse graphs. Adjacency matrix always uses space for all possible edges.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graph? Use adjacency list for less space [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs
• Confusing edge count with vertex count
• Ignoring space complexity differences

2. Which of the following is the correct TypeScript syntax to declare an adjacency matrix for a graph with 3 vertices initialized with zeros?

easy

A. const matrix: number[][] = new Array(3).fill(new Array(3).fill(0));

B. const matrix: number[] = [0,0,0];

C. const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]];

D. const matrix: number[][] = Array(3).map(() => Array(3).fill(0));

Solution

1. Step 1: Understand adjacency matrix type

   An adjacency matrix is a 2D array (array of arrays) of numbers representing edges.

2. Step 2: Check initialization correctness

   const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; explicitly creates a 3x3 matrix with zeros. const matrix: number[][] = new Array(3).fill(new Array(3).fill(0)); uses fill with the same inner array reference, causing bugs. const matrix: number[][] = Array(3).map(() => Array(3).fill(0)); uses map on empty array, which won't work as expected. const matrix: number[] = [0,0,0]; is 1D array, not matrix.

3. Final Answer:

   const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; -> Option C

4. Quick Check:

   Explicit 2D array with zeros = const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; [OK]

Hint: Use explicit 2D array for adjacency matrix initialization [OK]

Common Mistakes:

• Using fill with nested arrays causing shared references
• Declaring 1D array instead of 2D
• Using map on empty array without initialization

3. Given the following adjacency list representation of a graph in TypeScript:

const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: []
};
console.log(graph[2]);

What will be the output?

medium

A. [2]

B. [1, 2]

C. undefined

D. [0, 3]

Solution

1. Step 1: Identify the adjacency list for vertex 2

   In the graph object, key '2' maps to the array [0, 3].

2. Step 2: Understand console.log output

   Logging graph[2] prints the array [0, 3] representing edges from vertex 2.

3. Final Answer:

   [0, 3] -> Option D

4. Quick Check:

   graph[2] = [0, 3] [OK]

Hint: Access adjacency list by vertex key to get connected nodes [OK]

Common Mistakes:

• Confusing keys and values in adjacency list
• Expecting adjacency matrix output
• Assuming undefined for existing keys

4. Consider this TypeScript code snippet for creating an adjacency matrix for a graph with 3 vertices:

const size = 3;
const matrix = new Array(size).fill(new Array(size).fill(0));
matrix[0][1] = 1;
console.log(matrix);

What is the problem with this code?

medium

A. All rows refer to the same inner array, so all rows change when one element changes

B. The matrix is not initialized with zeros

C. The matrix is not a 2D array

D. The size variable is not used correctly

Solution

1. Step 1: Analyze the fill method usage

   Using fill with new Array(size).fill(0) creates one inner array and fills outer array with references to the same inner array.

2. Step 2: Understand effect of modifying one element

   Changing matrix[0][1] changes that element in all rows because they share the same inner array reference.

3. Final Answer:

   All rows refer to the same inner array, so all rows change when one element changes -> Option A

4. Quick Check:

   Shared inner array reference causes unexpected changes [OK]

Hint: Avoid fill with nested arrays; use map to create separate arrays [OK]

Common Mistakes:

• Thinking fill creates separate inner arrays
• Ignoring shared reference problem
• Assuming matrix is 1D array

5. You need to represent a dense graph with 1000 vertices where you frequently check if an edge exists between any two vertices. Which representation is best and why?

hard

A. Adjacency List, because it uses less space for dense graphs

B. Adjacency Matrix, because it allows O(1) edge existence checks

C. Edge List, because it is fastest for dense graphs

D. Incidence Matrix, because it uses less space than adjacency matrix

Solution

1. Step 1: Understand graph density and operation needs

   Dense graph means many edges; checking edge existence frequently requires fast lookup.

2. Step 2: Compare adjacency list and matrix for edge checks

   Adjacency matrix allows direct O(1) access to check if edge exists between two vertices. Adjacency list requires searching neighbors, which can be slower in dense graphs.

3. Step 3: Consider space tradeoff

   Though adjacency matrix uses more space, for dense graphs this is acceptable and beneficial for speed.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge existence checks -> Option B

5. Quick Check:

   Dense graph + frequent edge check = Adjacency Matrix [OK]

Hint: Dense graph + frequent edge check? Use adjacency matrix [OK]

Common Mistakes:

• Choosing adjacency list for dense graphs needing fast edge checks
• Ignoring time complexity of edge existence queries
• Confusing edge list with adjacency matrix benefits