Adjacency List Representation in DSA Typescript

Mental Model

We store each node and a list of its neighbors to show connections in a graph.

Analogy: Imagine a group of friends where each person keeps a list of their friends' names. This way, you know who is connected to whom by looking at each person's list.

Node 0 -> [1, 2]
Node 1 -> [0, 3]
Node 2 -> [0]
Node 3 -> [1]

Dry Run Walkthrough

Input: Graph with edges: 0-1, 0-2, 1-3

Goal: Build adjacency lists showing neighbors for each node

Step 1: Add edge 0-1: add 1 to node 0's list and 0 to node 1's list

Node 0 -> [1]
Node 1 -> [0]
Node 2 -> []
Node 3 -> []

Why: We record that node 0 and node 1 are connected

Step 2: Add edge 0-2: add 2 to node 0's list and 0 to node 2's list

Node 0 -> [1, 2]
Node 1 -> [0]
Node 2 -> [0]
Node 3 -> []

Why: We record that node 0 and node 2 are connected

Step 3: Add edge 1-3: add 3 to node 1's list and 1 to node 3's list

Node 0 -> [1, 2]
Node 1 -> [0, 3]
Node 2 -> [0]
Node 3 -> [1]

Why: We record that node 1 and node 3 are connected

Result:

Node 0 -> [1, 2]
Node 1 -> [0, 3]
Node 2 -> [0]
Node 3 -> [1]

Annotated Code

DSA Typescript

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

  constructor(nodes: number) {
    this.adjacencyList = new Map();
    for (let i = 0; i < nodes; i++) {
      this.adjacencyList.set(i, []);
    }
  }

  addEdge(u: number, v: number): void {
    this.adjacencyList.get(u)?.push(v); // add v to u's neighbors
    this.adjacencyList.get(v)?.push(u); // add u to v's neighbors
  }

  printGraph(): void {
    for (const [node, neighbors] of this.adjacencyList.entries()) {
      console.log(`Node ${node} -> [${neighbors.join(", ")}]`);
    }
  }
}

// Driver code
const graph = new Graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.printGraph();

this.adjacencyList.set(i, []);

Initialize empty neighbor list for each node

this.adjacencyList.get(u)?.push(v);

Add v to u's neighbor list to record edge

this.adjacencyList.get(v)?.push(u);

Add u to v's neighbor list to record edge (undirected graph)

for (const [node, neighbors] of this.adjacencyList.entries()) {

Iterate over all nodes to print their neighbors

Output

Node 0 -> [1, 2]

Node 1 -> [0, 3]

Node 2 -> [0]

Node 3 -> [1]

Complexity Analysis

Time: O(V + E) because we initialize all nodes and add each edge once

Space: O(V + E) because we store a list of neighbors for each node and each edge twice

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, adjacency list is more efficient for sparse graphs

Edge Cases

Graph with no edges

All nodes have empty neighbor lists

DSA Typescript

this.adjacencyList.set(i, []);

Graph with single node

One node with empty neighbor list

DSA Typescript

this.adjacencyList.set(i, []);

Adding edge with invalid node index

No neighbors added because get returns undefined and optional chaining prevents error

DSA Typescript

this.adjacencyList.get(u)?.push(v);

When to Use This Pattern

When you need to represent graph connections efficiently and want to quickly find neighbors of a node, use adjacency list representation because it stores only existing edges.

Common Mistakes

Mistake: Forgetting to add the edge in both directions for undirected graphs
Fix: Add neighbors to both nodes' lists to represent undirected edges

Summary

Stores each node with a list of its connected neighbors to represent a graph.

Use when you want efficient storage and quick access to neighbors in sparse graphs.

The key is each node keeps its own list of neighbors, so you only store actual connections.