Loading learning content...
In the previous module, we explored the adjacency matrix—a dense, two-dimensional representation that excels when graphs are nearly complete and when we need constant-time edge lookups. But real-world graphs tell a different story: they're typically sparse, with only a fraction of all possible edges actually present.
Consider a social network with 1 billion users. Each user might have, on average, 500 friends. An adjacency matrix would require 10¹⁸ bits (over 100 petabytes) of storage, even though only about 250 billion actual connections exist. This astronomical waste demands a fundamentally different approach—one that stores only what exists, not the entire possibility space.
Welcome to the adjacency list representation: the workhorse of graph algorithms in practice.
By the end of this page, you will understand how adjacency lists work at a fundamental level. You'll see how storing a list of neighbors for each vertex dramatically reduces space requirements for sparse graphs, explore multiple implementation strategies (arrays, linked lists, hash sets), and develop intuition for why this representation dominates real-world graph applications.
The adjacency list representation embodies a simple yet powerful principle: for each vertex, maintain a collection of its neighbors. Instead of reserving space for every possible edge (as the matrix does), we allocate space only for edges that actually exist in the graph.
The fundamental insight:
For a graph G = (V, E) with |V| vertices and |E| edges, the total information we need to store is:
This neighbor-centric view naturally leads to a collection of lists—one list per vertex, containing that vertex's adjacent vertices.
1234567891011121314151617
Graph G = (V, E) where V = {0, 1, 2, 3, 4} Edges: (0,1), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4) Adjacency List Representation:┌─────────┬─────────────────────────────────┐│ Vertex │ Neighbors (Adjacent Vertices) │├─────────┼─────────────────────────────────┤│ 0 │ → [1, 4] ││ 1 │ → [0, 2, 3, 4] ││ 2 │ → [1, 3] ││ 3 │ → [1, 2, 4] ││ 4 │ → [0, 1, 3] │└─────────┴─────────────────────────────────┘ Total storage: 14 entries (7 edges × 2 for undirected)Matrix would need: 25 cells (5 × 5)Contrast with the adjacency matrix:
In a matrix, we ask: "Is there an edge from vertex i to vertex j?" and we store the answer for all possible (i, j) pairs.
In an adjacency list, we ask: "Which vertices does vertex i connect to?" and we store only those vertices that answer "yes."
This shift in perspective—from "all possible pairs" to "actual connections"—is what enables adjacency lists to dramatically outperform matrices for sparse graphs.
A graph is considered sparse when |E| is much smaller than |V|². Most real-world graphs fall into this category: road networks, social graphs, web links, dependency graphs, biological networks. For these, adjacency lists aren't just better—they're often the only feasible choice.
The "list" in adjacency list is somewhat misleading—the neighbor collection for each vertex can be implemented using various data structures, each with different tradeoffs. Let's examine the major options:
Option 1: Array of Dynamic Arrays (Most Common)
This is the standard implementation in most programming languages. We maintain an array where index i contains a dynamic array (like Python's list, Java's ArrayList, or C++'s vector) of neighbors for vertex i.
1234567891011121314151617181920212223242526272829303132333435363738394041424344
class GraphArrayBased: """ Adjacency list using Python lists (dynamic arrays). This is the most common implementation: - graph[i] contains a list of all vertices adjacent to vertex i - Works for both directed and undirected graphs """ def __init__(self, num_vertices: int): self.V = num_vertices # Create a list of empty lists, one per vertex self.adj = [[] for _ in range(num_vertices)] def add_edge(self, u: int, v: int, directed: bool = False): """Add edge from u to v (and v to u if undirected).""" self.adj[u].append(v) if not directed: self.adj[v].append(u) def neighbors(self, v: int) -> list[int]: """Return all neighbors of vertex v.""" return self.adj[v] def has_edge(self, u: int, v: int) -> bool: """Check if edge (u, v) exists.""" return v in self.adj[u] # O(degree) time! def degree(self, v: int) -> int: """Return the degree of vertex v.""" return len(self.adj[v]) # Example usageg = GraphArrayBased(5)g.add_edge(0, 1)g.add_edge(0, 4)g.add_edge(1, 2)g.add_edge(1, 3)g.add_edge(1, 4)g.add_edge(2, 3)g.add_edge(3, 4) print(f"Neighbors of vertex 1: {g.neighbors(1)}") # [0, 2, 3, 4]print(f"Degree of vertex 1: {g.degree(1)}") # 4Option 2: Array of Linked Lists (Classic Approach)
The traditional textbook approach uses actual linked lists for each vertex's neighbors. While pedagogically important, this is rarely used in practice due to poor cache performance.
123456789101112131415161718192021222324252627282930313233343536373839
class ListNode: """A node in the linked list of neighbors.""" def __init__(self, vertex: int): self.vertex = vertex self.next = None class GraphLinkedList: """ Adjacency list using linked lists. Classic textbook implementation. Pros: Efficient insertion at head Cons: Poor cache locality, more memory overhead """ def __init__(self, num_vertices: int): self.V = num_vertices # Array of linked list heads, one per vertex self.adj = [None] * num_vertices def add_edge(self, u: int, v: int, directed: bool = False): """Add edge by prepending to the linked list (O(1) insertion).""" # Add v to u's list new_node = ListNode(v) new_node.next = self.adj[u] self.adj[u] = new_node if not directed: # Add u to v's list new_node = ListNode(u) new_node.next = self.adj[v] self.adj[v] = new_node def neighbors(self, v: int): """Generator that yields all neighbors of vertex v.""" current = self.adj[v] while current: yield current.vertex current = current.nextOption 3: Array of Hash Sets (When Edge Lookup Matters)
If we frequently need to check whether a specific edge exists (an operation that's O(degree) with arrays), we can use hash sets for each vertex's neighbors. This trades some memory for O(1) average-case edge lookup.
1234567891011121314151617181920212223242526272829303132
class GraphHashSet: """ Adjacency list using hash sets. Best for algorithms that frequently check edge existence. Trades memory for O(1) edge lookup. """ def __init__(self, num_vertices: int): self.V = num_vertices # Array of sets, one per vertex self.adj = [set() for _ in range(num_vertices)] def add_edge(self, u: int, v: int, directed: bool = False): """Add edge to sets (O(1) average time).""" self.adj[u].add(v) if not directed: self.adj[v].add(u) def remove_edge(self, u: int, v: int, directed: bool = False): """Remove edge (O(1) average time).""" self.adj[u].discard(v) if not directed: self.adj[v].discard(u) def has_edge(self, u: int, v: int) -> bool: """Check edge existence in O(1) average time!""" return v in self.adj[u] def neighbors(self, v: int) -> set[int]: """Return set of neighbors (iteration order may vary).""" return self.adj[v]| Implementation | Edge Lookup | Edge Insert | Iteration | Memory Overhead | Best For |
|---|---|---|---|---|---|
| Array of Arrays | O(degree) | O(1) amortized | Cache-friendly | Low | General purpose, traversals |
| Array of Linked Lists | O(degree) | O(1) | Cache-unfriendly | Higher (pointers) | Theoretical, historical |
| Array of Hash Sets | O(1) average | O(1) average | Unordered | Higher (hash table) | Frequent edge queries |
The distinction between directed and undirected graphs has important implications for adjacency list storage:
Undirected Graphs: Symmetric Storage
In an undirected graph, an edge (u, v) means both "u is connected to v" AND "v is connected to u." We must store this relationship in both directions:
123456789
Undirected graph with edges: {A-B, B-C, A-C} Adjacency List:A → [B, C] // A connects to B and CB → [A, C] // B connects to A and C C → [A, B] // C connects to A and B Notice: Edge A-B appears in A's list (as B) AND in B's list (as A)Total entries: 6 (3 edges × 2)Directed Graphs: Asymmetric Storage
In a directed graph, an edge (u → v) means only "u connects to v"—there's no automatic reverse relationship. Each edge is stored exactly once:
12345678
Directed graph with edges: A→B, B→C, C→A Adjacency List (Outgoing Edges):A → [B] // A has an outgoing edge to BB → [C] // B has an outgoing edge to CC → [A] // C has an outgoing edge to A Total entries: 3 (exactly |E| entries for directed graphs)Reverse Adjacency Lists for Directed Graphs
Sometimes with directed graphs, we need to efficiently answer: "Which vertices have edges pointing TO this vertex?" (i.e., find predecessors, not successors). The standard adjacency list answers the question of outgoing edges efficiently, but incoming edges require a linear scan through all lists.
For algorithms that need both directions (like computing strongly connected components), we can maintain a reverse adjacency list alongside the regular one:
123456789101112131415161718192021222324252627282930313233343536373839404142434445
class DirectedGraphWithReverse: """ Maintains both forward (outgoing) and reverse (incoming) edges. Useful for algorithms that traverse edges in both directions. """ def __init__(self, num_vertices: int): self.V = num_vertices self.out_adj = [[] for _ in range(num_vertices)] # v → successors self.in_adj = [[] for _ in range(num_vertices)] # v → predecessors def add_edge(self, u: int, v: int): """Add directed edge u → v.""" self.out_adj[u].append(v) # u's outgoing neighbor self.in_adj[v].append(u) # v's incoming neighbor def successors(self, v: int) -> list[int]: """Return vertices that v points to.""" return self.out_adj[v] def predecessors(self, v: int) -> list[int]: """Return vertices that point to v.""" return self.in_adj[v] def out_degree(self, v: int) -> int: """Number of outgoing edges from v.""" return len(self.out_adj[v]) def in_degree(self, v: int) -> int: """Number of incoming edges to v.""" return len(self.in_adj[v]) # Example: Building dependency graph# Task 0 must complete before tasks 1 and 2g = DirectedGraphWithReverse(4)g.add_edge(0, 1) # 0 → 1g.add_edge(0, 2) # 0 → 2g.add_edge(1, 3) # 1 → 3g.add_edge(2, 3) # 2 → 3 # What depends on task 0?print(f"Tasks depending on 0: {g.successors(0)}") # [1, 2] # What must complete before task 3?print(f"Prerequisites of 3: {g.predecessors(3)}") # [1, 2]Maintaining both forward and reverse adjacency lists doubles the space requirement from O(V + E) to O(V + 2E), but enables O(1) access to both predecessors and successors. This is often worthwhile for algorithms like Kosaraju's SCC algorithm or topological sorting with special requirements.
Many graph algorithms require edge weights—numerical values associated with edges that might represent distances, costs, capacities, or probabilities. Adjacency lists accommodate weights naturally by storing (neighbor, weight) pairs instead of just neighbor vertices.
Common Approaches:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
# Approach 1: List of (neighbor, weight) tuplesclass WeightedGraphTuples: def __init__(self, num_vertices: int): self.V = num_vertices self.adj = [[] for _ in range(num_vertices)] def add_edge(self, u: int, v: int, weight: float, directed: bool = False): self.adj[u].append((v, weight)) if not directed: self.adj[v].append((u, weight)) def neighbors_with_weights(self, v: int): """Returns list of (neighbor, weight) tuples.""" return self.adj[v] # Approach 2: Dictionary of dictionaries (more Pythonic)class WeightedGraphDict: def __init__(self): self.adj = {} # {vertex: {neighbor: weight, ...}, ...} def add_vertex(self, v): if v not in self.adj: self.adj[v] = {} def add_edge(self, u, v, weight, directed=False): self.add_vertex(u) self.add_vertex(v) self.adj[u][v] = weight if not directed: self.adj[v][u] = weight def get_weight(self, u, v) -> float | None: """O(1) weight lookup for edge (u, v).""" return self.adj.get(u, {}).get(v) def neighbors(self, v): """Returns dict: {neighbor: weight, ...}""" return self.adj.get(v, {}) # Example: Road networkroads = WeightedGraphDict()roads.add_edge("NYC", "Boston", 215) # 215 milesroads.add_edge("NYC", "Philadelphia", 95)roads.add_edge("Boston", "Portland", 110) print(f"NYC neighbors: {roads.neighbors('NYC')}")# {'Boston': 215, 'Philadelphia': 95} print(f"NYC to Boston distance: {roads.get_weight('NYC', 'Boston')}")# 21512345678910111213141516171819202122232425262728293031323334353637383940414243444546
import java.util.*; // Edge class for weighted graphsclass Edge { int destination; double weight; Edge(int destination, double weight) { this.destination = destination; this.weight = weight; }} class WeightedGraph { private int V; private List<List<Edge>> adj; WeightedGraph(int vertices) { V = vertices; adj = new ArrayList<>(V); for (int i = 0; i < V; i++) { adj.add(new ArrayList<>()); } } void addEdge(int u, int v, double weight, boolean directed) { adj.get(u).add(new Edge(v, weight)); if (!directed) { adj.get(v).add(new Edge(u, weight)); } } List<Edge> getNeighbors(int v) { return adj.get(v); } // For Dijkstra's algorithm, we often need this interface: void relaxNeighbors(int u, double[] dist, PriorityQueue<int[]> pq) { for (Edge e : adj.get(u)) { if (dist[u] + e.weight < dist[e.destination]) { dist[e.destination] = dist[u] + e.weight; pq.offer(new int[]{e.destination, (int)dist[e.destination]}); } } }}Real-world edges often have multiple attributes: distance, time, cost, reliability, capacity. The adjacency list naturally extends to store any edge metadata by using objects, dictionaries, or named tuples instead of simple (neighbor, weight) pairs.
The standard adjacency list assumes vertices are numbered 0 through V-1, allowing direct array indexing. But what if vertices have other identifiers—strings, UUIDs, or arbitrary objects?
Solution: Vertex Mapping
We create a mapping between vertex identifiers and integer indices:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
class LabeledGraph: """ Graph supporting arbitrary vertex labels (strings, etc.) Internally maps labels to integer indices for efficiency. """ def __init__(self): self.label_to_index = {} # label → integer index self.index_to_label = [] # index → label self.adj = [] # adjacency list (by index) self.V = 0 def add_vertex(self, label) -> int: """Add a vertex with the given label, return its index.""" if label not in self.label_to_index: index = self.V self.label_to_index[label] = index self.index_to_label.append(label) self.adj.append([]) self.V += 1 return index return self.label_to_index[label] def add_edge(self, label_u, label_v, directed=False): """Add edge between labeled vertices.""" u = self.add_vertex(label_u) v = self.add_vertex(label_v) self.adj[u].append(v) if not directed: self.adj[v].append(u) def neighbors(self, label): """Return neighbor labels for the given vertex.""" idx = self.label_to_index.get(label) if idx is None: return [] return [self.index_to_label[i] for i in self.adj[idx]] # Example: Social network with usernamessocial = LabeledGraph()social.add_edge("alice", "bob")social.add_edge("alice", "carol")social.add_edge("bob", "dave") print(f"Alice's friends: {social.neighbors('alice')}") # ['bob', 'carol']print(f"Bob's friends: {social.neighbors('bob')}") # ['alice', 'dave']Alternative: Pure Dictionary-Based Graphs
For maximum flexibility—especially when vertices are added and removed dynamically—a pure dictionary approach avoids the index-mapping complexity entirely:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
from collections import defaultdict class DynamicGraph: """ Fully dynamic graph using dictionaries. No fixed vertex count, arbitrary vertex labels. Tradeoff: Slightly more memory for dict overhead, but maximum flexibility for dynamic graphs. """ def __init__(self, directed=False): self.adj = defaultdict(set) # auto-creates empty sets self.directed = directed def add_edge(self, u, v): """Add edge (creates vertices implicitly).""" self.adj[u].add(v) if not self.directed: self.adj[v].add(u) def remove_edge(self, u, v): """Remove edge if it exists.""" self.adj[u].discard(v) if not self.directed: self.adj[v].discard(u) def remove_vertex(self, v): """Remove vertex and all its edges.""" # Remove v from all neighbor lists for neighbor in list(self.adj[v]): self.adj[neighbor].discard(v) # Remove v's entry del self.adj[v] def has_edge(self, u, v) -> bool: return v in self.adj[u] def has_vertex(self, v) -> bool: return v in self.adj def vertices(self): return self.adj.keys() def neighbors(self, v): return self.adj[v] # Example: Building graph incrementallyg = DynamicGraph()g.add_edge("node_a", "node_b")g.add_edge("node_a", "node_c")g.add_edge("node_b", "node_c") print(f"All vertices: {list(g.vertices())}")# ['node_a', 'node_b', 'node_c'] g.remove_vertex("node_b")print(f"After removing node_b: {list(g.vertices())}")# ['node_a', 'node_c']In practice, graphs come from various sources: files, databases, APIs, or as part of coding problems. Mastering the skill of quickly constructing an adjacency list from raw input is essential. Here are the most common patterns:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123
from collections import defaultdict # ==================================================# Pattern 1: Edge List Input# Common in competitive programming# ================================================== def build_from_edge_list(n: int, edges: list[tuple[int, int]]) -> list[list[int]]: """ Input: number of vertices and list of (u, v) pairs Example input: n = 4 edges = [(0, 1), (0, 2), (1, 2), (2, 3)] """ adj = [[] for _ in range(n)] for u, v in edges: adj[u].append(v) adj[v].append(u) # remove for directed graph return adj # ==================================================# Pattern 2: Edge List with Number of Edges First# Very common format: first line has V E, then E edges# ================================================== def build_from_competitive_input(): """ Input format: 4 5 <- 4 vertices, 5 edges 0 1 <- edge 1 0 2 <- edge 2 1 2 <- edge 3 1 3 <- edge 4 2 3 <- edge 5 """ line = input().split() V, E = int(line[0]), int(line[1]) adj = [[] for _ in range(V)] for _ in range(E): edge = input().split() u, v = int(edge[0]), int(edge[1]) adj[u].append(v) adj[v].append(u) return adj # ==================================================# Pattern 3: Adjacency List Input (Direct Neighbors)# Each line lists neighbors of vertex i# ================================================== def build_from_neighbor_lists(neighbor_lists: list[list[int]]) -> list[list[int]]: """ Input: directly given neighbors for each vertex Example: neighbor_lists = [ [1, 2], # vertex 0 connects to 1, 2 [0, 2, 3], # vertex 1 connects to 0, 2, 3 [0, 1, 3], # vertex 2 connects to 0, 1, 3 [1, 2] # vertex 3 connects to 1, 2 ] """ # Input is already in adjacency list format! return [list(neighbors) for neighbors in neighbor_lists] # ==================================================# Pattern 4: Matrix to Adjacency List Conversion# Converting from matrix representation# ================================================== def matrix_to_adj_list(matrix: list[list[int]]) -> list[list[int]]: """ Convert adjacency matrix to adjacency list. Essential skill for choosing representation at runtime. """ n = len(matrix) adj = [[] for _ in range(n)] for i in range(n): for j in range(n): if matrix[i][j] != 0: # edge exists adj[i].append(j) return adj # ==================================================# Pattern 5: Grid to Graph Conversion# 2D grids are implicit graphs# ================================================== def grid_to_adj_list(grid: list[list[str]], blocked: str = '#') -> dict[tuple[int,int], list[tuple[int,int]]]: """ Convert a 2D grid to an adjacency list. Each cell (r, c) becomes a vertex. 4-directional neighbors become edges. Example grid: . . # . . . . . # . . . """ rows, cols = len(grid), len(grid[0]) adj = defaultdict(list) directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right for r in range(rows): for c in range(cols): if grid[r][c] != blocked: for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != blocked: adj[(r, c)].append((nr, nc)) return adjBefore writing any graph algorithm, always clarify the input format. Many bugs come from misinterpreting whether vertices are 0-indexed or 1-indexed, whether edges are directed or undirected, or whether the input is an edge list vs. adjacency list. Read the problem statement carefully!
We've established the foundation of adjacency list representation—the primary graph storage method used in practice. Let's consolidate the key insights:
What's Next:
With the structural understanding in place, the next page analyzes the space complexity of adjacency lists—understanding precisely why O(V + E) space makes them the choice for sparse graphs, and exploring the constants hidden in that notation.
You now understand how adjacency lists store graphs by maintaining a collection of neighbors for each vertex. This neighbor-centric view forms the basis for nearly all practical graph implementations and algorithms.