List of Neighbors for Each… — Graph Representation —… | OneNoughtOne

0/97

Data Structures & AlgorithmsGraph Representation — Adjacency List

Graph Representation — Adjacency List

LevelIntermediate

Duration60 mins

TopicGraph Representation — Adjacency List

1 / 4

List of Neighbors for Each Vertex

The Neighbor-Centric View of Graphs

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.

What You Will Learn

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 Core Idea: Store Only What Exists

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: Which vertices exist (trivially, all of them: 0 through |V|-1) For each vertex, which other vertices it connects to (its neighbors) This neighbor-centric view naturally leads to a collection of lists—one list per vertex, containing that vertex's adjacent vertices.

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.

The Sparsity Advantage

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.

Implementation Strategies: Arrays, Lists, and Beyond

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 usage
g = 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)}")         # 4

Option 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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.next

Option 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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]

Comparison of Adjacency List Implementations
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

Directed vs Undirected: How Storage Differs

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:

Undirected graph with edges: {A-B, B-C, A-C}
 
Adjacency List:
A → [B, C]    // A connects to B and C
B → [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 \to v) means only "u connects to v"—there's no automatic reverse relationship. Each edge is stored exactly once:

Directed graph with edges: A→B, B→C, C→A
 
Adjacency List (Outgoing Edges):
A → [B]       // A has an outgoing edge to B
B → [C]       // B has an outgoing edge to C
C → [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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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 2
g = DirectedGraphWithReverse(4)
g.add_edge(0, 1)  # 0 → 1
g.add_edge(0, 2)  # 0 → 2
g.add_edge(1, 3)  # 1 → 3
g.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]

Space Tradeoff

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.

Representing Weighted Graphs with Adjacency Lists

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# Approach 1: List of (neighbor, weight) tuples
class 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 network
roads = WeightedGraphDict()
roads.add_edge("NYC", "Boston", 215)     # 215 miles
roads.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')}")
# 215

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;
 
// Edge class for weighted graphs
class 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]});
            }
        }
    }
}

Multiple Edge Attributes

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 Vertex Index Assumption and Alternatives

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 usernames
social = 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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 incrementally
g = 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']

Building Graphs from Common Input Formats

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
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 adj

Pro Tip: Recognize the Pattern Early

Before 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!

Summary: The Adjacency List Foundation

We've established the foundation of adjacency list representation—the primary graph storage method used in practice. Let's consolidate the key insights:

Key Takeaways

•Store only what exists: Adjacency lists allocate space for actual edges, not all possible edges. This is fundamentally more efficient for sparse graphs.
•Implementation flexibility: The 'list' can be dynamic arrays, linked lists, hash sets, or any collection—choose based on your algorithm's needs.
•Undirected edges appear twice: In undirected graphs, each edge creates two entries (one in each endpoint's list).
•Directed graphs can use reverse lists: When you need both predecessor and successor queries, maintain both forward and reverse adjacency lists.
•Weights integrate naturally: Store (neighbor, weight) pairs or use dictionaries/objects to attach arbitrary edge metadata.
•Vertex mapping enables labels: Map string/object labels to integer indices when needed, or use pure dictionary representations for maximum flexibility.

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.

Page Complete

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.

Data Structures & AlgorithmsGraph Representation — Adjacency List

Graph Representation — Adjacency List

LevelIntermediate

Duration60 mins

TopicGraph Representation — Adjacency List

1 / 4

List of Neighbors for Each Vertex

The Neighbor-Centric View of Graphs

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.

What You Will Learn

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 Core Idea: Store Only What Exists

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: Which vertices exist (trivially, all of them: 0 through |V|-1) For each vertex, which other vertices it connects to (its neighbors) This neighbor-centric view naturally leads to a collection of lists—one list per vertex, containing that vertex's adjacent vertices.

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.

The Sparsity Advantage

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.

Implementation Strategies: Arrays, Lists, and Beyond

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 usage
g = 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)}")         # 4

Option 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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.next

Option 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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]

Comparison of Adjacency List Implementations
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

Directed vs Undirected: How Storage Differs

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:

Undirected graph with edges: {A-B, B-C, A-C}
 
Adjacency List:
A → [B, C]    // A connects to B and C
B → [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 \to v) means only "u connects to v"—there's no automatic reverse relationship. Each edge is stored exactly once:

Directed graph with edges: A→B, B→C, C→A
 
Adjacency List (Outgoing Edges):
A → [B]       // A has an outgoing edge to B
B → [C]       // B has an outgoing edge to C
C → [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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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 2
g = DirectedGraphWithReverse(4)
g.add_edge(0, 1)  # 0 → 1
g.add_edge(0, 2)  # 0 → 2
g.add_edge(1, 3)  # 1 → 3
g.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]

Space Tradeoff

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.

Representing Weighted Graphs with Adjacency Lists

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# Approach 1: List of (neighbor, weight) tuples
class 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 network
roads = WeightedGraphDict()
roads.add_edge("NYC", "Boston", 215)     # 215 miles
roads.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')}")
# 215

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;
 
// Edge class for weighted graphs
class 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]});
            }
        }
    }
}

Multiple Edge Attributes

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 Vertex Index Assumption and Alternatives

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 usernames
social = 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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 incrementally
g = 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']

Building Graphs from Common Input Formats

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
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 adj

Pro Tip: Recognize the Pattern Early

Before 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!

Summary: The Adjacency List Foundation

We've established the foundation of adjacency list representation—the primary graph storage method used in practice. Let's consolidate the key insights:

Key Takeaways

•Store only what exists: Adjacency lists allocate space for actual edges, not all possible edges. This is fundamentally more efficient for sparse graphs.
•Implementation flexibility: The 'list' can be dynamic arrays, linked lists, hash sets, or any collection—choose based on your algorithm's needs.
•Undirected edges appear twice: In undirected graphs, each edge creates two entries (one in each endpoint's list).
•Directed graphs can use reverse lists: When you need both predecessor and successor queries, maintain both forward and reverse adjacency lists.
•Weights integrate naturally: Store (neighbor, weight) pairs or use dictionaries/objects to attach arbitrary edge metadata.
•Vertex mapping enables labels: Map string/object labels to integer indices when needed, or use pure dictionary representations for maximum flexibility.

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.

Page Complete

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.

List of Neighbors for Each Vertex

The Neighbor-Centric View of Graphs

The Core Idea: Store Only What Exists

Implementation Strategies: Arrays, Lists, and Beyond

Directed vs Undirected: How Storage Differs

Representing Weighted Graphs with Adjacency Lists

The Vertex Index Assumption and Alternatives

Building Graphs from Common Input Formats

Summary: The Adjacency List Foundation

There’s more to understand.

List of Neighbors for Each Vertex

The Neighbor-Centric View of Graphs

The Core Idea: Store Only What Exists

Implementation Strategies: Arrays, Lists, and Beyond

Directed vs Undirected: How Storage Differs

Representing Weighted Graphs with Adjacency Lists

The Vertex Index Assumption and Alternatives

Building Graphs from Common Input Formats

Summary: The Adjacency List Foundation

There’s more to understand.