Graph Adjacency List Explained

What Is an Adjacency List?

An adjacency list is a graph representation that stores the neighbors of each vertex. Instead of allocating space for every possible pair of vertices, an adjacency list records only the edges that actually exist.

This representation is particularly useful for sparse graphs, where the number of edges is much smaller than the maximum possible number of edges.

Basic Example

Consider a graph containing four vertices with the following connections:

A --- B
|     |
C --- D

Its adjacency list can be written as:

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

Each vertex has a list containing the vertices directly connected to it.

Why Use an Adjacency List?

A graph with V vertices can potentially contain many more possible vertex-to-vertex relationships than the graph actually uses. An adjacency matrix allocates space for all possible pairs, while an adjacency list stores the existing relationships.

For a graph with V vertices and E edges, an adjacency list typically requires O(V + E) space.

Adjacency List for an Undirected Graph

In an undirected graph, an edge connects two vertices in both directions. Therefore, each edge is normally stored in the adjacency list of both vertices.

A --- B
|
C

The adjacency list is:

A: [B, C]
B: [A]
C: [A]

The edge A-B appears under both A and B because the connection can be traversed in either direction.

Adjacency List for a Directed Graph

In a directed graph, edges have a source and destination. The destination is normally stored in the source vertex's adjacency list.

A ---> B
B ---> C
C ---> A

The adjacency list is:

A: [B]
B: [C]
C: [A]

Unlike an undirected graph, A → B does not automatically create B → A.

Creating an Adjacency List in JavaScript

JavaScript objects and Map objects can both be used to implement adjacency lists. A Map is often convenient when vertex identifiers are not limited to simple object property keys.

const graph = new Map();

graph.set('A', ['B', 'C']);
graph.set('B', ['A', 'D']);
graph.set('C', ['A']);
graph.set('D', ['B']);

console.log(graph.get('A'));
console.log(graph.get('B'));

Building an Adjacency List Dynamically

Instead of manually creating every neighbor list, an edge function can construct the graph as edges are added.

const graph = {};

function addEdge(graph, a, b) {
  if (!graph[a]) {
    graph[a] = [];
  }

  if (!graph[b]) {
    graph[b] = [];
  }

  graph[a].push(b);
  graph[b].push(a);
}

addEdge(graph, 'A', 'B');
addEdge(graph, 'A', 'C');
addEdge(graph, 'B', 'D');

console.log(graph);

This implementation creates an undirected graph because each edge is stored in both directions.

Adding a Directed Edge

For a directed graph, only the source vertex needs to receive the destination in its adjacency list.

const graph = {};

function addDirectedEdge(graph, from, to) {
  if (!graph[from]) {
    graph[from] = [];
  }

  if (!graph[to]) {
    graph[to] = [];
  }

  graph[from].push(to);
}

addDirectedEdge(graph, 'A', 'B');
addDirectedEdge(graph, 'B', 'C');

console.log(graph);

Weighted Adjacency List

An adjacency list can also represent a weighted graph. Instead of storing only the neighboring vertex, each entry can contain the destination and edge weight.

const graph = {
  A: [
    { node: 'B', weight: 4 },
    { node: 'C', weight: 10 }
  ],
  B: [
    { node: 'A', weight: 4 },
    { node: 'C', weight: 3 }
  ],
  C: [
    { node: 'A', weight: 10 },
    { node: 'B', weight: 3 }
  ]
};

This representation preserves both pieces of information required by a weighted graph: the neighboring vertex and the cost of reaching it.

Adding Weighted Edges

For an undirected weighted graph, the same weighted connection is normally stored for both vertices.

const graph = {};

function addWeightedEdge(graph, a, b, weight) {
  if (!graph[a]) {
    graph[a] = [];
  }

  if (!graph[b]) {
    graph[b] = [];
  }

  graph[a].push({ node: b, weight });
  graph[b].push({ node: a, weight });
}

addWeightedEdge(graph, 'A', 'B', 5);
addWeightedEdge(graph, 'B', 'C', 3);

console.log(graph);

Finding Neighbors

One of the main advantages of an adjacency list is that a vertex's neighbors can be accessed directly.

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A'],
  D: ['B']
};

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

If vertex A has degree d, iterating through its neighbors takes O(d) time.

Checking Whether an Edge Exists

To check whether an edge exists using a basic adjacency list, you normally search the neighbor list of the source vertex.

function hasEdge(graph, from, to) {
  return graph[from]?.includes(to) ?? false;
}

