A graph on paper is just dots and lines. Before a program can search it, find paths through it or count its connections, those dots and lines have to be turned into something that lives in memory. The format we choose for that is called the graph representation, and it decides how fast every later operation will be.
Two formats cover almost every practical need: the adjacency matrix, a V × V grid of yes/no cells, and the adjacency list, which is the subject of this tutorial. We will build an adjacency list in Java for all four combinations of directed/undirected and weighted/unweighted graphs, then look at a name-based version, its costs, and when to prefer it.
What is an Adjacency List?
An adjacency list gives every vertex its own small collection holding the vertices it connects to. Think of the contacts app on a phone: each person keeps a list of only the people they actually know, not a register of everyone on the planet with a checkmark beside the few they have met. The list for a vertex is often called its neighbour list.
In Java there are three common ways to hold these lists:
List<List<Integer>>: the outer list is indexed by vertex number 0 to V - 1. Simple and fast, and the form used in most examples below.List<Integer>[]: an array of lists. It behaves the same way but needs an unchecked generic array, so the list-of-lists form is usually cleaner.Map<K, List<K>>: the key is the vertex itself. Use it when vertices are names, IDs or objects rather than consecutive integers.
The Sample Graph Used in This Tutorial
To make the examples easy to compare, every program uses the same five vertices (0 to 4) and the same six connections. In the directed version the arrows below show the direction of each edge:
┌──────────────────┐
▼ │
0 ──► 1 ──► 2 ──► 4 ─────┘
│ ▲
└──► 3 ─────┘
Edges: 0→1, 0→3, 1→2, 3→2, 2→4, 4→1
Notice the loop 1 → 2 → 4 → 1. A cycle like this needs no special handling in an adjacency list; it is simply three ordinary entries.
Adjacency List for a Directed Graph
In a directed graph an edge from → to can only be travelled one way, so it is written into the neighbour list of from and nowhere else. The program wraps the list of lists in a small class so the setup code is written once.
import java.util.ArrayList;
import java.util.List;
// Directed, unweighted graph stored as an adjacency list
public class Main {
private final List<List<Integer>> adj;
Main(int vertexCount) {
adj = new ArrayList<>(vertexCount);
for (int v = 0; v < vertexCount; v++) {
adj.add(new ArrayList<>()); // every vertex starts with an empty neighbour list
}
}
// A directed edge is recorded only in the list of its source vertex
void addEdge(int from, int to) {
adj.get(from).add(to);
}
void display() {
for (int v = 0; v < adj.size(); v++) {
System.out.println(v + " -> " + adj.get(v));
}
}
public static void main(String[] args) {
Main graph = new Main(5);
graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(1, 2);
graph.addEdge(3, 2);
graph.addEdge(2, 4);
graph.addEdge(4, 1);
System.out.println("Directed graph (vertex -> outgoing neighbours):");
graph.display();
}
}Directed graph (vertex -> outgoing neighbours): 0 -> [1, 3] 1 -> [2] 2 -> [4] 3 -> [2] 4 -> [1]
Vertex 0 has two outgoing edges, every other vertex has one, and the total number of entries (6) equals the number of edges. Vertex 2 is reached from both 1 and 3, but that is not visible in the list of 2, because the list only records where you can go from a vertex.
Adjacency List for an Undirected Graph
When edges have no direction, a connection between u and v must be visible from both ends. The only change from the previous program is that addEdge writes two entries instead of one. As a bonus, the size of a neighbour list is now exactly the degree of that vertex.
import java.util.ArrayList;
import java.util.List;
// Undirected, unweighted graph stored as an adjacency list
public class Main {
private final List<List<Integer>> adj;
Main(int vertexCount) {
adj = new ArrayList<>(vertexCount);
for (int v = 0; v < vertexCount; v++) {
adj.add(new ArrayList<>());
}
}
// An undirected edge is stored twice: once at each endpoint
void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u);
}
int degree(int v) {
return adj.get(v).size();
}
void display() {
for (int v = 0; v < adj.size(); v++) {
System.out.println(v + " -> " + adj.get(v) + " (degree " + degree(v) + ")");
}
}
public static void main(String[] args) {
Main graph = new Main(5);
graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(1, 2);
graph.addEdge(3, 2);
graph.addEdge(2, 4);
graph.addEdge(4, 1);
System.out.println("Undirected graph (vertex -> neighbours):");
graph.display();
}
}Undirected graph (vertex -> neighbours): 0 -> [1, 3] (degree 2) 1 -> [0, 2, 4] (degree 3) 2 -> [1, 3, 4] (degree 3) 3 -> [0, 2] (degree 2) 4 -> [2, 1] (degree 2)
There are now 12 entries for 6 edges, and the degrees add up to 12 as well. This is the handshake rule: in any undirected graph the sum of all degrees is twice the number of edges.
Adjacency List for a Directed Weighted Graph
Many graphs attach a number to each edge: a ticket price, a travel time, a bandwidth limit. A plain integer can no longer describe a neighbour, so each entry becomes a small Edge record holding the target vertex and the cost. A Java record keeps this to a single line.
import java.util.ArrayList;
import java.util.List;
// Directed, weighted graph: each list entry carries a target and a cost
public class Main {
record Edge(int target, int cost) {
@Override
public String toString() {
return target + "(" + cost + ")";
}
}
private final List<List<Edge>> adj;
Main(int vertexCount) {
adj = new ArrayList<>(vertexCount);
for (int v = 0; v < vertexCount; v++) {
adj.add(new ArrayList<>());
}
}
void addEdge(int from, int to, int cost) {
adj.get(from).add(new Edge(to, cost));
}
void display() {
for (int v = 0; v < adj.size(); v++) {
System.out.println(v + " -> " + adj.get(v));
}
}
public static void main(String[] args) {
Main graph = new Main(5);
graph.addEdge(0, 1, 8);
graph.addEdge(0, 3, 4);
graph.addEdge(1, 2, 6);
graph.addEdge(3, 2, 1);
graph.addEdge(2, 4, 9);
graph.addEdge(4, 1, 3);
System.out.println("Directed weighted graph (vertex -> target(cost)):");
graph.display();
}
}Directed weighted graph (vertex -> target(cost)): 0 -> [1(8), 3(4)] 1 -> [2(6)] 2 -> [4(9)] 3 -> [2(1)] 4 -> [1(3)]
This is exactly the shape that shortest-path algorithms such as Dijkstra's expect: for the vertex being processed, they loop over its Edge entries and read both the target and the cost in one step.
Adjacency List for an Undirected Weighted Graph
Combine the two previous ideas: store an Edge record, and store it at both endpoints with the same cost. The example also adds a helper that sums the weights around one vertex, which shows how easily per-vertex questions are answered from its list.
import java.util.ArrayList;
import java.util.List;
// Undirected, weighted graph: the same weight is stored at both endpoints
public class Main {
record Edge(int target, int cost) {
@Override
public String toString() {
return target + "(" + cost + ")";
}
}
private final List<List<Edge>> adj;
Main(int vertexCount) {
adj = new ArrayList<>(vertexCount);
for (int v = 0; v < vertexCount; v++) {
adj.add(new ArrayList<>());
}
}
void addEdge(int u, int v, int cost) {
adj.get(u).add(new Edge(v, cost));
adj.get(v).add(new Edge(u, cost));
}
// Sum of the weights of all edges touching vertex v
int totalCost(int v) {
int sum = 0;
for (Edge e : adj.get(v)) {
sum += e.cost();
}
return sum;
}
void display() {
for (int v = 0; v < adj.size(); v++) {
System.out.println(v + " -> " + adj.get(v) + " total = " + totalCost(v));
}
}
public static void main(String[] args) {
Main graph = new Main(5);
graph.addEdge(0, 1, 8);
graph.addEdge(0, 3, 4);
graph.addEdge(1, 2, 6);
graph.addEdge(3, 2, 1);
graph.addEdge(2, 4, 9);
graph.addEdge(4, 1, 3);
System.out.println("Undirected weighted graph (vertex -> neighbour(cost)):");
graph.display();
}
}Undirected weighted graph (vertex -> neighbour(cost)): 0 -> [1(8), 3(4)] total = 12 1 -> [0(8), 2(6), 4(3)] total = 17 2 -> [1(6), 3(1), 4(9)] total = 16 3 -> [0(4), 2(1)] total = 5 4 -> [2(9), 1(3)] total = 12
Map-Based Adjacency List with Named Vertices
Real data rarely arrives numbered 0 to V - 1. Stations, user IDs and URLs are easier to handle when the vertex itself is the key of a Map. A LinkedHashMap keeps vertices in the order they were added, which makes the output predictable. This version also shows how to delete a vertex: remove its own entry, then remove it from each of its neighbours' lists.
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
// Adjacency list keyed by vertex name instead of by index
public class Main {
private final Map<String, List<String>> adj = new LinkedHashMap<>();
void addVertex(String name) {
adj.putIfAbsent(name, new ArrayList<>());
}
void addEdge(String a, String b) {
addVertex(a);
addVertex(b);
adj.get(a).add(b);
adj.get(b).add(a);
}
// Deleting a vertex also deletes every edge that points to it
void removeVertex(String name) {
List<String> neighbours = adj.remove(name);
if (neighbours == null) {
return;
}
for (String n : neighbours) {
adj.get(n).remove(name);
}
}
public static void main(String[] args) {
Main metro = new Main();
metro.addEdge("Central", "Harbour");
metro.addEdge("Central", "Museum");
metro.addEdge("Harbour", "Airport");
metro.addEdge("Museum", "Airport");
System.out.println("Before: " + metro.adj);
metro.removeVertex("Museum");
System.out.println("After removing Museum: " + metro.adj);
}
}Before: {Central=[Harbour, Museum], Harbour=[Central, Airport], Museum=[Central, Airport], Airport=[Harbour, Museum]}
After removing Museum: {Central=[Harbour], Harbour=[Central, Airport], Airport=[Harbour]}Time and Space Complexity
In the table, V is the number of vertices, E the number of edges and deg(v) the length of the neighbour list of vertex v.
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
| Memory used | O(V + E) | O(V2) |
| Add an edge | O(1) | O(1) |
| Check whether edge u–v exists | O(deg(u)) | O(1) |
| Visit all neighbours of v | O(deg(v)) | O(V) |
| Remove an edge | O(deg(u)) | O(1) |
| Add a vertex | O(1) | O(V2) (grid must be rebuilt) |
| Full BFS or DFS traversal | O(V + E) | O(V2) |
The gap matters most for sparse graphs, where E is far smaller than V2. A road map of 100,000 junctions with around 250,000 roads needs about 350,000 list slots, while a matrix would need ten billion cells.
Advantages of an Adjacency List
- Memory proportional to the graph: only real connections are stored, so space grows with V + E instead of V2.
- Fast neighbour iteration: looping over a vertex's neighbours touches only those neighbours, which is the inner loop of BFS, DFS, Dijkstra's and Prim's algorithms.
- Easy to grow: a new vertex is one new empty list; nothing else has to be resized.
- Room for edge data: weights, labels or timestamps fit naturally into an edge object.
- Handles unusual edges: self-loops and repeated (parallel) edges are just extra entries in a list.
Disadvantages of an Adjacency List
- Slower edge checks: answering "is u connected to v?" means scanning the list of u, instead of reading one cell.
- Weak for dense graphs: when most pairs are connected, the per-entry overhead of objects and pointers makes a list larger than a compact matrix.
- Incoming edges are hidden: in a directed graph, finding which vertices point to v requires checking every list, unless a second reverse list is kept.
- Duplicate bookkeeping: undirected edges are stored twice, and both copies must be kept in sync on every update or delete.
Key Takeaways
- An adjacency list maps each vertex to the collection of vertices it connects to.
- Directed edges are stored once; undirected edges are stored at both endpoints.
- Weighted graphs replace plain integers with an edge object that carries the weight.
- Use a
Mapwhen vertices are not simple indexes. - Prefer an adjacency list for sparse graphs and traversal-heavy work; prefer a matrix for small, dense graphs that need constant-time edge checks.