Historical Context & Motivation
Graphs are everywhere in the real world—social networks, road maps, the internet, even the connections between characters in your favorite TV show. The challenge that computer scientists have wrestled with for decades is: how do you store all those connections inside a computer's memory so you can work with them efficiently? The answer depends on the problem you're solving, but one of the most popular and flexible approaches is the adjacency list.
Map and List interfaces, giving developers a clean way to implement adjacency lists using Map<Integer, List<Integer>>.The central question this lesson addresses is straightforward: given a graph with numbered nodes and edges between them, how can you represent it in Java so that adding connections, looking up neighbors, and traversing the graph are all fast and memory-efficient? The Map<Integer, List<Integer>> adjacency list is the modern Java answer to that question.
Core Principles & Definitions
Before diving into code, let's nail down the key vocabulary. A graph is a data structure made up of vertices (also called nodes) and edges (connections between vertices). When you write Map<Integer, List<Integer>>, the keys of the map are vertex IDs and each key maps to a list of neighbor vertex IDs. That list is the adjacency list for that vertex.
Vertex (Node)
key in the map.Edge
Adjacency List
List<Integer> value in the map.Directed vs. Undirected
Sparse vs. Dense
Visual Explanation — From Drawing to Data Structure
The diagram below shows an undirected graph with five vertices (labeled 0 through 4) and six edges. On the left you see the graph as you'd draw it on paper; on the right, the same graph is stored as a Map<Integer, List<Integer>>. Notice how each vertex's list contains only the vertices it's directly connected to.
Map<Integer, List<Integer>>. Each key maps to a list of its directly connected neighbors.Look at vertex 2 in the diagram. It connects to vertices 0, 3, and 4, so the map entry for key 2 stores [0, 3, 4]. Because this is an undirected graph, the edge between 2 and 0 also means vertex 0's list includes 2. Every edge shows up twice in the map—once for each endpoint.
How It Works — Building the Map in Java
In Java, we typically use a HashMap<Integer, List<Integer>> to implement the adjacency list. The three core operations are: adding a vertex, adding an edge, and querying neighbors. Let's look at how each one works and what it costs in terms of speed.
Adding a Vertex
To add vertex v, call graph.putIfAbsent(v, new ArrayList<>()). This inserts a new key in the map with an empty neighbor list if the vertex doesn't already exist. Because HashMap.put runs in amortized O(1) time, adding a vertex is essentially instant.
Adding an Edge (Undirected)
To add an undirected edge between vertices u and v, you add v to the list of u and also add u to the list of v. In code: graph.get(u).add(v); graph.get(v).add(u); Each ArrayList.add runs in amortized O(1), so adding an edge is also O(1).
Querying Neighbors
To find all neighbors of vertex v, call graph.get(v). This returns the entire neighbor list in O(1) time. Iterating through all neighbors takes O(degree) time, where degree is the number of edges connected to that vertex.
Common Code Patterns & Directed Graphs
Now that you understand the mechanism, let's look at how a directed graph differs and examine the full code pattern side by side. In a directed graph, an edge from u to v does NOT imply an edge from v back to u. Think of a one-way street: just because you can drive from A to B doesn't mean you can drive from B to A.
computeIfAbsent so you don't have to add vertices before adding edges: graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v); This creates the list automatically if vertex u doesn't exist yet. It's a one-liner that handles vertex creation and edge addition at the same time.Worked Example — Building a Friend Network
Imagine you're building a simple friend network for a social app. You have four users with IDs 1, 2, 3, and 4. The friendships are: 1–2, 1–3, 2–4, and 3–4. Let's build the adjacency list step by step in Java.
Map<Integer, List<Integer>> graph = new HashMap<>(); At this point, the map is empty—no vertices, no edges.graph = {}for (int v : new int[]{1,2,3,4}) graph.put(v, new ArrayList<>()); Now every vertex has a key in the map, but no one has friends yet.{1=[], 2=[], 3=[], 4=[]}graph.get(1).add(2); graph.get(2).add(1);{1=[2], 2=[1], 3=[], 4=[]}{1=[2,3], 2=[1,4], 3=[1,4], 4=[2,3]}graph.get(3) to retrieve the neighbor list. This returns [1, 4], meaning user 3 is friends with users 1 and 4. The lookup is O(1) because HashMap provides constant-time key access.Adjacency List vs. Adjacency Matrix
The adjacency list isn't the only way to store a graph. The other classic representation is the adjacency matrix: a 2D array where matrix[i][j] = 1 if there's an edge from vertex i to vertex j. Understanding the trade-offs between these two representations is essential for choosing the right tool.
| Feature | Adjacency List (Map) | Adjacency Matrix (2D Array) |
|---|---|---|
| Space | O(V + E) — stores only actual edges | O(V²) — allocates space for all possible edges |
| Add Edge | O(1) amortized | O(1) |
| Check if Edge Exists | O(degree) — must scan neighbor list | O(1) — direct array lookup |
| Get All Neighbors | O(degree) — iterate the list | O(V) — must scan entire row |
| Best For | Sparse graphs (few edges) | Dense graphs (many edges) |
Connecting to Advanced Topics
The Map<Integer, List<Integer>> pattern you just learned is the foundation for virtually every graph algorithm you'll encounter. Once you can build the adjacency list, you can run Breadth-First Search (BFS), Depth-First Search (DFS), shortest-path algorithms, and more. The table below previews how the basic pattern extends.
| This Lesson (Intro) | Advanced Extension |
|---|---|
Map<Integer, List<Integer>> | Map<Integer, List<int[]>> — pairs store (neighbor, weight) for weighted graphs |
| Unweighted edges | Weighted edges for Dijkstra's algorithm, Prim's MST |
| Integer vertex labels | Map<String, List<String>> — generic vertex types (names, URLs) |
| Build graph, query neighbors | BFS, DFS, topological sort, cycle detection |
The jump from an unweighted adjacency list to a weighted one is small. Instead of storing just an integer neighbor, you store a pair: the neighbor ID and the edge weight. Everything else—the map structure, the add-edge pattern, the neighbor query—stays the same. Mastering the basic pattern now makes these advanced topics much easier to learn.
Practice Problems
graph.get(2) return?int degree(Map<Integer, List<Integer>> graph, int v) that returns the degree (number of edges) of vertex v. Handle the case where v is not in the graph by returning −1.computeIfAbsent, then write code that prints all classrooms reachable directly from classroom 2.Lesson Summary
A graph is a data structure composed of vertices and edges. The adjacency list representation uses a Map<Integer, List<Integer>> where each key is a vertex ID and its value is the list of neighboring vertices. Adding a vertex and adding an edge both run in O(1) amortized time, and the total space is O(V + E), making it ideal for sparse graphs.
For undirected graphs, every edge is stored twice (once per endpoint). For directed graphs, each edge is stored once—only in the source vertex's list. The computeIfAbsent pattern simplifies building graphs in Java. Compared to the adjacency matrix (O(V²) space), the adjacency list uses far less memory when edges are few. This foundational structure powers algorithms like BFS, DFS, and Dijkstra's shortest path.