Interview Cake by Aced

Adjacency List

In short: An adjacency list represents a graph by storing, for each node, a list of the nodes it's connected to, usually in a hash map or an array of lists. It takes O(n + m) space and is the default choice for sparse graphs in coding interviews.

One common graph storage format is called an adjacency list.

In this format, every node has an array of connected neighbors: an adjacency list. We could store these arrays in a hash map where the keys represent the node and the values are the adjacency lists.

For instance, here's one graph:

An example graph composed of 4 labeled vertices.

And, here's how we'd represent it using a hash map:

Map<Integer, Integer[]> graph = new HashMap<Integer, Integer[]>() {{ put(0, new Integer[] {1}); put(1, new Integer[] {0, 2, 3}); put(2, new Integer[] {1, 3}); put(3, new Integer[] {1, 2}); }};

Since node 3 has edges to nodes 1 and 2, graph.get(3) has the adjacency list {1, 2}.

See also:

Frequently Asked Questions

What is an adjacency list?

A way to store a graph where each node maps to a list (or set) of its neighbors. For example, {0: [1], 1: [0, 2, 3]} means node 1 is connected to nodes 0, 2, and 3.

What's the difference between an adjacency list and an adjacency matrix?

An adjacency list uses O(n + m) space and makes it fast to loop over a node's neighbors; an adjacency matrix uses O(n^2) space but checks whether an edge exists in O(1). Lists suit sparse graphs, matrices dense ones.

How long does it take to check for an edge in an adjacency list?

O(d), where d is the node's degree, if neighbors are stored in a list, or O(1) on average if each node's neighbors are stored in a hash set.

Last updated: October 21, 2026

. . .