Core Data Structures

Graph Representations

A graph is a set of vertices and a set of edges connecting them. How you store that structure — adjacency list vs. adjacency matrix — trades memory and iteration speed against O(1) edge lookup, and the choice ripples through every algorithm built on top.

Adjacency list: array/map of vertices, each holding a list of its neighbors — O(V + E) space, ideal for sparse graphs
Adjacency matrix: V × V boolean/weight grid — O(V²) space regardless of edge count, but O(1) edge-existence lookup
Iterating all neighbors of a vertex: O(deg(v)) with a list, O(V) with a matrix — the list wins whenever the graph is sparse
Directed vs. undirected: undirected edges appear in both endpoints' adjacency lists (or are symmetric in the matrix)
Weighted graphs store a weight alongside each edge — the list holds (neighbor, weight) pairs; the matrix stores weights instead of booleans
Most real-world graphs (social networks, road networks, dependency graphs) are sparse — E is much closer to V than to V² — which is why adjacency lists are the default

Adjacency list vs. adjacency matrix
Aspect	Adjacency list	Adjacency matrix
Space	O(V + E)	O(V²)
Edge (u, v) exists?	O(deg(u))	O(1)
Iterate all neighbors of v	O(deg(v))	O(V)
Iterate all edges	O(V + E)	O(V²)
Best for	Sparse graphs (most real graphs)	Dense graphs, or when O(1) edge lookup matters most

Adjacency list for a weighted directed graph

class Graph {
    private final Map<Integer, List<int[]>> adj = new HashMap<>();  // vertex -> [neighbor, weight]

    void addEdge(int from, int to, int weight) {
        adj.computeIfAbsent(from, k -> new ArrayList<>()).add(new int[]{to, weight});
        // omit the mirrored addEdge(to, from, weight) call for a directed graph
    }

    List<int[]> neighbors(int v) {
        return adj.getOrDefault(v, List.of());   // O(1) — empty list, not null, for a leaf vertex
    }
}

The choice of representation is not cosmetic — it determines the complexity of every algorithm built on top. Both BFS/DFS traversal (Graph Traversal Bfs Dfs) and Dijkstra's algorithm (Shortest Paths) are typically quoted as O(V + E) and O((V + E) log V) respectively — bounds that assume an adjacency list. Run the exact same algorithms over an adjacency matrix and every "iterate neighbors" step costs O(V) instead of O(deg(v)), degrading both to have a V² term.