Data Structure1 Practice2 Interview

Adjacency List

GuideCode Labs

Graph representation storing each vertex's neighbors with space proportional to vertices and edges. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Adjacency List when the prompt's constraints and required operations match this shape: Graph representation storing each vertex's neighbors with space proportional to vertices and edges.

On this page · Mental Model

Checking your account…

Mental Model

An adjacency list stores, for each vertex, only the neighbors connected by real edges. Its memory tracks graph content instead of every possible vertex pair.

Store Only Existing Neighbors

Allocate one neighbor collection for every vertex, including isolated ones. Lists preserve edge order and duplicates; sets enforce unique membership. For an undirected graph, store both directions. Space is O(V + E), counting each undirected edge twice.

Build Directed and Undirected Lists

Choose direction and duplicate policy before insertion. Independent list allocation matters: [[]] * node_count aliases all neighbor lists. Sort only if deterministic neighbor order belongs to the output or traversal contract.

Build an Undirected Adjacency List

Reference

def build_adjacency_list(node_count, edges):
    adjacency = [set() for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].add(right)
        adjacency[right].add(left)
    return [sorted(neighbors) for neighbors in adjacency]

Practice

Implement build_adjacency_list(node_count, edges). Deduplicate undirected edges, preserve isolated vertices, and sort neighbors.

def build_adjacency_list(node_count, edges):
    adjacency = [[]] * node_count
    for left, right in edges:
        adjacency[left].append(right)
    return adjacency

Public tests

Verify independent complete vertex storage

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Traverse Sparse Neighborhoods

DFS or BFS enumerates only existing edges. With discovery-time visited marking, reachability is O(V + E), unlike scanning a full matrix row for every visited vertex.

Traverse Sparse Neighbors

Reference

def reachable_vertices(adjacency, start):
    seen = {start}
    stack = [start]
    while stack:
        node = stack.pop()
        for neighbor in adjacency[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                stack.append(neighbor)
    return sorted(seen)

Practice

Implement reachable_vertices(adjacency, start). Return all reachable vertices sorted, using explicit visited state.

def reachable_vertices(adjacency, start):
    return sorted(adjacency[start])

Public tests

Verify traversal beyond direct neighbors

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose List or Matrix

Choose a list for sparse graphs and neighbor iteration. Choose a matrix for dense graphs or many constant-time edge-existence queries. A set-backed list improves duplicate checks but adds hashing cost and loses authored order.

Common Pitfalls

Omitting isolated vertices makes vertex identity depend on appearing in an edge.
Adding one direction for an undirected edge breaks reachability.
Aliased neighbor lists connect unrelated vertices.
Marking visited after removal permits duplicate frontier entries.

Explain It in an Interview

State direction, duplicate policy, and neighbor container. Explain O(V + E) by charging each stored neighbor entry once, then distinguish representation space from traversal space.

Build Graph Representations(opens in a new tab) isolates storage; Course Schedule(opens in a new tab) uses a directed adjacency list for prerequisites.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Adjacency List itself is taught as an interview abstraction.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Core Adjacency List workflow	`O(V^2 + E + V log V)`	`O(V^2 + E + V log V)`	Accumulate canonical neighbors in per-node sets while writing symmetric matrix cells, then sort each set for deterministic output.

Space

O(V^2 + E) for the demonstrated Adjacency List workflow.

Assumptions

State the concrete operation and representation before claiming a bound; tree height and graph density can change it.
The bound counts the operations in Build Graph Representations and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

State the precise Adjacency List invariant before coding and preserve it after every update, traversal step, or recursive return.
Represent sparse neighbor relationships and dense edge lookup from one graph contract. This remains true after every accepted operation.
Normalize undirected edges, duplicates, and self-loops consistently. This remains true after every accepted operation.

When To Use Or Avoid Adjacency List

Use It When

Use Adjacency List when its representation directly supports the prompt's repeated query or update.
Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Adjacency List invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def build_graph_representations(node_count, edges):
    pass

Use instead

def build_graph_representations(node_count, edges):
    adjacency = [set() for _ in range(node_count)]
    matrix = [[0 for _ in range(node_count)] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].add(right)
        adjacency[right].add(left)
        matrix[left][right] = 1
        matrix[right][left] = 1
    return [[sorted(neighbors) for neighbors in adjacency], matrix]

Where you will hit this: Build Graph Representations(opens in a new tab)

Breaking the central invariant

Records only the listed edge direction, producing a directed graph instead of the required undirected graph.

Prevent it: Keep this invariant visible while editing: State the precise Adjacency List invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def build_graph_representations(node_count, edges):
    adjacency = [[] for _ in range(node_count)]
    matrix = [[0] * node_count for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].append(right)
        matrix[left][right] = 1
    return [adjacency, matrix]

Use instead

def build_graph_representations(node_count, edges):
    adjacency = [set() for _ in range(node_count)]
    matrix = [[0 for _ in range(node_count)] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].add(right)
        adjacency[right].add(left)
        matrix[left][right] = 1
        matrix[right][left] = 1
    return [[sorted(neighbors) for neighbors in adjacency], matrix]

Where you will hit this: Build Graph Representations(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(V^2 + E + V log V).

Avoid

def build_graph_representations(node_count, edges):
    adjacency = [[] for _ in range(node_count)]
    matrix = [[0] * node_count for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].append(right)
        matrix[left][right] = 1
    return [adjacency, matrix]

Use instead

def build_graph_representations(node_count, edges):
    adjacency = [set() for _ in range(node_count)]
    matrix = [[0 for _ in range(node_count)] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].add(right)
        adjacency[right].add(left)
        matrix[left][right] = 1
        matrix[right][left] = 1
    return [[sorted(neighbors) for neighbors in adjacency], matrix]

Where you will hit this: Course Schedule(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…

Adjacency List Code Labs

Mental Model

Store Only Existing Neighbors

Build Directed and Undirected Lists

Public tests

Traverse Sparse Neighborhoods

Public tests

Choose List or Matrix

Common Pitfalls

Explain It in an Interview

Python Version Note

Complexity & Invariants

Space

Assumptions

Invariants Worth Saying Aloud

When To Use Or Avoid Adjacency List

Use It When

Choose Another Tool When

Common Pitfalls

Leaving the core transition unfinished

Breaking the central invariant

Hiding Python work inside the loop

Related Practice

Related Interview Problems

Reviewed References