Adjacency List Representation of Graphs
Understand how adjacency lists represent graphs efficiently for sparse networks. Learn the data structure, memory usage, traversal performance, and comparison with adjacency matrices.
Detailed Explanation
Adjacency List
An adjacency list stores, for each node, a list of its neighbors (and optionally edge weights). It is the most common graph representation in practice because most real-world graphs are sparse.
Structure
Each node maps to a list of connected nodes:
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]
For a weighted graph:
A: [(B, 4), (C, 2)]
B: [(A, 4), (D, 3)]
C: [(A, 2), (D, 5)]
D: [(B, 3), (C, 5)]
Implementation Options
- HashMap<Node, List
> — Most flexible, handles any node type - Array of arrays — Fastest for integer-labeled nodes
- Linked lists — Classic textbook approach, less cache-friendly
Time Complexity
| Operation | Time |
|---|---|
| Check if edge exists | O(degree) |
| Add edge | O(1) |
| Remove edge | O(degree) |
| Find all neighbors | O(degree) |
| Space | O(V + E) |
Advantages
- Space-efficient for sparse graphs — O(V + E) vs O(V²)
- Fast neighbor iteration — Only visit actual neighbors
- Natural for BFS/DFS — Traversal algorithms iterate neighbors directly
Disadvantages
- Edge existence check is O(degree) — Not constant time like a matrix
- More complex implementation — Requires managing dynamic lists
Comparison
| Adjacency Matrix | Adjacency List | |
|---|---|---|
| Space | O(V²) | O(V + E) |
| Edge check | O(1) | O(degree) |
| Neighbors | O(V) | O(degree) |
| Best for | Dense graphs | Sparse graphs |
Use Case
Adjacency lists are the default choice for representing graphs in software engineering. They are used in social network backends (each user stores a list of friends/followers), in package managers (each package lists its dependencies), in web crawlers (each page links to other pages), and in virtually all graph algorithm implementations in competitive programming and interview settings.