Adjacency List

In Turkish: Komşuluk Listesi
Pronunciation: uh-JAY-sun-see list

Updated September 30, 20263 min read

In short

An adjacency list is a way of storing a graph in which each node keeps a list of the nodes it connects to, using memory in proportion to its nodes and edges.

What is an adjacency list?

An adjacency list is the most common way to store a graph in a program. For every node, also called a vertex, it keeps a list of that node's neighbors, meaning the nodes it has an edge to. In code this is usually just a dictionary or map from each node to an array of its neighbors.

In a directed graph, each edge appears once, in the list of the node it starts from; in an undirected graph, each edge is stored twice, once at each end. For weighted graphs, each entry holds the neighbor together with the edge's weight, such as a distance or a cost. The total memory is O(V + E), where V is the number of vertices and E the number of edges, and visiting all of a node's neighbors takes time proportional to how many it has. Checking whether one specific edge exists, however, means scanning a list, which takes O(d) time, where d is the node's degree, its number of neighbors.

Think of the contact list on each person's phone: to find someone's friends, you open their list, instead of consulting a giant table of every possible pair of people in the world. Adjacency lists are the standard input for graph algorithms such as breadth-first search, depth-first search, Dijkstra's algorithm, and topological sort, all of which walk each node's neighbors. Real-world graphs such as social networks, road maps, web links, and package dependencies are sparse, meaning each node connects to only a tiny fraction of the others, which is exactly where adjacency lists shine.

The main alternative is an adjacency matrix, a V by V grid in which the cell at row i and column j records whether there is an edge from i to j. A matrix checks for any edge in O(1) but always uses O(V^2) memory, even for a graph with almost no edges, so it suits small or dense graphs. Also note that an adjacency list is a way to represent a graph, not a data structure with its own rules: the neighbor lists can be arrays, linked lists, or hash sets when fast edge lookups are needed.

Key takeaways

An adjacency list maps each node to the list of nodes it has edges to.
It uses O(V + E) memory, which suits sparse graphs.
Iterating over a node's neighbors is fast, but checking for one specific edge takes O(degree).
Weighted graphs store a weight alongside each neighbor.
An adjacency matrix uses O(V^2) memory but checks any edge in O(1).

Example

Building a weighted adjacency list in Pythonpython

from collections import defaultdict

# Build an undirected, weighted graph from a list of roads (city, city, km)
roads = [("A", "B", 5), ("A", "C", 2), ("B", "D", 4), ("C", "D", 8)]
graph = defaultdict(list)
for u, v, km in roads:
    graph[u].append((v, km))  # store each edge in both directions
    graph[v].append((u, km))

print(graph["A"])  # [('B', 5), ('C', 2)]
print(graph["D"])  # [('B', 4), ('C', 8)]

# A node's degree is simply the length of its neighbor list
print({node: len(neighbors) for node, neighbors in graph.items()})  # every city has 2

Readers ask

What is the difference between an adjacency list and an adjacency matrix?

An adjacency list stores only the edges that exist, using O(V + E) memory, and is best for sparse graphs. An adjacency matrix stores a cell for every pair of nodes, using O(V^2) memory, but checks whether any edge exists in O(1), which suits small or dense graphs.

What is the space complexity of an adjacency list?

It is O(V + E): one entry per vertex plus one entry per edge in a directed graph, or two per edge in an undirected graph, since each edge is recorded at both ends.

How do I represent an adjacency list in code?

The simplest form is a map from each node to an array of neighbors, such as a Python dict of lists or a JavaScript Map of arrays. When nodes are numbered from 0 to V - 1, an array of arrays works too and is slightly faster.