jsschools

Adjacency List

A graph representation where each vertex maps to the list of its neighboring vertices, using O(V+E) space — optimal for sparse graphs.

Spec ↗

Syntax

// Map-based
const adjList = new Map();
adjList.set(u, [v1, v2, ...]);
// or Array-based (when vertices are 0-indexed integers)
const adjList = Array.from({ length: V }, () => []);

Parameters

NameTypeRequiredDescription
V number Yes Number of vertices.
directed boolean No When true, edges are one-directional. When false (default), adding edge (u, v) also adds (v, u).

Returns

Array<number[]> — An array of neighbor lists, one per vertex.

Examples

// Build and query an adjacency list
class Graph {
  #adj;
  constructor(v) { this.#adj = Array.from({ length: v }, () => []); }
  addEdge(u, v, directed = false) {
    this.#adj[u].push(v);
    if (!directed) this.#adj[v].push(u);
  }
  neighbors(u) { return this.#adj[u]; }
}
const g = new Graph(5);
g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4);
console.log(g.neighbors(0));
console.log(g.neighbors(1));
Output 
[ 1, 2 ]
[ 0, 3 ]

// Topological sort (Kahn's algorithm) using adjacency list
function topoSort(adj, V) {
  const inDeg = new Array(V).fill(0);
  for (let u = 0; u < V; u++) for (const v of adj[u]) inDeg[v]++;
  const queue = [];
  for (let i = 0; i < V; i++) if (!inDeg[i]) queue.push(i);
  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of adj[u]) if (--inDeg[v] === 0) queue.push(v);
  }
  return order.length === V ? order : []; // [] if cycle
}
const adj = [[1, 2], [3], [3], [4], []];
console.log(topoSort(adj, 5));
Output 
[ 0, 1, 2, 3, 4 ]

Notes

| Operation | Time | Space | |-------------------|-------|-------| | Add vertex | O(1) | O(1) | | Add edge | O(1) | O(1) | | Remove edge (u,v) | O(deg(u)) | O(1) | | Check edge (u,v) | O(deg(u)) | O(1) | | Iterate neighbors | O(deg(u)) | O(1) | | Total space | — | O(V+E)| Preferred over adjacency matrix when E << V². Edge existence check is O(deg(u)) rather than O(1) — use a Set of neighbors for O(1) lookups at the cost of more memory.

See also