AntInLoop

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.

OperationComplexity
AccessO(deg(v))
SearchO(deg(v))
InsertionO(1)
DeletionO(deg(v))
SpaceO(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