Adjacency list

An adjacency list represents a Graph by storing, for each vertex, a list of its neighbors. With $n$ vertices, you have $n$ lists; the $i$ -th list contains every vertex that $v_{i}$ has an edge to.

$\forall v_{i} \in V, {w : (v_{i}, w) \in E}$

Each list is typically a Linked list or a Dynamic array. The container holding the lists is itself an array of length $V$ , indexed by vertex.

Properties

Size: $O (V + E)$ — proportional to actual data.
Per-vertex storage: a list of neighbors plus list overhead.
No wasted space for non-edges.

For a sparse graph with millions of vertices but a constant number of edges per vertex, the adjacency list is dramatically smaller than the corresponding adjacency matrix.

Operations

Operation	Complexity
Check if edge $(u, v)$ exists	$O (de g (u))$
Add edge	$O (1)$ to prepend to the list
Remove edge	$O (de g (u))$ to find and remove
Iterate all neighbors of $v$	$O (de g (v))$
Total space	$O (V + E)$

Edge lookup is no longer constant time — to check if there’s an edge from $u$ to $v$ , you scan $u$ ‘s neighbor list. For high-degree vertices, this can be slow.

Implementation

typedef struct edgeNode {
    int dest;
    int weight;             // for weighted graphs
    struct edgeNode *next;
} edgeNode;
 
edgeNode *adj[MAX_V] = {NULL};   // array of list heads
 
void addEdge(int u, int v, int weight, bool directed) {
    edgeNode *node = malloc(sizeof(edgeNode));
    node->dest   = v;
    node->weight = weight;
    node->next   = adj[u];
    adj[u] = node;
    
    if (!directed) {
        node = malloc(sizeof(edgeNode));
        node->dest   = u;
        node->weight = weight;
        node->next   = adj[v];
        adj[v] = node;
    }
}

A new edge is prepended to the source vertex’s list — $O (1)$ . For undirected graphs, two list nodes per edge.

When to use

Adjacency lists win when:

The graph is sparse — $E ≪ V^{2}$ . Almost all real-world graphs.
Memory is constrained.
You frequently iterate neighbors — $O (de g)$ rather than $O (V)$ per vertex.
You don’t need fast edge-existence checks.

Most graph algorithms in practice use adjacency lists:

BFS and DFS: $O (V + E)$ instead of $O (V^{2})$ .
Dijkstra with priority queue: $O ((V + E) lo g V)$ .
Topological sort: $O (V + E)$ .

When not to use

Very dense graphs — at $E \sim V^{2}$ , the adjacency list’s overhead (per-node pointers, allocator overhead, scattered memory) makes it slower than a matrix.
Need to query edge existence in $O (1)$ — common in algorithms that check “is there an edge between any two vertices?” repeatedly.

In these cases, see Adjacency matrix.

Variants

Linked list (most common): straightforward, easy to add/remove edges.
Dynamic array: better cache behavior, faster iteration.
Hash set: $O (1)$ edge lookup at the cost of unordered iteration.
Sorted array: $O (lo g de g)$ lookup via binary search if neighbors are sorted.

The choice depends on workload. For typical mixed read/write patterns, linked lists or dynamic arrays are fine.

Effect on algorithm complexity

The same algorithm has different complexities depending on representation:

Algorithm	Adjacency matrix	Adjacency list (binary heap PQ)
BFS / DFS	$O (V^{2})$	$O (V + E)$
Dijkstra	$O (V^{2})$	$O ((V + E) lo g V)$
Prim’s algorithm	$O (V^{2})$	$O ((V + E) lo g V)$

The Dijkstra and Prim rows depend on both the graph representation and the priority-queue choice — the bound combines the cost of decrease-key operations (PQ-dependent) with edge enumeration (representation-dependent). Switching from a binary heap to a Fibonacci heap drops Dijkstra and Prim with adjacency lists to $O (E + V lo g V)$ . The " $O (V^{2})$ " matrix entries are for the simple array-PQ implementation, which on dense graphs is actually faster than the heap version since iterating neighbors costs $O (V)$ per vertex either way.

For sparse graphs ( $E ≪ V^{2}$ ), the adjacency-list version is dramatically faster. This is why production graph code almost universally uses lists.

For the matrix alternative, see Adjacency matrix. For graph fundamentals and algorithm context, see Graph.

Idriss Rami — Notes

Explorer