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.