Topic 60 of 78
Graph Adjacency List
Overview
A Graph is a data structure representing relationships (Edges) between objects (Vertices or Nodes). Think of a social network: You are a Node, and your friendships are Edges. An Adjacency List is the most common way to represent a Graph in code. It uses a Map or an Array of Lists, where each Node maps to a list of its immediate neighbors. It is highly memory-efficient for 'sparse' graphs (where most nodes aren't connected to everyone else).
Syntax
Using a `HashMap` allows for string-based node names (like City names) and handles disconnected nodes easily.
Adjacency List using a HashMap
java
public class Graph {
// Map of Node ID -> List of Neighbor IDs
private Map<Integer, List<Integer>> adjList = new HashMap<>();
public void addNode(int id) {
adjList.putIfAbsent(id, new ArrayList<>());
}
public void addEdge(int source, int destination) {
adjList.get(source).add(destination);
// If it's an UNDIRECTED graph, add the reverse edge too!
// adjList.get(destination).add(source);
}
public List<Integer> getNeighbors(int id) {
return adjList.getOrDefault(id, new ArrayList<>());
}
}Common Pitfalls
- Forgetting to initialize the empty list for a node, causing a NullPointerException when you try to add an edge.
- In an undirected graph, forgetting to add the edge going BOTH ways (`source -> destination` AND `destination -> source`).
Interview Tips
- Adjacency Lists are the default, go-to representation for Graphs in interviews. They take O(V + E) space.
Real-World Example
Social networks (Facebook friends) and Maps/Navigation systems represent real-world connections using Adjacency Lists.
example
java
// Finding friends of friends
List<String> friends = graph.getNeighbors("Alice");
for (String friend : friends) {
System.out.println(friend + "'s friends: " + graph.getNeighbors(friend));
}