const graph = {
  A: ['B', 'C'],
  B: ['A'],
  C: ['A']
};

console.log(hasEdge(graph, 'A', 'B')); // true
console.log(hasEdge(graph, 'A', 'D')); // false

With a normal array-based neighbor list, the lookup is generally O(degree) rather than O(1). A different structure, such as a Set, can provide faster average membership checks.

BFS with an Adjacency List

Breadth-First Search is particularly natural with adjacency lists because the algorithm needs to visit the neighbors of each vertex.

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];

  visited.add(start);

  while (queue.length > 0) {
    const current = queue.shift();

    console.log(current);

    for (const neighbor of graph[current]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A'],
  D: ['B']
};

bfs(graph, 'A');

With a suitable queue implementation, BFS using an adjacency list runs in O(V + E) time because each vertex and edge is processed a bounded number of times.

DFS with an Adjacency List

Depth-First Search also works efficiently with adjacency lists.

function dfs(graph, vertex, visited = new Set()) {
  if (visited.has(vertex)) {
    return;
  }

  visited.add(vertex);
  console.log(vertex);

  for (const neighbor of graph[vertex]) {
    dfs(graph, neighbor, visited);
  }
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A'],
  D: ['B']
};

dfs(graph, 'A');

DFS also takes O(V + E) time for an adjacency-list representation when traversing the reachable portion of the graph.

Space Complexity

An adjacency list stores the vertices and the edges that actually exist. Therefore, its typical space complexity is:

Space: O(V + E)

For an undirected graph, each edge is commonly stored twice, once for each endpoint. This changes the constant amount of storage but not the asymptotic complexity.

Time Complexity of Common Operations

Adjacency List vs Adjacency Matrix

Both representations are widely used, but they make different trade-offs.

Using Sets for Neighbor Lists

If an application frequently checks whether a particular neighbor exists, a Set can be used instead of an array for each adjacency list.

const graph = new Map();

graph.set('A', new Set(['B', 'C']));
graph.set('B', new Set(['A']));
graph.set('C', new Set(['A']));

console.log(graph.get('A').has('B')); // true
console.log(graph.get('A').has('D')); // false

This can provide average-case constant-time membership checks, while arrays are often simpler when traversal order and direct iteration are the primary concerns.

Representing Weighted Graphs with Objects

For algorithms such as Dijkstra's algorithm, each adjacency-list entry commonly stores both a neighbor and its edge weight.

const graph = {
  A: [
    { node: 'B', weight: 2 },
    { node: 'C', weight: 7 }
  ],
  B: [
    { node: 'C', weight: 3 }
  ],
  C: []
};

for (const edge of graph.A) {
  console.log(
    'Neighbor:',
    edge.node,
    'Weight:',
    edge.weight
  );
}

Practical Example: Network Connections

Imagine a network where computers are vertices and network connections are edges. An adjacency list can store only the connections that actually exist.

const network = {
  ServerA: ['ServerB', 'ServerC'],
  ServerB: ['ServerA', 'ServerD'],
  ServerC: ['ServerA'],
  ServerD: ['ServerB']
};

If ServerA has connections to ServerB and ServerC, only those relationships need to be stored under ServerA. There is no need to allocate entries for every other possible server pair.

When Should You Use an Adjacency List?

• The graph is sparse.
• You frequently need to iterate through the neighbors of a vertex.
• The graph contains a large number of vertices but relatively few edges.
• You are implementing BFS, DFS, connected components, or many graph algorithms.
• Memory efficiency is important.
• You need to represent weighted edges without allocating space for nonexistent edges.

Common Mistakes

• Forgetting to add both directions when representing an undirected edge.
• Accidentally adding reverse edges to a directed graph.
• Assuming an array-based adjacency list provides O(1) edge lookup.
• Forgetting to initialize a vertex's neighbor list before adding edges.
• Ignoring isolated vertices that have no neighbors.
• Storing weighted edges without preserving their associated weights.
• Using an adjacency matrix when the graph is extremely sparse and memory is limited.

Key Takeaways

• An adjacency list stores the neighbors of each vertex.
• It normally requires O(V + E) space.
• Undirected edges are generally stored in both vertices' lists.
• Directed edges are normally stored from source to destination.
• Weighted graphs can store objects containing both a neighbor and its weight.
• BFS and DFS can run in O(V + E) time using an adjacency list.
• Finding neighbors is efficient because only actual connections are stored.
• Basic array-based edge lookup takes O(degree) time rather than O(1).
• Adjacency lists are especially useful for sparse graphs and traversal-based algorithms.