Graph Representation

Adjacency List

What is an Adjacency List?

An adjacency list represents a graph as a collection of per-vertex neighbor lists: one entry per vertex, holding only the vertices it's actually connected to. Instead of a full V×V grid of mostly zeros, each vertex stores exactly as many entries as it has edges, nothing more.

How Does It Work?

Adding an edge (u, v) appends v to u's list. For an undirected graph, u is also appended to v's list, since the edge goes both ways; for a directed graph, only u's list gets the new entry. Checking whether an edge exists means scanning through one vertex's list looking for the target, proportional to that vertex's degree (its number of neighbors), not the whole graph.

This is the mirror image of an adjacency matrix's tradeoffs. A matrix spends O(V²) space no matter what, in exchange for O(1) edge-existence checks. A list spends space proportional to the actual number of edges, O(V + E), but checking a specific edge now costs O(degree) instead of O(1). For the vast majority of real-world graphs, which are sparse (E is much smaller than V²), that tradeoff strongly favors the list.

The same triangle graph: every vertex's list holds only its actual neighbors
ABC
A→
BC
B→
AC
C→
AB

Building the List

  1. Create an empty list (or map) for every vertex
  2. For every edge (u, v) with weight w: append (v, w) to u's list
  3. If the graph is undirected, also append (u, w) to v's list, since the same edge is recorded from both directions
  4. To check if an edge exists between two vertices, scan the source vertex's list for the target

Complexity

  • Space Complexity: O(V + E), proportional to the actual number of vertices and edges, not V².
  • Check if edge (u, v) exists: O(degree(u)), scan u's list, which is only as long as u's actual neighbor count.
  • Iterate over a vertex's neighbors: O(degree(u)), the list already holds exactly the relevant entries.
  • Add an edge: O(1), appending to a list.

Time Complexity Analysis

Adjacency lists are the default choice for most graph algorithms: BFS, DFS, Dijkstra's algorithm, and topological sort all need to repeatedly ask "what are this vertex's neighbors?", which a list answers by directly returning exactly the relevant entries, without wasting time scanning past vertices that aren't connected at all.

Daily DSA Challenge by Scale Engineer

See how a graph's edges become per-vertex neighbor lists

Add vertices, then connect them with edges

Graph

Add a vertex to begin

Adjacency List

Add vertices to see the list
Neighbor entryMost recently added edgeSelected (click any entry)

Test Your Knowledge before moving forward!

Adjacency List Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Adjacency List Implementation

class GraphList {
  constructor() {
    this.list = new Map(); // vertex -> [{ to, weight }, ...]
  }

  addVertex(v) {
    if (!this.list.has(v)) this.list.set(v, []);
  }

  addEdge(from, to, weight = 1, directed = false) {
    this.list.get(from).push({ to, weight });
    if (!directed) this.list.get(to).push({ to: from, weight }); // mirror the edge both ways
  }

  hasEdge(from, to) {
    return this.list.get(from).some((entry) => entry.to === to); // O(degree(from))
  }

  neighbors(v) {
    return this.list.get(v).map((entry) => entry.to); // exactly the relevant entries
  }
}

// Usage example
const g = new GraphList();
["A", "B", "C", "D"].forEach((v) => g.addVertex(v));
g.addEdge("A", "B");
g.addEdge("A", "C");
g.hasEdge("A", "B"); // true
g.neighbors("A");    // ["B", "C"]

Done With the Learning

Mark Adjacency List as done and view it on your dashboard

Explore Other Topics

Adjacency Matrix

Binary Search

Structure & Properties

Heap Sort