The Core Idea
Two Ways to Store the Same Connections
A graph's abstract idea — nodes connected by edges — has to be stored concretely in memory somehow before any algorithm (DFS, BFS, Dijkstra, etc.) can actually run on it. The two standard representations, an adjacency matrix and an adjacency list, store exactly the same information but organize it completely differently, leading to very different memory usage and different speeds for different operations.
Neither representation is universally 'better' — the right choice depends entirely on how densely connected your specific graph is, and which operations (checking if a specific edge exists, versus listing all of a node's neighbors) your algorithm needs to do most often.
💡 Memory Trick
An ADJACENCY MATRIX is a full seating chart grid for every possible pair of people at a party, marked yes or no for whether they know each other — even the vast majority of 'no' pairs still take up a square on the chart. An ADJACENCY LIST is instead just each person holding a short list of only the people they actually know — no wasted space listing everyone they DON'T know.
The Two Representations
How Each One Is Built
1
Adjacency Matrix
A V × V grid (where V is the number of vertices), where cell [i][j] is marked (often with 1 or the edge's weight) if an edge exists from node i to node j, and 0 (or infinity, for weighted graphs) otherwise. Checking whether a specific edge exists is O(1) — just look up that one cell — but the matrix takes O(V²) space regardless of how many edges actually exist.
Example: a 1,000-node graph needs a 1,000 × 1,000 matrix (1 million cells) even if it only has 50 actual edges.
2
Adjacency List
An array (or hash map) of V lists, where list i contains only the nodes that node i actually connects to. This takes O(V + E) space total — proportional to the actual number of edges, not the maximum possible number. Checking whether a specific edge exists requires scanning node i's list — O(degree of i) rather than O(1) — but listing all of a node's neighbors (a very common operation in DFS/BFS) is immediate, since that's exactly what the list already contains.
Choosing Between Them
Dense Graphs vs. Sparse Graphs
The deciding factor is graph density — how many actual edges exist compared to the maximum possible number of edges (V²). For a dense graph (edges close to V², meaning most possible connections actually exist), an adjacency matrix's O(V²) space isn't much worse than the true edge count, and its O(1) 'does this edge exist' check is valuable. For a sparse graph (far fewer edges than V², which describes most real-world networks — social graphs, road networks, web links), an adjacency list's O(V + E) space is dramatically smaller, since E is much less than V².
Most real-world graphs used in practice — social networks, road networks, dependency graphs — are sparse, which is exactly why adjacency lists are the far more commonly used representation in practice, despite adjacency matrices being conceptually simpler to reason about and implement.
🖥️ Applied Scenario
You're representing a social network of 10 million users, where the average user is friends with about 200 others.
1
You calculate that an adjacency matrix would require a 10 million × 10 million grid — 100 trillion cells — an obviously infeasible amount of memory.
2
You calculate that an adjacency list requires space proportional to V + E: 10 million nodes plus roughly 10 million × 200 friendship edges — a dramatically smaller, entirely feasible number.
3
You confirm that your primary operation — 'list all of this user's friends' — is exactly what an adjacency list already stores directly per node, requiring no extra computation.
4
Conclusion: because this social network is extremely sparse (200 actual connections per user versus 10 million theoretically possible), an adjacency list is the only remotely practical representation.
📌 Exam Application
Exam questions often present a graph's density (or a specific real-world scenario) and ask you to justify which representation is more appropriate, expecting you to reference the O(V²) versus O(V + E) space trade-off directly. You may also be asked to state the time complexity of checking whether a specific edge exists, or of listing all neighbors of a given node, under each representation.
⚠️ Most Common Graph Representations Mistakes
The most common mistake is defaulting to an adjacency matrix out of familiarity without checking the graph's actual density — for any large, sparse real-world graph, this can waste an enormous, often infeasible, amount of memory. Another frequent error is assuming adjacency list's neighbor-listing speed is always O(1) — it's actually O(degree of that specific node), which only behaves like a small constant if the graph is sparse and that node doesn't have an unusually large number of connections.
✓ Quick Self-Test
Can you calculate, for a graph with 100 nodes and 150 edges, the exact space an adjacency matrix would use versus an adjacency list? Can you explain why most real-world graphs are represented with adjacency lists rather than adjacency matrices?
Next Lesson
Circular Buffer
→
← All Data Structures Lessons