Adjacency List for Coding Interviews: Build It, When a Matrix Wins, and How to Traverse It

An adjacency list represents a graph by storing the neighbors of each node. It is the default graph representation for Software Engineer interviews because it uses O(V + E) space and lets a traversal inspect only the edges that actually exist.

The representation is simple. The judgment is deciding whether to build it at all. An edge list usually needs conversion. A tree already exposes its children. A grid, URL crawler, or combination lock has neighbors that are cheaper to generate on demand. This guide covers all three cases with runnable Python.

Build an adjacency list from edges

For an undirected graph with edges (0, 1), (0, 2), (1, 3), and (2, 3), each edge appears in both endpoint lists.

This builder keeps isolated nodes and also tolerates endpoints that were omitted from nodes:

def build_adjacency(nodes, edges, directed=False):
    """Return dict[node, list[node]] for an unweighted graph."""
    adjacency = {node: [] for node in nodes}

    for source, target in edges:
        adjacency.setdefault(source, []).append(target)
        adjacency.setdefault(target, [])
        if not directed:
            adjacency[target].append(source)

    return adjacency

if __name__ == "__main__":
    nodes = range(5)  # node 4 is isolated
    edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
    print(build_adjacency(nodes, edges))

Output:

{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2], 4: []}

The build takes O(V + E) time and space. For an undirected graph, there are 2E neighbor entries, which is still O(E).

Small changes cover common variants:

Graph type	Stored neighbor entry	Build rule
Directed	target	Add only source -> target
Undirected	target and source	Add both directions
Weighted directed	(target, weight)	Add one tuple
Weighted undirected	(target, weight) and (source, weight)	Add reversed tuple too
Duplicate-free	Use a set while building	Convert to sorted lists if deterministic order matters

Direction is the first thing to state aloud. Forgetting the reverse edge on an undirected graph creates a traversal that works from some start nodes and fails from others. For a directed acyclic graph, the same forward list plus indegree counts feeds topological sort.

Choose a list, matrix, or generated neighbors

An adjacency matrix is a V by V table where matrix[u][v] records whether an edge exists. A grid of terrain values is not an adjacency matrix. The grid stores node data; its edges are implied by neighboring coordinates.

Operation	Adjacency list	Adjacency matrix
Space	O(V + E)	O(V²)
Test one edge	O(deg(u)), or expected O(1) with neighbor sets	O(1)
Iterate neighbors of one node	O(deg(u))	O(V)
Full BFS or DFS	O(V + E)	O(V²)
Good fit	Sparse graphs, which dominate interview problems	Small dense graphs or all-pairs algorithms

The matrix wins when the graph is dense, the node count is small, or constant-time edge tests dominate. Floyd-Warshall is the standard matrix-shaped algorithm because it updates a distance for every node pair.

Generated neighbors are better when the relationship can be computed cheaply. A four-direction grid is the clearest example:

def grid_neighbors(row, col, rows, cols):
    for delta_row, delta_col in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_row = row + delta_row
        next_col = col + delta_col
        if 0 <= next_row < rows and 0 <= next_col < cols:
            yield next_row, next_col

Building a dictionary for every grid cell would duplicate information already encoded by coordinates. The same idea applies to combination-lock states, word transformations, and URLs returned by a fetch function.

For a crawler, normalization is part of node identity. Resolve relative URLs, strip fragments, and check the canonical URL before enqueueing. At larger scale, frontier and deduplication become system concerns covered in the web-crawler design guide.

Traverse safely with BFS and DFS

BFS gives shortest-path distances in an unweighted graph. Mark nodes when they enter the queue so the same node cannot be enqueued by several parents.

from collections import deque

def bfs_distances(adjacency, start):
    distance = {start: 0}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbor in adjacency.get(node, ()):
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)

    return distance

if __name__ == "__main__":
    graph = {
        0: [1, 2],
        1: [0, 3],
        2: [0, 3],
        3: [1, 2],
        4: [],
    }
    print(bfs_distances(graph, 0))

Output:

{0: 0, 1: 1, 2: 1, 3: 2}

Node 4 is absent from the result because it is unreachable from node 0. That is different from a distance of zero or infinity, and the caller should decide which output convention it needs.

An iterative DFS avoids recursion-depth failures on long path-shaped graphs:

def dfs_order(adjacency, start):
    seen = set()
    order = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)

        # Reverse a list to preserve its left-to-right order in the traversal.
        for neighbor in reversed(adjacency.get(node, ())):
            if neighbor not in seen:
                stack.append(neighbor)

    return order

if __name__ == "__main__":
    graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
    print(dfs_order(graph, 0))

Both traversals are O(V + E) over an adjacency list. A weighted shortest-path problem changes the queue into a priority queue and records tentative costs; the heap guide covers that container choice.

This short overview compares graph representations visually:

Video: Graph Data Structure Intro (inc. adjacency list, adjacency matrix, incidence matrix)

A reliable graph-problem checklist

Use this sequence before choosing BFS, DFS, or a shortest-path algorithm:

1. Define the node. A city, course, grid cell, URL, or state tuple can be a node.
2. Define one edge. State whether it is directed and whether it has a weight.
3. Choose the neighbor source. Build from edges, traverse existing children, or generate neighbors.
4. Normalize identity. Make equal logical nodes use equal keys.
5. Choose the traversal goal. Reachability suggests DFS or BFS; unweighted distance suggests BFS; weighted distance needs a different shortest-path method.
6. Mark discovery at the right time. For BFS, mark on enqueue. For iterative DFS, either mark on push or guard on pop consistently.
7. State complexity for the representation. A matrix traversal is O(V²), not O(V + E).

Backtracking can look similar because it also explores choices, but its state is usually a partial candidate rather than a persistent graph node. The backtracking guide explains when to switch mental models.

FAQ

Does an adjacency list have to be a dictionary of lists?

No. A list of lists is efficient when nodes are integers from 0 to n - 1. A dictionary supports arbitrary hashable IDs. Sets can remove duplicate edges and speed up edge-existence checks, but they do not preserve a stable neighbor order.

Why include isolated nodes during construction?

An edge-only build never sees them. Initializing every known node preserves the difference between “this node exists with no neighbors” and “this node was absent from the input.”

Should I sort neighbor lists?

Only when the output requires deterministic or lexical order. Sorting every list adds work. Most reachability and distance problems accept any valid traversal order.

Can BFS use a generated neighbor function instead of a stored graph?

Yes. Replace adjacency.get(node, ()) with neighbors(node). Complexity then depends on how many states are reached and how expensive each neighbor generation is.

When is an adjacency matrix the better answer?

Use it for small dense graphs, repeated constant-time edge tests, or algorithms whose state is already a V by V table. For sparse interview graphs, an adjacency list is normally clearer and much smaller.