Adjacency List Representation

When working with graphs in software, one of the first and most important decisions is choosing how to store the graph in memory. The adjacency list is the most widely used graph representation, especially in practical programming contexts, because it scales gracefully to large, sparse graphs and maps naturally onto common data structures like arrays, objects, and hash maps. Understanding it deeply — including its trade-offs against alternatives like the adjacency matrix — is essential before implementing any graph algorithm.

A graph consists of a set of vertices (also called nodes) and a set of edges (connections between pairs of vertices). The challenge is encoding this relational structure efficiently. An adjacency list solves this by giving every vertex its own list of neighbors — the vertices it is directly connected to — and nothing more. This deceptively simple idea has profound consequences for memory usage and algorithm performance.

What Is an Adjacency List?

At its core, an adjacency list is a collection of lists, one per vertex. Each list contains exactly the vertices that share a direct edge with the vertex that owns the list. No space is reserved for vertex pairs that are not connected, which is what distinguishes this approach from an adjacency matrix.

Consider a small undirected graph with four vertices — A, B, C, and D — and the following edges: A–B, A–C, B–D, and C–D. The adjacency list looks like this:

Every row captures only the real connections for that vertex. If you add a fifth isolated vertex E (one with no edges), its row simply holds an empty list — it consumes almost no additional memory.

In JavaScript, this structure is most naturally implemented as a plain object (using vertex identifiers as keys and arrays of neighbors as values) or as a Map (which supports non-string keys and preserves insertion order). Both choices give O(1) average-case access to any vertex's neighbor list by key lookup.

// Object-based adjacency list for the graph above
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C']
};

// Accessing A's neighbors
console.log(graph['A']); // ['B', 'C']

For an undirected graph, each edge (u, v) appears in both u's list and v's list, because the relationship is symmetric — if you can travel from u to v, you can also travel from v to u. This means every undirected edge is stored twice in total across the entire structure, but this is intentional and necessary for correct traversal in both directions.

Building an Adjacency List in JavaScript

A clean, reusable implementation wraps the adjacency list in a class with dedicated helper methods. This keeps the construction logic organized and makes it easy to extend the graph incrementally.

class Graph {
  constructor() {
    // Each key maps to an array of neighboring vertex identifiers
    this.adjacencyList = {};
  }

  // Register a new vertex with an empty neighbor list
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  // Add an undirected edge between two existing vertices
  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }

  // Remove a specific edge
  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1]
      .filter(v => v !== vertex2);
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2]
      .filter(v => v !== vertex1);
  }

  // Remove a vertex and all edges connected to it
  removeVertex(vertex) {
    for (const neighbor of this.adjacencyList[vertex]) {
      this.adjacencyList[neighbor] = this.adjacencyList[neighbor]
        .filter(v => v !== vertex);
    }
    delete this.adjacencyList[vertex];
  }
}

// Usage
const g = new Graph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addVertex('D');

g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'D');

console.log(g.adjacencyList);
// { A: ['B','C'], B: ['A','D'], C: ['A','D'], D: ['B','C'] }

The pattern is straightforward: addVertex initializes a key in the object with an empty array, and addEdge mutates both arrays for an undirected edge. Because JavaScript arrays are dynamic, there is no need to pre-allocate space. Removal operations use filter to produce new arrays that exclude the target vertex — this is a common, safe pattern that avoids index-based splice errors.

When vertex identifiers are not strings (for example, numeric node IDs or complex objects), using a Map is preferable:

class GraphMap {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1, v2) {
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1);
  }
}

Space Complexity of the Adjacency List

The space complexity of an adjacency list is O(V + E), where V is the number of vertices and E is the number of edges. This breaks down as follows:

• The outer structure (the object or Map) holds V entries — one per vertex.
• Across all neighbor arrays combined, there are exactly E entries for a directed graph (one per directed edge) or 2E entries for an undirected graph (each edge appears in both endpoints' lists).
• Together, the total space is proportional to V + E.

This is the minimum possible space to represent a graph, because you cannot store fewer than E edge relationships without losing information. The key insight is that vertices with no or few connections do not waste space. A graph with 1,000 vertices and only 50 edges requires space proportional to 1,050 units — not 1,000,000 (which is what an adjacency matrix would require for those same 1,000 vertices).

This efficiency advantage becomes enormous for sparse graphs — graphs where the number of edges E is much smaller than V². Real-world networks (social graphs, web link graphs, road networks, dependency trees) are almost always sparse, which is why adjacency lists are the default choice in practice.

As the graph becomes denser — as E approaches V² — the space savings diminish. A complete graph (where every pair of vertices is connected) has E = V(V−1)/2, and the adjacency list stores O(V²) entries just like a matrix. At that point, the structural overhead of the list (pointer indirection, array objects) can actually make it less cache-friendly than a flat matrix.

Adjacency List vs. Adjacency Matrix

An adjacency matrix is a V×V grid where cell [u][v] is 1 (or the edge weight) if an edge exists between u and v, and 0 otherwise. It is the primary alternative to the adjacency list, and each representation has genuinely different strengths.

The most significant trade-off is edge existence queries. An adjacency matrix delivers O(1) lookup: matrix[u][v] is a direct array index. An adjacency list must scan vertex u's neighbor array to find v, which takes O(degree(u)) time — potentially O(V) in the worst case for a high-degree vertex. If your application constantly asks "does edge (u, v) exist?" across arbitrary pairs, the matrix's O(1) lookup is compelling.

Conversely, neighbor iteration strongly favors the adjacency list. To visit all neighbors of vertex u in a matrix, you must read every cell in row u — all V of them — even if u has only three actual connections. In an adjacency list, you visit exactly the neighbors that exist, taking O(degree(u)) time. For traversal-heavy algorithms like BFS and DFS on sparse graphs, this is a decisive advantage.

Here is a concrete illustration. Suppose you have a graph with V = 10,000 vertices (representing cities) and E = 30,000 edges (roads). The average degree is 30,000 × 2 / 10,000 = 6. Checking a single edge in the adjacency list takes at most 6 comparisons on average. Running BFS across the whole graph on the list takes O(10,000 + 30,000) = O(40,000) steps. The same BFS on a matrix requires scanning all 10,000 entries per row visited, resulting in O(V²) = O(100,000,000) steps — a factor of 2,500 slower.

Directed vs. Undirected Graphs in Adjacency Lists

The adjacency list representation handles both directed and undirected graphs cleanly, with just one rule change in addEdge.

In a directed graph (digraph), an edge from u to v is a one-way connection. Only u's neighbor list is updated:

// Directed addEdge — only source gets the entry
addDirectedEdge(source, destination) {
  this.adjacencyList[source].push(destination);
  // destination does NOT get source added
}

This means if you add the edge A → B, you can travel from A to B during traversal, but NOT from B to A (unless a separate edge B → A is also added). The total number of entries across all neighbor lists equals exactly E (the number of directed edges).

In an undirected graph, every edge is bidirectional. Both endpoints are updated:

// Undirected addEdge — both vertices get each other
addEdge(vertex1, vertex2) {
  this.adjacencyList[vertex1].push(vertex2);
  this.adjacencyList[vertex2].push(vertex1);
}

The total number of entries across all neighbor lists is 2E. This is expected behavior, not redundancy — it allows any traversal algorithm to correctly follow an undirected edge in either direction without special casing.

This distinction matters enormously for algorithms. In a directed graph, BFS from vertex A will only reach vertices reachable by following directed edges forward from A. In-degree and out-degree are separate concepts. Cycle detection, topological sort, and strongly connected component algorithms all depend on the directional nature of the edges being correctly encoded in the list.

A common practical extension is a weighted graph, where each neighbor entry stores not just the vertex identifier but also the edge weight. This is typically done by storing objects instead of raw vertex identifiers:

// Weighted adjacency list using objects
addWeightedEdge(v1, v2, weight) {
  this.adjacencyList[v1].push({ node: v2, weight });
  this.adjacencyList[v2].push({ node: v1, weight });
}

// Example
g.addWeightedEdge('A', 'B', 4);
// adjacencyList['A'] = [{ node: 'B', weight: 4 }]
// adjacencyList['B'] = [{ node: 'A', weight: 4 }]

This pattern is used directly in Dijkstra's algorithm and Prim's algorithm, where the weight determines which edge to explore next.

When to Choose an Adjacency List

The adjacency list is the right default choice for the vast majority of graph problems. The decision framework is nuanced, but the following guidelines cover most scenarios:

• Use an adjacency list when the graph is sparse. If E is much smaller than V², the list will use a fraction of the memory that a matrix would require. Social networks, file system dependency graphs, web crawl graphs, and transportation networks are almost always sparse.
• Use an adjacency list when you need to traverse neighbors frequently. BFS and DFS both run in O(V + E) time on an adjacency list, which is theoretically optimal. The same algorithms on a matrix run in O(V²), which is wasteful when edges are sparse.
• Use an adjacency matrix when constant-time edge queries are critical. If your algorithm repeatedly checks arbitrary (u, v) pairs for edge existence — as in certain dynamic programming formulations or dense relational computations — the O(1) matrix lookup justifies the O(V²) space cost.
• Use an adjacency matrix when the graph is dense. If nearly every pair of vertices is connected, the list offers no meaningful space saving and may add overhead from pointer indirection and array object management.
• Consider hybrid structures for special cases. Some applications use an adjacency list for traversal and a hash set per vertex for O(1) edge existence checks. This sacrifices some memory for the best of both worlds.

In competitive programming and production systems alike, the adjacency list's combination of O(V + E) space, O(1) edge addition, and O(degree) neighbor iteration makes it the go-to representation. Mastering its implementation and trade-offs prepares you directly for implementing BFS, DFS, Dijkstra's shortest path, Prim's minimum spanning tree, and virtually every other fundamental graph algorithm.