Graph Representation — Represent graphs using adjacency lists (Map<Integer, List<Integer>> style) (intro) - Java

SECTION 1

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.

1736 • Euler & the Seven Bridges

Leonhard Euler solved the famous Königsberg bridge problem, founding graph theory as a branch of mathematics. He represented land masses as nodes and bridges as edges.

1956 • Dijkstra's Shortest Path

Edsger Dijkstra designed his famous shortest-path algorithm, which works most efficiently when graphs are stored as adjacency lists rather than full matrices.

1960s • Adjacency Lists Formalized

As computers gained more memory, researchers formalized the adjacency list representation using linked lists. This became the go-to structure for sparse graphs in textbooks.

1998 • Java Collections Framework

Java 2 introduced the Collections Framework with 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.

SECTION 2

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)

A single point in the graph, identified by an integer. In Java, it becomes a key in the map.

Edge

A connection between two vertices. Represented by adding each vertex to the other's neighbor list (for undirected graphs).

Adjacency List

The list of all neighbors for a single vertex. Stored as a List<Integer> value in the map.

Directed vs. Undirected

In a directed graph, edge A→B doesn't imply B→A. In an undirected graph, every edge goes both ways.

Sparse vs. Dense

A sparse graph has far fewer edges than the maximum possible. Adjacency lists shine for sparse graphs because they only store actual edges.

✦

KEY TAKEAWAY

Think of an adjacency list like a phone contacts app. Each person (vertex) has their own contact list (neighbor list). You don't store a massive table of every possible pair of people—you only store the people each person actually knows. That's why adjacency lists are memory-efficient for graphs with relatively few edges.

SECTION 3

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.

Left: a visual drawing of the undirected graph with 5 vertices and 6 edges. Right: the same graph stored as a 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.

SECTION 4

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.

SPACE COMPLEXITY

Space = O(V + E)

Where V is the number of vertices and E is the number of edges. The map stores V keys, and across all lists, there are 2E entries total (each edge counted once per endpoint in an undirected graph).

TIME — ADD EDGE

addEdge(u, v) → O(1) amortized

HashMap lookup is O(1) on average, and ArrayList append is O(1) amortized. Together, adding an edge is constant time.

SECTION 5

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.

Side-by-side comparison of undirected vs. directed graph code and resulting adjacency lists. The only difference is whether you add the reverse edge.

💡

Helper Method Pattern

A common Java pattern is to use 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.

SECTION 6

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.

Build an Adjacency List for an Undirected Friend Network

1
Step 1 — Declare the Map

Create an empty map to hold the graph: Map<Integer, List<Integer>> graph = new HashMap<>(); At this point, the map is empty—no vertices, no edges.

graph = {}
2
Step 2 — Add All Vertices

For each user ID, insert a key with an empty list: 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=[]}
3
Step 3 — Add Edge 1–2

Since this is an undirected friendship, add in both directions: graph.get(1).add(2); graph.get(2).add(1);

{1=[2], 2=[1], 3=[], 4=[]}
4
Step 4 — Add Remaining Edges (1–3, 2–4, 3–4)

Repeat the same pattern for each edge. Edge 1–3: add 3 to 1's list and 1 to 3's list. Edge 2–4: add 4 to 2's list and 2 to 4's list. Edge 3–4: add 4 to 3's list and 3 to 4's list.

{1=[2,3], 2=[1,4], 3=[1,4], 4=[2,3]}
5
Step 5 — Query: Who are user 3's friends?

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

graph.get(3) → [1, 4]

SECTION 7

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)

Head-to-head comparison of the two main graph representations

🔀

WHEN TO USE WHICH?

If your graph is like a highway map—many cities but relatively few direct roads between them—use an adjacency list. If your graph is like a classroom where nearly everyone knows everyone else, an adjacency matrix may be simpler. Most real-world graphs (social networks, the web, road networks) are sparse, which is why adjacency lists are the default choice.

SECTION 8

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

From this lesson's basics to future graph algorithms

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.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

In an undirected graph with 4 vertices and 3 edges, how many total entries (across all lists combined) will the adjacency list contain? Explain your reasoning.

Show answer

The adjacency list will contain 6 total entries. In an undirected graph, every edge appears twice—once in each endpoint's list. With 3 edges, that gives 3 × 2 = 6 entries total. For example, if the edges are 0–1, 1–2, 2–3, then: 0→[1], 1→[0,2], 2→[1,3], 3→[2], which has 1 + 2 + 2 + 1 = 6 entries.

Question 2: BASIC CALCULATION

Given edges: 0–1, 0–2, 1–2, 2–3 in an undirected graph, write out the complete adjacency list as a map. What does graph.get(2) return?

Show answer

The adjacency list is: {0=[1,2], 1=[0,2], 2=[0,1,3], 3=[2]}. Calling graph.get(2) returns [0, 1, 3] because vertex 2 is connected to vertices 0, 1, and 3. The degree of vertex 2 is 3, meaning it has three neighbors.

Question 3: INTERMEDIATE

Write a Java method 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.

Show answer

The method should check if the vertex exists in the map, then return the size of its neighbor list:

int degree(Map<Integer, List<Integer>> graph, int v) { if (!graph.containsKey(v)) return -1; return graph.get(v).size(); }

The containsKey check runs in O(1) for a HashMap, and size() on an ArrayList is also O(1), so the entire method is constant time. Returning −1 signals that the vertex doesn't exist.

Question 4: APPLIED

A school has 5 classrooms (labeled 1–5) connected by hallways: 1–2, 1–3, 2–3, 2–4, 4–5. Build the adjacency list in Java using computeIfAbsent, then write code that prints all classrooms reachable directly from classroom 2.

Show answer

Build the graph like this:

Map<Integer, List<Integer>> g = new HashMap<>(); int[][] edges = {{1,2},{1,3},{2,3},{2,4},{4,5}}; for (int[] e : edges) { g.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]); g.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]); }

Then print neighbors: System.out.println(g.get(2)); outputs [1, 3, 4]. The computeIfAbsent pattern eliminates the need for a separate vertex-creation loop.

Question 5: CRITICAL THINKING

Consider a directed graph where edges represent Twitter follows: user A follows user B does NOT mean B follows A. Given follows: 1→2, 1→3, 2→3, 3→1, write the adjacency list. Then explain: what would you need to change in the data structure to also efficiently answer "who follows user X?" (i.e., find incoming edges)?

Show answer

The adjacency list for the directed graph is: {1=[2,3], 2=[3], 3=[1]}. This lets you quickly answer "who does X follow?" but NOT "who follows X?" To efficiently answer the reverse question, you'd need a second map—a reverse adjacency list—where each key maps to the list of users who point TO that key. For this graph it would be: {1=[3], 2=[1], 3=[1,2]}. Maintaining two maps doubles the memory for edges but lets you traverse the graph in both directions in O(1) per lookup. This is a common pattern in real-world systems like social networks.

SUMMARY

Lesson Summary

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.