What Is an Adjacency List?
An adjacency list is one of the most common and efficient ways to represent a graph in code. It stores each node alongside a collection of its neighboring nodes. Instead of a dense matrix of edges, you have a mapping from a node to a list (or set) of all nodes directly reachable from it.
For a graph with vertices V and edges E, the adjacency list uses O(V + E) space. This makes it ideal for sparse graphs, where the number of edges is much smaller than V². In contrast, an adjacency matrix would require O(V²) space regardless of edge count.
A typical adjacency list can be built using a hash map (dictionary) or an array of lists. The keys are the node identifiers, and the values are lists of neighboring nodes. In weighted graphs, each neighbor entry is often a pair (tuple) containing the neighbor and the edge weight.
Simple Visual Example
Graph:
0 → 1, 2
1 → 2
2 → 0, 3
3 → 3 (self-loop)
Adjacency list representation:
{
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
}
Why Adjacency Lists Matter in Interviews
🚀 Deploy your AI agent in 10 minutes
Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.
Try it free →In technical interviews, graph problems appear frequently. The adjacency list is the default representation because of its flexibility and performance characteristics:
- Space efficiency – Most real-world graphs (social networks, web links, transportation maps) are sparse. You save memory and avoid iterating over empty cells.
- Traversal speed – Iterating over a node’s neighbors is proportional to its degree, not to the total number of vertices. This leads to faster BFS/DFS in sparse graphs.
- Easy to build from edge lists – Interview inputs often come as arrays of edges, adjacency matrices, or connections. Converting to an adjacency list is straightforward and demonstrates fundamental graph manipulation skills.
- Natural fit for algorithms – Classic algorithms like Dijkstra, topological sort, cycle detection, and connected components are almost always implemented with adjacency lists in interview settings.
Mastering adjacency list construction, traversal, and modification is a core skill that unlocks success across a wide range of graph problems.
How to Build and Use an Adjacency List
You typically start with an input like an edge list or a set of connections. You’ll create a mapping (dictionary or array of lists) and populate it. The exact implementation depends on whether the graph is directed, undirected, weighted, or unweighted.
Basic Implementation (Unweighted, Directed)
def build_adjacency_list(n, edges):
# n: number of nodes (0-indexed)
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
return adj
# Example usage
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
adj = build_adjacency_list(4, edges)
# adj[0] → [1, 2], adj[1] → [2], adj[2] → [3], adj[3] → []
Undirected Graph
Simply add both directions. Use a set instead of a list if you want to avoid duplicates (when edges may be repeated).
def build_undirected_adjacency(n, edges):
adj = [set() for _ in range(n)]
for u, v in edges:
adj[u].add(v)
adj[v].add(u)
return adj
Weighted Graph
Store tuples of (neighbor, weight) in the list.
def build_weighted_adjacency(n, weighted_edges):
adj = [[] for _ in range(n)]
for u, v, w in weighted_edges:
adj[u].append((v, w))
# For undirected weighted, also append (u, w) to adj[v]
return adj
# Example: edges = [(0, 1, 5), (1, 2, 3), (2, 0, 1)]
Using a Dictionary for Non-Integer Nodes
from collections import defaultdict
def build_graph(edges):
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
# For undirected: adj[v].append(u)
return adj
# Nodes can be strings, tuples, etc.
edges = [("A", "B"), ("B", "C"), ("C", "A")]
graph = build_graph(edges)
Traversal Algorithms Using Adjacency Lists
Once you have the adjacency list, BFS and DFS are the building blocks for solving more complex problems.
BFS (Breadth-First Search)
from collections import deque
def bfs(adj, start):
visited = set()
q = deque([start])
visited.add(start)
while q:
node = q.popleft()
print(node) # or process node
for neighbor in adj[node]:
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)
DFS (Depth-First Search)
def dfs(adj, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node) # process node
for neighbor in adj[node]:
if neighbor not in visited:
dfs(adj, neighbor, visited)
# Iterative DFS using stack
def dfs_iterative(adj, start):
visited = set()
stack = [start]
visited.add(start)
while stack:
node = stack.pop()
print(node)
for neighbor in adj[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
Common Interview Problems and Solutions
Below are classic adjacency-list-based problems you’ll likely encounter, with complete solutions and analysis.
1. Clone Graph (Deep Copy)
Problem: Given a node in a connected undirected graph represented as an adjacency list (each node's neighbors list), return a deep copy of the entire graph.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def cloneGraph(node):
if not node:
return None
old_to_new = {}
def dfs(n):
if n in old_to_new:
return old_to_new[n]
copy = Node(n.val)
old_to_new[n] = copy
for nei in n.neighbors:
copy.neighbors.append(dfs(nei))
return copy
return dfs(node)
Complexity: O(V + E) time and space. The dictionary maps original nodes to cloned nodes, preventing cycles.
2. Detect Cycle in Undirected Graph
Problem: Determine if an undirected graph contains a cycle. The graph is given as number of vertices n and an edge list.
def has_cycle_undirected(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
def dfs(node, parent):
visited[node] = True
for nei in adj[node]:
if not visited[nei]:
if dfs(nei, node):
return True
elif nei != parent:
# visited neighbor that is not parent → cycle
return True
return False
for i in range(n):
if not visited[i]:
if dfs(i, -1):
return True
return False
For directed graphs, use three colors (white, gray, black) or track recursion stack to detect back edges.
3. Course Schedule / Topological Sort
Problem: There are numCourses and prerequisites pairs [a, b] meaning b → a. Return a valid order or detect impossibility (cycle).
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
adj = defaultdict(list)
indegree = [0] * numCourses
for a, b in prerequisites:
adj[b].append(a)
indegree[a] += 1
q = deque([i for i in range(numCourses) if indegree[i] == 0])
order = []
while q:
course = q.popleft()
order.append(course)
for nei in adj[course]:
indegree[nei] -= 1
if indegree[nei] == 0:
q.append(nei)
return order if len(order) == numCourses else []
This is Kahn’s algorithm using BFS. DFS with stack also works. Both rely on the adjacency list for dependency traversal.
4. Connected Components in Undirected Graph
Problem: Count the number of connected components.
def count_components(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
count = 0
def dfs(node):
visited[node] = True
for nei in adj[node]:
if not visited[nei]:
dfs(nei)
for i in range(n):
if not visited[i]:
dfs(i)
count += 1
return count
5. Shortest Path in Unweighted Graph
Problem: Find the minimum number of edges from start to target. BFS on adjacency list gives shortest path by edge count.
def shortest_path(adj, start, target):
if start == target:
return 0
visited = set([start])
q = deque([(start, 0)]) # (node, distance)
while q:
node, dist = q.popleft()
for nei in adj[node]:
if nei == target:
return dist + 1
if nei not in visited:
visited.add(nei)
q.append((nei, dist + 1))
return -1 # not reachable
6. Word Ladder
Problem: Transform one word to another by changing one letter at a time, each intermediate word must be in a dictionary. This is essentially a shortest path on an implicit graph. Build adjacency by grouping words with wildcards.
from collections import defaultdict, deque
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
# Build adjacency via generic transformations
wild_to_words = defaultdict(list)
for word in wordList:
for i in range(len(word)):
wild = word[:i] + '*' + word[i+1:]
wild_to_words[wild].append(word)
visited = set([beginWord])
q = deque([(beginWord, 1)])
while q:
word, steps = q.popleft()
for i in range(len(word)):
wild = word[:i] + '*' + word[i+1:]
for neighbor in wild_to_words[wild]:
if neighbor == endWord:
return steps + 1
if neighbor not in visited:
visited.add(neighbor)
q.append((neighbor, steps + 1))
return 0
7. Number of Islands (Grid to Adjacency List)
While often solved directly on a 2D grid, you can treat each cell as a node and build an explicit adjacency list for practice. Usually it's more efficient to use the grid directly, but understanding the conversion is valuable.
# Conceptual conversion: grid cell (r,c) with value '1' connects to 4-directional neighbors
# Adjacency list: key = (r,c), value = list of neighbor coordinates that are '1'
In interviews, you'll often stick to grid traversal with DFS/BFS rather than building a full adjacency list, but the mental model is identical: each cell has up to 4 neighbors.
Best Practices and Tips
- Choose the right container – Use
defaultdict(list)or array of lists for performance. Use sets for neighbors if you need to quickly deduplicate or check existence. - Always handle disconnected components – Many problems require iterating over all vertices and initiating DFS/BFS from unvisited ones.
- Track visited state correctly – For BFS, mark visited when enqueuing; for DFS, when pushing/entering. Avoid revisiting nodes that cause infinite loops or exponential blowups.
- Watch for cycles in directed graphs – Use a three-color marking (0=unvisited, 1=visiting, 2=visited) or a recursion set to detect back edges.
- Prefer iterative over recursive DFS for large graphs – Recursion depth can hit limits. Use explicit stacks when possible.
- Convert input efficiently – If input is an edge list, build the adjacency list in one pass. Avoid nested loops scanning a matrix when a sparse representation exists.
- Keep edge weights accessible – For Dijkstra or Bellman-Ford, store tuples
(neighbor, weight). Use a priority queue that sorts by distance. - Test with edge cases – Single node, no edges, self-loops, disconnected nodes, duplicate edges. Your adjacency list should gracefully handle these.
Conclusion
The adjacency list is the cornerstone of graph problem-solving in technical interviews. Its space efficiency and natural alignment with traversal algorithms make it the go-to representation for most problems. By mastering how to build adjacency lists from different input formats, apply BFS/DFS, and adapt them to classic problems like cycle detection, topological sorting, and shortest paths, you’ll be equipped to tackle the vast majority of graph-based interview challenges. Always focus on clarity, handle edge cases, and choose the right traversal strategy, and you’ll turn adjacency list problems into reliable successes.