GraphsData structureaka neighbor lists, adj

Adjacency List

For each vertex, a list of its neighbors (and edge weights), giving O(V + E) space and O(deg) neighbor iteration — the default graph representation.

▶ Visualize Pattern: Breadth-First Search Practice (5)

Progress

Definition

An adjacency list stores, for every vertex u, the collection adj[u] of vertices adjacent to u (with weights when the graph is weighted). Total storage is O(V + E): one slot per vertex plus one entry per edge (two per undirected edge).

Iterating a vertex's neighbors costs O(deg(u)), which is what makes Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra's Algorithm, Topological Sort, and virtually every graph algorithm run in O(V + E) or O(E log V). It is the representation to reach for unless the graph is dense or you specifically need O(1) edge lookup.

Concrete forms: array of dynamic arrays (vector<vector<int>>, number[][]), a hash map from vertex id to list when ids are not 0…V-1, sets instead of lists when O(1) edge lookup/deletion matters, or the compact CSR (compressed sparse row) layout — two flat arrays offsets and targets — for cache-friendly, immutable graphs.

sparse graphO(V + E)default representationneighbor iterationCSR

Intuition

A mental model before the formal terms.

A phone contact list: each person has their own list of friends. To find who Alice knows you read her list, not a table of every possible pair. Storage grows with the number of friendships, not the square of the population.

Checking "does Alice know Bob?" means scanning Alice's list — fine for short lists, slow for a celebrity with a million contacts. That is the trade-off against the Adjacency Matrix.

How it works

Allocate adj as V empty lists (or an empty map keyed by vertex).
addEdge(u, v): adj[u].push(v); for an Undirected Graph also adj[v].push(u). For a Weighted Graph push (v, w) pairs.
neighbors(u): return adj[u]. degree(u): adj[u].length.
hasEdge(u, v): linear scan of adj[u], or O(1) if each list is a hash set.
removeEdge(u, v): find and splice out of adj[u] (and adj[v]); O(deg) with lists, O(1) with sets.
Build from an Edge List in O(V + E): one pass to push each edge. Build CSR by counting degrees, prefix-summing to offsets, then filling targets.
When vertex ids are strings or sparse integers, map them to 0…V-1 first (a Hash Map from id to index) so arrays can be used.

Why it works

Each edge is stored exactly where it is needed — next to its source vertex — so traversals touch each edge once per endpoint, giving the O(V + E) bound.

Space is proportional to the actual number of edges, so sparse graphs with V = 10⁶ and E = 3·10⁶ fit comfortably where a matrix (10¹² cells) cannot exist.

Operations

Operation	Description	Cost
addEdge(u, v[, w])	Append to adj[u] (and adj[v] if undirected).	O(1)
removeEdge(u, v)	Splice out of the list (O(1) with a set).	O(deg(u))
hasEdge(u, v)	Scan adj[u] (O(1) with a set).	O(deg(u))
neighbors(u)	Iterate adj[u].	O(deg(u))
degree(u)	Length of adj[u].	O(1)
addVertex	Push a new empty list.	O(1) amortized
buildFromEdges	One pass over the edge list.	O(V + E)
BFS / DFS	Visit every vertex and edge once.	O(V + E)

Recognition

How to tell a problem wants this.

Any graph problem where the input is a list of edges or pairs and V is large.
n up to 10⁵ or more with m edges of similar magnitude.
Traversal-heavy algorithms: BFS, DFS, Dijkstra, topological sort, components.
Trees given as parent arrays or edge lists — build children lists.

“minimum steps” → Breadth-First Search “connected groups” → Depth-First Search “weighted graph” → Shortest Path (Weighted)“prerequisites” → Topological Sort

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Breadth-First Search (BFS) visualization.

Graph — One edge per line: "A B". Optional "source: A" / "target: F" lines.

Queue (front → back)

1/42Start BFS from A. Put it in the queue and mark it visited with distance 0.

Current nodeIn queueVisitedBFS tree edge

PseudocodeLearn Breadth-First Search (BFS) →

1queue = [source]; visited = {source}
2while queue not empty:
3  u = queue.popleft()
4  for v in neighbors(u):
5    if v not in visited:
6      visited.add(v); parent[v] = u
7      queue.append(v)

Complexity

best O(V + E)

avg O(V + E)

worst O(V + E)

space O(V)

Speed

Pseudocode

1adj = [[] for _ in range(V)]
2for u, v in edges: adj[u].append(v); adj[v].append(u)  # undirected
3neighbors(u): return adj[u]
4csr: offsets[u+1] = offsets[u] + deg(u); targets[offsets[u]..offsets[u+1]) = neighbors of u

Implementation

1class AdjacencyList:
2    """The default representation: one list of neighbours per vertex.
3    Vertices are 0..n-1, which lets the outer container be a flat list."""
4 
51 · State: adj[u] holds every v with an edge u -> v
6    def __init__(self, n: int, directed: bool = False) -> None:
7        self.adj: list[list[int]] = [[] for _ in range(n)]
8        self.directed = directed
9 
102 · Adding an edge is an append on one or both endpoints
11    def add_edge(self, u: int, v: int) -> None:
12        self.adj[u].append(v)
13        if not self.directed:
14            self.adj[v].append(u)
15 
16    def __len__(self) -> int:
17        return len(self.adj)
18 
19    def neighbours(self, u: int) -> list[int]:
20        return self.adj[u]
21 
22    def degree(self, u: int) -> int:
23        return len(self.adj[u])
24 
253 · Iterating all edges is O(V + E) — the whole point of the structure
26    def edges(self) -> list[tuple[int, int]]:
27        out: list[tuple[int, int]] = []
28        for u, row in enumerate(self.adj):
29            for v in row:
30                if self.directed or u <= v:  # undirected: emit once
31                    out.append((u, v))
32        return out
33 
344 · Membership is O(deg(u)) — the price paid for the compact storage
35    def has_edge(self, u: int, v: int) -> bool:
36        return v in self.adj[u]
37 
385 · Reversing a directed graph rebuilds the lists with edges flipped
39    def reversed(self) -> "AdjacencyList":
40        r = AdjacencyList(len(self.adj), directed=True)
41        for u, row in enumerate(self.adj):
42            for v in row:
43                r.adj[v].append(u)
44        return r

