Adjacency List Graph Representation Data Structure
An Adjacency List stores a dynamic list of outgoing neighbors for each vertex, using optimal O(V + E) memory and powering nearly all modern sparse-graph algorithms.
| Operation | Complexity |
|---|---|
| Access | O(deg(v)) |
| Search | O(deg(v)) |
| Insertion | O(1) |
| Deletion | O(deg(v)) |
| Space | O(V + E) |
Interactive Visualizer · C++ / Python / Java / JS Code
Adjacency List Graph Representation
An Adjacency List represents a graph $G = (V, E)$ as an array of $V$ dynamic lists where adj[u] holds all neighbors (and optional weights) adjacent to vertex u. Because real-world graphs (maps, social networks, dependency graphs) are almost always sparse ($E \ll V^2$), Adjacency Lists use $O(V + E)$ memory and iterate every vertex's neighbors in optimal $O(\deg(u))$ time!
At a Glance
| Operation | Complexity |
| :--- | :---: |
| Memory | $O(V + E)$ |
| Add Edge (u, v) | $O(1)$ |
| Iterate All Neighbors of u | $O(\deg(u))$ |
| Check If Edge (u, v) Exists | $O(\deg(u))$ (or $O(\log \deg(u))$ if sorted) |
---
Practice Problems
Easy
1. Weighted Directed & Undirected Adjacency List + Transpose
Build a weighted adjacency list and compute its transposed (reversed-edge) graph in $O(V + E)$ time.
Approach: Store vector<vector<pair<int, int>>> adj(n); reverse each (u, v, w) into rev[v].push_back({u, w}). Time: $O(V + E)$. Space: $O(V + E)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
#include <vector>
int main() {
int n = 4;
std::vector<std::vector<std::pair<int, int>>> adj(n), rev(n);
auto addDir = [&](int u, int v, int w) { adj[u].push_back({v, w}); };
addDir(0, 1, 5); addDir(0, 2, 3); addDir(2, 3, 7);
for (int u = 0; u < n; ++u)
for (const auto& [v, w] : adj[u]) rev[v].push_back({u, w});
std::cout << "Incoming edges to 3: " << rev[3].size()
<< " (from " << rev[3][0].first << ", w=" << rev[3][0].second << ")\n";
return 0;
}
</details>
2. Compressed Sparse Row (CSR / Forward Star) Static Adjacency List
Pack a static graph into two flat arrays (head[0..V] and edges[0..E-1]) for maximum CPU cache locality and zero per-vertex heap allocations!
Approach: Count out-degrees, compute prefix sums into head[], and scatter edges into a single contiguous edges[] array. Time: $O(V + E)$ build, ultra-fast iteration.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
#include <vector>
struct CSRGraph {
int n;
std::vector<int> head, to;
CSRGraph(int n, const std::vector<std::pair<int, int>>& edges) : n(n), head(n + 1, 0), to(edges.size()) {
for (const auto& [u, v] : edges) ++head[u + 1];
for (int i = 1; i <= n; ++i) head[i] += head[i - 1];
std::vector<int> cur = head;
for (const auto& [u, v] : edges) to[cur[u]++] = v;
}
void printNeighbors(int u) const {
for (int idx = head[u]; idx < head[u + 1]; ++idx) std::cout << to[idx] << " ";
}
};
int main() {
CSRGraph g(4, {{0, 1}, {0, 2}, {0, 3}, {2, 3}});
g.printNeighbors(0);
std::cout << "\n"; // 1 2 3
return 0;
}
</details>
---
Related Structures & Algorithms
- Adjacency Matrix — $O(1)$ edge lookup alternative for dense graphs.
- Breadth-First Search (BFS) & Depth-First Search (DFS) — run in $O(V + E)$ on Adjacency Lists.