The adjacency list

Lesson · 8 min read · Graphs · Storing a graph

One list of neighbours per node: memory in proportion to the edges, and the representation almost every graph algorithm expects.

Structure

An adjacency list keeps, for each node, a list of the nodes it has an edge to. Nothing is stored for pairs that are not connected, so the memory is proportional to n + m rather than n².

stored as→

The same four-node graph as in the matrix lesson. Each undirected edge appears in two lists.

Every graph traversal does the same thing at every node: "for each neighbour v of u". With a list that loop touches exactly the neighbours, so a full traversal costs O(n + m). With a matrix the same loop reads n entries per node, for O(n²) in total.

Weights, and nodes that are not numbers

For a weighted graph each entry becomes a pair (neighbour, weight).

Step 1 / 2

stored as→
Entries written neighbour·weight: node 0 has edges to 1 (weight 4) and 2 (weight 1).
Step 2 / 2

stored as→
A map from ticker to neighbours. An edge here could mean "returns correlated above some threshold".

When nodes have names (tickers, words, account numbers), use a hash map from name to list instead of an array. Nothing else in an algorithm changes: it still asks for the neighbours of a node.

Implementation

Almost every graph problem hands you an edge list and expects you to build the adjacency list first. This is the code to have in your fingers:

from collections import defaultdict

def build(n, edges, directed=False):
    adj = [[] for _ in range(n)]          # nodes 0..n-1
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)              # the line most often forgotten
    return adj

def build_weighted(edges):
    adj = defaultdict(list)               # nodes with any hashable label
    for u, v, w in edges:
        adj[u].append((v, w))
    return adj

std::vector<std::vector<int>> build(int n, const std::vector<std::pair<int, int>>& edges,
                                    bool directed = false) {
    std::vector<std::vector<int>> adj(n);          // nodes 0..n-1
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        if (!directed) adj[v].push_back(u);        // the line most often forgotten
    }
    return adj;
}

using Weighted = std::unordered_map<std::string, std::vector<std::pair<std::string, int>>>;

Weighted build_weighted(const std::vector<std::tuple<std::string, std::string, int>>& edges) {
    Weighted adj;                                  // nodes with any hashable label
    for (const auto& [u, v, w] : edges) adj[u].push_back({v, w});
    return adj;
}

static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());   // nodes 0..n-1
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        if (!directed) adj.get(e[1]).add(e[0]);              // the line most often forgotten
    }
    return adj;
}

record Edge(String from, String to, int weight) {}

static Map<String, List<Edge>> buildWeighted(List<Edge> edges) {
    Map<String, List<Edge>> adj = new HashMap<>();            // nodes with any label
    for (Edge e : edges) adj.computeIfAbsent(e.from(), k -> new ArrayList<>()).add(e);
    return adj;
}

function build(n, edges, directed = false) {
    const adj = Array.from({ length: n }, () => []);   // nodes 0..n-1
    for (const [u, v] of edges) {
        adj[u].push(v);
        if (!directed) adj[v].push(u);                 // the line most often forgotten
    }
    return adj;
}

function buildWeighted(edges) {
    const adj = new Map();                             // nodes with any label
    for (const [u, v, w] of edges) {
        if (!adj.has(u)) adj.set(u, []);
        adj.get(u).push([v, w]);
    }
    return adj;
}

fn build(n: usize, edges: &[(usize, usize)], directed: bool) -> Vec<Vec<usize>> {
    let mut adj = vec![Vec::new(); n];                 // nodes 0..n-1
    for &(u, v) in edges {
        adj[u].push(v);
        if !directed { adj[v].push(u); }               // the line most often forgotten
    }
    adj
}

fn build_weighted<'a>(edges: &[(&'a str, &'a str, i64)]) -> HashMap<&'a str, Vec<(&'a str, i64)>> {
    let mut adj: HashMap<&str, Vec<(&str, i64)>> = HashMap::new();   // nodes with any hashable label
    for &(u, v, w) in edges {
        adj.entry(u).or_default().push((v, w));
    }
    adj
}

build :: Int -> [(Int, Int)] -> Bool -> Array Int [Int]
build n edges directed =
  accumArray (flip (:)) [] (0, n - 1)            -- nodes 0 .. n - 1
    [ e | (u, v) <- edges, e <- (u, v) : [ (v, u) | not directed ] ]   -- (v, u): the edge most often forgotten

buildWeighted :: Ord a => [(a, a, Int)] -> Map.Map a [(a, Int)]
buildWeighted edges = Map.fromListWith (flip (++)) [ (u, [(v, w)]) | (u, v, w) <- edges ]   -- any orderable label

Converting a matrix to a list is a matter of reading each row. The problem at the end of this module asks for exactly that; here is its solution in all six languages.

def matrix_to_list(matrix):
    # Row i lists the edges leaving i; reading it left to right keeps them sorted.
    return [[j for j, x in enumerate(row) if x == 1] for row in matrix]

#include <vector>

std::vector<std::vector<int>> solve(const std::vector<std::vector<int>>& matrix) {
    const int n = matrix.size();
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (matrix[i][j] == 1) adj[i].push_back(j);   // row i: edges leaving i
    return adj;
}

class Solution {
    public int[][] matrixToList(int[][] matrix) {
        int n = matrix.length;
        int[][] adj = new int[n][];
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int x : matrix[i]) if (x == 1) count++;
            adj[i] = new int[count];
            int k = 0;
            for (int j = 0; j < n; j++) if (matrix[i][j] == 1) adj[i][k++] = j;   // row i: edges leaving i
        }
        return adj;
    }
}

function matrixToList(matrix) {
  // Row i lists the edges leaving i; reading it left to right keeps them sorted.
  return matrix.map(row => {
    const out = [];
    for (let j = 0; j < row.length; j++) if (row[j] === 1) out.push(j);
    return out;
  });
}

fn solve<const N: usize>(matrix: &[[i64; N]]) -> Vec<Vec<i64>> {
    // Row i lists the edges leaving i; reading it left to right keeps them sorted.
    matrix
        .iter()
        .map(|row| (0..N).filter(|&j| row[j] == 1).map(|j| j as i64).collect())
        .collect()
}

solve :: [[Int]] -> [[Int]]
-- Row i lists the edges leaving i; reading it left to right keeps them sorted.
solve matrix = [[j | (j, x) <- zip [0 ..] row, x == 1] | row <- matrix]

The same code is the reference solution to Adjacency matrix to adjacency list, where it is compiled and run against the tests in all six languages.

Matrix or list

The two representations trade the same costs in opposite directions. A third, the plain list of edges, is what problems usually give you; it is the right structure for Kruskal's algorithm and Bellman–Ford, which only ever loop over all edges.

Operation	Matrix	Adjacency list	Edge list
Is there an edge u → v?	O(1)	O(deg u)	O(m)
List the neighbours of u	O(n)	O(deg u)	O(m)
Visit every edge	O(n²)	O(n + m)	O(m)
Memory	O(n²)	O(n + m)	O(m)
Best for	dense, small n, Floyd–Warshall	traversals, Dijkstra, almost everything	Kruskal, Bellman–Ford

TimeO(n + m) to build and to traverse

SpaceO(n + m)

If you need fast "is there an edge?" checks as well, store each node's neighbours in a hash set instead of a list: O(1) checks on average, still O(n + m) memory.

Default to the adjacency list. Reach for the matrix only when n is small and the graph is dense, or when the algorithm is built on it.