Adjacency List

Explanation

To store a graph, you need to represent which vertices are connected by edges. The adjacency list approach gives each vertex its own list of neighbors. In code, this is typically a Map (or array indexed by vertex number) where each key is a vertex and each value is an array of adjacent vertices (and optionally edge weights). Space complexity: O(V + E) — you store each vertex once and each edge once (twice for undirected graphs). This is optimal for sparse graphs where E << V². In contrast, an adjacency matrix uses O(V²) space regardless of edge count. For a social network with 1 billion users but only ~200 connections each, an adjacency matrix would require storing 10^18 entries — impossible. An adjacency list stores only 200 billion entries (one per edge) — still large, but tractable. Time complexity trade-offs: adjacency list gives O(degree(v)) to check if an edge (u, v) exists — you scan u's neighbor list. An adjacency matrix gives O(1) for edge existence but O(V) to find all neighbors. For algorithms like DFS, BFS, and Dijkstra that iterate all neighbors of a vertex, adjacency lists are more efficient on sparse graphs. For weighted graphs, each entry in the neighbor list includes both the neighbor vertex and the edge weight: adj.get(u) = [{vertex: v, weight: 3}, ...]. This is the standard representation for Dijkstra's algorithm and other weighted-graph algorithms.

Code Example

// Building an adjacency list from an edge list

// Undirected weighted graph
function buildGraph(n, edges) {
  // n vertices labeled 0..n-1
  const adj = Array.from({ length: n }, () => []);

  for (const [u, v, weight] of edges) {
    adj[u].push({ to: v, w: weight });
    adj[v].push({ to: u, w: weight }); // omit for directed
  }
  return adj;
}

const edges = [[0,1,4],[0,2,1],[1,2,2],[1,3,5],[2,3,8]];
const graph = buildGraph(4, edges);

// DFS using adjacency list
function dfs(adj, start, visited = new Set()) {
  visited.add(start);
  console.log(start);
  for (const { to } of adj[start]) {
    if (!visited.has(to)) dfs(adj, to, visited);
  }
}

dfs(graph, 0); // 0, 1, 2, 3 (order depends on edge insertion)

Why It Matters for Engineers

Graph problems make up a significant portion of coding interviews at top tech companies, and almost every graph problem provides input as an edge list that you convert to an adjacency list as your first step. Being fluent in building and traversing adjacency lists — and knowing why they're the right choice for sparse graphs — is essential graph algorithm knowledge. In real systems, graph representations matter for performance: a social network's friend graph, a web crawler's link graph, and a logistics network's route graph all use adjacency list-equivalent representations in production databases like Neo4j or Apache Spark's GraphX because the sparse-graph properties hold at scale.