# Adjacency List

URL: https://softwaredictionary.org/terms/adjacency-list
Category: Data Structures
Last updated: 2026-09-30
In Turkish: Komşuluk Listesi
Pronunciation: uh-JAY-sun-see list

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 Python

```python
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
```

## Frequently asked questions

**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.

---

Software Dictionary: https://softwaredictionary.org/ · https://softwaredictionary.org/llms.txt