An adjacency list stores each vertex with its neighboring vertices, rather than placing every possible pair in a grid. It is usually the most efficient representation for a sparse graph, where the number of edges is much smaller than the square of the number of vertices.

An adjacency list is not an ordered path through a graph. Each entry records local connections; a traversal algorithm chooses the next vertex separately.

What is an adjacency list?

An adjacency list maps every vertex to a collection of adjacent vertices. In an adjacency list graph, the outer structure is commonly an array or map, and each value is a dynamic list. An array works well when vertices have numeric indexes. A map is useful when labels such as “A” or “Airport 12” identify vertices.

For a vertex v, its list contains the vertices reachable by one edge from v. The number of entries is its degree in an undirected graph or its out-degree in a directed graph. Isolated vertices still receive an empty list so that the representation includes every vertex.

How do you build a graph adjacency list from edge data?

Start with the vertices, create an empty list for each one, and then process each edge. Consider this undirected edge data:

• A-B
• A-C
• B-D
• C-D

The matching adjacency-list representation is:

• A: B, C
• B: A, D
• C: A, D
• D: B, C

Each undirected edge appears twice. The edge A-B is recorded in A’s list and B’s list, allowing neighbor lookup from either endpoint. A simple construction procedure is:

1. Initialize an empty list for every vertex.
2. For an edge between u and v, append v to u’s list.
3. Because the edge is undirected, append u to v’s list as well.

If the input can contain parallel edges, append each occurrence unless the application requires duplicate removal. A set can enforce unique neighbors, but it changes the storage structure and may add overhead.

How does an adjacency list represent directed and weighted edges?

Direction determines which list receives an edge. For directed edges A→B, A→C, and C→B, the list is:

• A: B, C
• B: empty
• C: B

The reverse connection is not implied. If an algorithm must find incoming neighbors, it can maintain a second reverse adjacency list or scan all lists.

Weighted edges store a neighbor together with its weight. For example, the weighted edge data A→B with cost 5 and A→C with cost 2 becomes:

• A: (B, 5), (C, 2)
• B: empty
• C: empty

The weight can represent distance, price, capacity, or another application-specific value. Adding weights changes the value stored beside each neighbor, not the basic adjacency-list structure or its usual asymptotic costs.

When is an adjacency list for a graph better than an adjacency matrix?

For V vertices and E edges, an adjacency list uses O(V + E) space when each edge is stored once in a directed graph or twice in an undirected graph. This is efficient for sparse graphs because it stores actual connections instead of all possible connections.

• Iterating neighbors: O(degree(v)) for vertex v. The algorithm visits only listed neighbors.
• Testing a specific edge: usually O(degree(v)) when scanning the list for the target. A hash-based neighbor set provides O(1) average lookup, with additional memory overhead.
• Adding an edge: commonly O(1) when appending to a list, unless duplicate checking is required.

An adjacency matrix uses O(V²) space and provides O(1) edge testing by checking one cell. However, finding all neighbors of a vertex requires scanning its entire row, which costs O(V), including cells for absent edges. Choose an adjacency list when neighbor traversal and compact storage matter, especially for sparse networks. Choose a matrix when the graph is dense or constant-time edge tests are more important than memory use.