Adjacency list, adjacency matrix or edge list?

Graphs Junior Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

edges = [(0, 1), (0, 2), (2, 3)]
graph: dict[int, list[int]] = {v: [] for v in range(4)}
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
print(graph[0], graph[3], sum(map(len, graph.values())))

Options[1, 2] [2] 6[1, 2] [] 3[1, 2] [2] 3

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [1, 2] [2] 6

Right: each undirected edge appears twice, so 3 edges give 6 entries.

An undirected adjacency list holds 2E entries, which is why its memory is O(V + E).

Why not the others?

B [1, 2] [] 3. Undirected edges are added in both directions.
C [1, 2] [2] 3. Count both directions: 2 × 3 = 6.

30-second answer

An adjacency list (a list or dict of neighbour lists) uses O(V + E) memory and lists a node's neighbours in time proportional to its degree, so it suits most sparse graphs. An adjacency matrix uses O(V²) memory but answers 'is there an edge?' in O(1). An edge list is just the input pairs, ideal for Kruskal or union-find.

Practise saying it · 45 s. No recording, just a timer

Compare ways to store a graph.

Say your answer out loud, then check which of these points you covered:

List: O(V + E)
Matrix: O(V²), O(1) edge test
Edge list for Kruskal

Deep dive

Grids are implicit graphs: neighbours are computed from coordinates, so no list needs building.

For weighted graphs store (neighbour, weight) pairs in the list.

Building the adjacency list from edges is O(V + E) and usually the first five lines of a graph answer.

Common mistakes

Building a V by V matrix for a sparse graph with a million nodes.
Forgetting to add both directions for undirected edges.

Senior take & follow-ups

State V and E early; every graph cost is written in terms of them.

Follow-up questions

Think of your answer first, then open the hint.

When is a matrix better?
Show hint
Dense graphs or algorithms like Floyd-Warshall that touch every pair.
How do graph databases store this?
Show hint
As adjacency kept next to each node or in edge tables keyed by node, tuned for neighbour lookups.

Similar on Backend: When a graph database helps Graph databases keep adjacency on disk so neighbour lookups stay fast; in an interview you hold the same adjacency list in memory.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.