Walkthrough

[[] for _ in range(n)] builds n distinct lists; [[]] * n would alias one list n times, the exact analogue of the JavaScript fill bug.
__len__ makes len(graph) return the vertex count, which reads better than a size() method.
for u, row in enumerate(self.adj) walks vertex and neighbour list together, avoiding range(len(...)) plus indexing.
v in self.adj[u] is a linear scan; swapping the inner lists for set objects makes it O(1) at the cost of losing insertion order.
The return annotation "AdjacencyList" is quoted because the class is not yet bound when the method is defined.

Complexity (this implementation)

time O(1) add_edge, O(deg(u)) has_edge, O(V + E) full traversal · space O(V + E)

Every neighbour is a boxed int object; for large graphs array.array("i") or NumPy cuts memory by roughly an order of magnitude.

Language notes

collections.defaultdict(list) is the idiomatic representation when vertices are labels rather than a dense 0..n-1 range.
[[]] * n aliases and is the classic Python graph bug; the list comprehension is the fix.
networkx is the standard library-adjacent answer for real graph work and handles labelled vertices, attributes and dozens of algorithms.
from __future__ import annotations removes the need to quote the forward-referenced return type.

Common mistakes in this language

Writing self.adj = [[]] * n, after which adding one edge appears to add it to every vertex.
Using a dict keyed by vertex but forgetting isolated vertices, so len(graph) undercounts and traversals skip them.
Mutating the list returned by neighbours() and corrupting the graph, since Python returns the live list rather than a copy.

Language differences that matter here

Building n distinct empty lists is a trap in two languages for the same reason: new Array(n).fill([]) in JS/TS and [[]] * n in Python both alias one list; C++ std::vector<std::vector<int>>(n) value-initialises n separate vectors.
Labelled vertices: Python reaches for defaultdict(list), JS/TS for Map (never a plain object, whose keys coerce to strings), and C++ for std::unordered_map<Label, std::vector<Label>>.
Exposing the neighbour list: TypeScript can return readonly number[] and C++ const std::vector<int>&, both compile-time protections; JavaScript and Python hand back the live list with nothing stopping a caller from mutating it.
Cache-friendly alternatives differ in name only — CSR in C++, Int32Array plus offsets in JS/TS, array.array or NumPy in Python — and all three beat a container-of-containers on a static graph.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Vertex's list by index.
Search	O(deg(u))	O(V)	Edge existence; O(1) with hash sets.
Insert	O(1)	O(1)	Edge or vertex (amortized).
Delete	O(deg(u))	O(V)	Edge; O(1) with hash sets.
Update	O(deg(u))	O(V)	Change an edge weight.
Neighbors	O(deg(u))	O(V)
Degree	O(1)	O(1)
BFS / DFS	O(V + E)	O(V + E)
Space	O(V + E)		Undirected edges are stored twice.

Advantages & disadvantages

Advantages

O(V + E) space — optimal for sparse graphs.
Neighbor iteration in O(deg) gives linear-time traversals.
Vertices and edges can be added dynamically.
Supports parallel edges and edge attributes naturally.

Disadvantages

Edge lookup hasEdge(u, v) is O(deg(u)) unless lists are replaced by hash sets (more memory, slower iteration).
Edge deletion is O(deg) with plain lists.
Pointer-chasing across many small arrays is less cache-friendly than a matrix or CSR on dense graphs.
For dense graphs it uses more memory than a bit-packed matrix.

Use cases

Default representation in every graph algorithm on this site: Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra's Algorithm, Kahn's Algorithm, Tarjan's SCC Algorithm.
Social networks, web graphs, road networks — all sparse.
Trees: children lists built from (parent, child) pairs.
Course Schedule, Clone Graph, Number of Connected Components — build from edge pairs, then traverse.

Use it when

Almost always — it is the default for sparse graphs and traversal algorithms.
V is large and E is far below V².
Vertices or edges are added during the algorithm.

Avoid it when

Dense graphs with many hasEdge queries — use an Adjacency Matrix.
Algorithms that only sort or scan edges (Kruskal) — an Edge List is enough.
Read-only huge graphs where cache locality matters — use CSR (a flattened adjacency list).

Alternatives

Adjacency Matrix Edge List

Common mistakes

Using [[]] * n in Python — every vertex shares the same list.
Forgetting the reverse insertion for undirected graphs.
Not sizing adj for isolated vertices when building from edges (a vertex with no edges must still exist).
Assuming vertex ids are 0…V-1 when the input uses arbitrary labels — map them first.
Using a list where a set is needed for frequent hasEdge / removeEdge calls.

Interview patterns

Build the list from edge pairs, then BFS/DFS: Number of Connected Components, Clone Graph, Course Schedule.
Weighted list with (v, w) for Dijkstra: Network Delay Time.
Reverse graph for "who can reach t" questions (Kosaraju, All Paths Lead to Destination).
Convert a tree given as a parent array into children lists for a DFS.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner
Recursion versus iterationIntermediate
When space complexity mattersIntermediate

Mock interviews

Course ScheduleIntermediate
Network Delay TimeAdvanced
Number of IslandsIntermediate

Interview problems

Word Ladderhard Clone Graphmedium Number of Connected Componentsmedium Network Delay Timemedium Course Schedulemedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related