Introduction

Adjacency lists are popular because they represent sparse graphs efficiently, but their performance depends on the operation you are measuring. The right way to analyze them is to separate storage cost, neighbor iteration, edge lookup, and full graph traversal instead of summarizing everything as one complexity value.

Space Complexity

An adjacency list stores a collection of neighbors for each vertex. For a graph with V vertices and E edges, the total storage is O(V + E).

That result comes from two parts:

• One entry for each vertex
• One stored neighbor reference for each edge

In a directed graph, each edge appears once. In an undirected graph, each edge is usually stored twice, once from each endpoint. The big-O result is still linear in the graph size.

Cost of Core Operations

The main advantage of an adjacency list is fast access to the neighbors of one vertex. It does not make every graph query constant time.

For a classic list-backed representation:

• Access the neighbor list for one vertex: usually O(1)
• Iterate over all neighbors of one vertex: O(deg(v))
• Add an edge by appending to a list: usually O(1) amortized
• Check whether a specific edge exists: O(deg(u))
• Remove an edge: O(deg(u))

The important symbol here is deg(v), the degree of a vertex. Operations that search inside a neighbor list depend on that degree, not on the total number of vertices.

Example Implementation

The following Python example shows a plain adjacency-list graph where each vertex stores neighbors in a normal list.

1class Graph:
2    def __init__(self, directed=False):
3        self.directed = directed
4        self.adj = {}
5
6    def add_vertex(self, vertex):
7        self.adj.setdefault(vertex, [])
8
9    def add_edge(self, u, v):
10        self.add_vertex(u)
11        self.add_vertex(v)
12        self.adj[u].append(v)
13        if not self.directed:
14            self.adj[v].append(u)
15
16    def has_edge(self, u, v):
17        return v in self.adj.get(u, [])

In this version, has_edge(u, v) scans the neighbor list for u, so it is not constant time. That is one of the most common misunderstandings about adjacency lists.

Why BFS and DFS Are O(V + E)

Breadth-first search and depth-first search work very well with adjacency lists because the representation lets you iterate only over actual edges that exist. During a full traversal, each vertex is visited a limited number of times and each stored edge is inspected a limited number of times.

That gives the familiar O(V + E) time for BFS and DFS.

This is a traversal result, not a universal rule for every operation on the data structure. People often quote O(V + E) correctly for graph search but then incorrectly apply it to edge lookup or deletion.

Representation Details Matter

The phrase adjacency list does not describe one exact container choice. If each vertex stores neighbors in a hash set instead of a list, then edge existence checks can become average-case O(1) at the cost of extra memory and different iteration behavior.

That means complexity answers depend on the exact variant you assume. In interviews and coursework, if nothing else is stated, it is usually safest to assume a standard list-backed adjacency list.

Common Pitfalls

• Claiming edge lookup is always O(1) in an adjacency list.
• Forgetting that undirected graphs usually store each edge twice.
• Applying the O(V + E) traversal result to unrelated operations such as single-edge removal.
• Ignoring the effect of the underlying container used for each neighbor list.

Summary

• A standard adjacency list uses O(V + E) space.
• Neighbor iteration is efficient and costs O(deg(v)) for one vertex.
• Edge insertion is usually cheap, but edge lookup in a list-backed version is not constant time.
• BFS and DFS run in O(V + E) because they inspect each vertex and stored edge a limited number of times.
• Always state whether the neighbor container is a list, set, or something else before quoting exact costs.