Graph Adjacency List
Overview
A Graph is a data structure consisting of Nodes (Vertices) connected by Edges. Unlike trees, graphs can have cycles (loops), multiple disjoint pieces, and no strict root.
There are two main ways to represent a graph in code. The most common and efficient for real-world scenarios is the Adjacency List. In this representation, every vertex stores a list of the vertices it is directly connected to (its neighbors).
In Java, this is perfectly modeled using a HashMap<Node, List<Node>> or an array of List objects List<Integer>[].
The Adjacency List is extremely Space Efficient (O(V + E)) because it only allocates memory for edges that actually exist. This makes it the superior choice for 'Sparse Graphs' (like Facebook friends or city road networks, where a node is only connected to a tiny fraction of the total network).
Syntax
import java.util.*;
public class Graph {
// HashMap representation allows for arbitrary node IDs (like Strings or negative numbers)
private Map<Integer, List<Integer>> adjList = new HashMap<>();
// Add a vertex to the graph
public void addVertex(int v) {
adjList.putIfAbsent(v, new ArrayList<>());
}
// Add an undirected edge between v and w
public void addEdge(int v, int w) {
addVertex(v);
addVertex(w);
// Undirected means the connection goes both ways
adjList.get(v).add(w);
adjList.get(w).add(v);
}
// Get all neighbors of a vertex
public List<Integer> getNeighbors(int v) {
return adjList.getOrDefault(v, new ArrayList<>());
}
public static void main(String[] args) {
Graph g = new Graph();
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
System.out.println("Neighbors of 0: " + g.getNeighbors(0)); // [1, 2]
}
}Common Pitfalls
- NullPointerExceptions when checking unconnected nodes. If you initialize the graph using a HashMap, querying
map.get(node)for a node that has no edges might returnnull. Always usemap.getOrDefault(node, new ArrayList<>())or ensure all vertices are initialized. - Infinite loops during traversal. Because graphs can have cycles (A points to B, B points to C, C points to A), a naive DFS/BFS will loop forever. You MUST maintain a
Set<Node> visitedto track where you've been and avoid processing the same node twice. - Forgetting to add bidirectional edges. If the problem states the graph is 'Undirected', you must add the edge twice:
list.get(u).add(v)ANDlist.get(v).add(u). If it is 'Directed', you only add it once.
Interview Questions
When the graph is Sparse (has relatively few edges compared to the maximum possible edges). An Adjacency List uses O(V + E) space, whereas a Matrix always uses O(V^2) space. Real-world graphs like social networks are massively sparse (you have 500 friends, not 2 billion).
O(K), where K is the number of neighbors Node A has. You must get A's list and iterate through it to see if B is present. (In an Adjacency Matrix, this check is O(1)).
Real-World Example
Social Networks (Facebook/LinkedIn) are giant graphs using Adjacency Lists. A 'User' is a vertex, and a 'Friendship' is an undirected edge. Because users only have a few hundred friends out of billions of accounts, an Adjacency Matrix would require exabytes of wasted memory. The List only stores the actual connections.
class SocialNetwork {
Map<String, Set<String>> friendsList = new HashMap<>();
public void makeFriends(String userA, String userB) {
friendsList.putIfAbsent(userA, new HashSet<>());
friendsList.putIfAbsent(userB, new HashSet<>());
// Using a Set instead of List prevents duplicate edges O(1)
friendsList.get(userA).add(userB);
friendsList.get(userB).add(userA);
}
}Check Your Knowledge
Test your understanding of Graph Adjacency List with these quick questions.