Why create a list for every node first?

A node that appears in no edge still exists. If lists are only created when an edge mentions a node, looking up an isolated node fails or returns nothing, and it is missing when you loop over all nodes.

Why add each edge twice?

In an undirected graph an edge a-b can be walked both ways, so b goes into a’s list and a goes into b’s. For a directed edge from a to b, add b to a’s list only.

Why use an explicit stack instead of recursion?

LeetCode 1971 allows up to 200,000 nodes, and a graph that is one long path would recurse that deep, which overflows the call stack in most languages. An explicit stack does the same depth-first walk without that limit.

Graph Representation: Adjacency List

How to build and store graphs efficiently.

Medium

15 min

Solve on LeetCode

Examples

Input:n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

Output:true

Explain:

0 and 2 are joined directly, and also through 1.

Input:n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5

Output:false

Explain:

Nodes 0, 1 and 2 are never connected to 3, 4 and 5.

Representing a Graph

We don't get 'Node' objects automatically. Often, inputs are given as a list of Edges or integer pairs.

Input: n = 4, edges = [[0,1], [0,2], [2,3]].

We need to convert this into a structure that allows fast lookups of neighbors: getNeighbors(u).

Adjacency Matrix vs List

Adjacency Matrix: A 2D array adj[n][n] where adj[i][j] = 1 if connected.

Pros: O(1) edge check.
Cons: O(N²) space. Slow to iterate neighbors O(N).

Adjacency List: A Map or Array of Lists where adj[i] contains a list of neighbors.

Pros: O(V + E) space. Fast to iterate neighbors.
Verdict: Almost always use Adjacency List for interview problems unless N is very small or the graph is dense.

Visualization

ARROW = ONE END ADDED · src → dst IS THE QUESTION

EMPTY LISTS

Edges read

0 / 3

Path exists

—

adjacency list

empty

stack (top last)

Not started

Give every node 0 to 2 its own empty list — even a node no edge mentions

Edge 0-1: add 1 to 0's list

edges

source

destination

Build the adjacency list for LeetCode 1971 one edge at a time — each undirected edge lands in both of its nodes' lists — then use it: a DFS with an explicit stack starts at source and answers whether destination can be reached. Try the Isolated node preset: node 4 appears in no edge, but it still gets an empty list.

Dry Run

Input: n = 4, edges = [[0,1], [0,2], [2,3]], source = 1, destination = 3

Step	Action	State	Explanation
Init	Create lists	`0:[], 1:[], 2:[], 3:[]`	One empty list for every node, even one no edge mentions.
1	Read `[0,1]`	`0:[1], 1:[0]`	Undirected, so the edge goes into both lists.
2	Read `[0,2]`	`0:[1,2], 2:[0]`	Add to both lists.
3	Read `[2,3]`	`2:[0,3], 3:[2]`	Add to both lists. The graph is built.
4	Push source	stack `[1]`	Mark 1 visited.
5	Pop 1	stack `[0]`	1 is not 3. Neighbour 0 is unvisited: mark it and push it.
6	Pop 0	stack `[2]`	Neighbour 1 is visited: skip. Neighbour 2 is unvisited: mark and push.
7	Pop 2	stack `[3]`	Neighbour 0 is visited: skip. Neighbour 3 is unvisited: mark and push.
8	Pop 3	stack `[]`	3 is the destination. Return `true`.

Edge Cases & Common Mistakes

When building graphs, watch out for:

0-indexed vs 1-indexed: Inputs might be 1 to N. Adjust your array size to N+1 or map to 0..N-1.
Directed vs Undirected: Commonly, inputs like [u, v] imply an undirected edge (u-v), requiring adj[u].push(v) AND adj[v].push(u). If directed, only add one way.
Duplicate Edges: Some problem constraints allow parallel edges (multiple edges between same nodes). Decide if you need a Set instead of a List to ignore them.
Self Loops: An edge [u, u] might exist. It shouldn't break the build process but might affect traversal algorithms.
Disconnected Components: Some nodes might not appear in the edges list at all (isolated nodes). Ensure you initialize the list for all 0 to n-1.

Code: Build the List, Then Search It

LeetCode 1971 (Find if Path Exists in Graph): create a list for every node 0 to n - 1, add each edge in both directions, then run DFS with an explicit stack from source. Marking a node visited when it is pushed means no node is pushed twice. The stack is explicit because a path of 200,000 nodes would overflow the call stack in most languages.

Graph Representation: Adjacency List Code

1var validPath = function(n, edges, source, destination) {
2    const graph = Array.from({ length: n }, () => []);
3    for (const [a, b] of edges) {
4        graph[a].push(b);
5        graph[b].push(a);
6    }
7
8    const visited = new Array(n).fill(false);
9    visited[source] = true;
10    const stack = [source];
11    while (stack.length > 0) {
12        const node = stack.pop();
13        if (node === destination) {
14            return true;
15        }
16        for (const neighbor of graph[node]) {
17            if (!visited[neighbor]) {
18                visited[neighbor] = true;
19                stack.push(neighbor);
20            }
21        }
22    }
23    return false;
24};

Summary

Step 1 of most Graph problems is Building the Adjacency List.
Use a HashMap or Array of Lists.
Don't forget to add edges in both directions if the graph is Undirected.

Graphs Overview

Clone Graph

Graph Representation: Adjacency List

Representing a Graph

Adjacency Matrix vs List

Visualization

Dry Run

Edge Cases & Common Mistakes

Code: Build the List, Then Search It

Graph Representation: Adjacency List Code

Summary

The approach, step by step

Create every list

Add each edge both ways

Search with a stack

Frequently asked questions

Why create a list for every node first?

Why add each edge twice?

Why use an explicit stack instead of recursion?

Graph Representation

AI resume checker — match your resume to the job description