What Is an Adjacency List? The Graph Representation Every Interview Expects

You've got a graph problem. Six nodes, a handful of edges, and an interviewer watching you figure out where to start. You draw boxes and arrows on the whiteboard. The boxes look fine. Now what?

The adjacency list is the default answer, and understanding exactly why is what separates people who "know graphs" from people who can actually solve graph problems in 45 minutes.

---

What a Graph Actually Needs From Storage

A graph has two things: vertices (nodes) and edges (connections between nodes). Every graph algorithm needs to answer one question repeatedly: "Given a vertex, what are its neighbors?"

You could store a graph as an edge list, a flat list of pairs like [(A, B), (B, C), (A, C)]. Simple, but finding all neighbors of A requires scanning the whole list. That's O(E) per lookup. For a graph with millions of edges, that's "submit button, watch the timer tick, hear the interviewer shift in their chair" slow.

You could also store an adjacency matrix, where matrix[i][j] = 1 means there's an edge from i to j. Neighbor lookup is O(V) per query because you always scan a full row. Worse, the matrix takes O(V²) space regardless of how many edges actually exist. A five-city map uses 25 entries. You're paying rent for 20 empty apartments. For sparse graphs, that's a lot of wasted memory. (A full comparison is in Adjacency List vs Adjacency Matrix.)

The adjacency list threads the needle.

---

What an Adjacency List Actually Is

An adjacency list stores, for each vertex, a list of that vertex's direct neighbors. That's the whole idea.

For an undirected graph with five cities:

A -- B
|    |
C -- D
     |
     E

The adjacency list looks like this:

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C, E]
E: [D]

Each vertex is a key. Its value is the list of vertices it connects to. To find A's neighbors, you look up A and get [B, C] in O(1). To iterate all neighbors, you walk the list in O(degree(A)).

For a directed graph, the list only stores outgoing edges. If A points to B but B doesn't point back, only A's list contains B.

---

Adjacency List Implementation in Python and TypeScript

In Python, a defaultdict(list) is the natural fit:

from collections import defaultdict

graph = defaultdict(list)

def add_edge(u, v):
    graph[u].append(v)
    graph[v].append(u)

add_edge("A", "B")
add_edge("A", "C")
add_edge("B", "D")
add_edge("C", "D")
add_edge("D", "E")

In TypeScript, a Map<string, string[]> or plain object works:

const graph: Record<string, string[]> = {};

function addEdge(u: string, v: string): void {
  if (!graph[u]) graph[u] = [];
  if (!graph[v]) graph[v] = [];
  graph[u].push(v);
  graph[v].push(u);
}

addEdge("A", "B");
addEdge("A", "C");
addEdge("B", "D");

For weighted graphs, store pairs instead of single vertices:

graph = defaultdict(list)

def add_edge(u, v, weight):
    graph[u].append((v, weight))
    graph[v].append((u, weight))

In most interview problems, the graph arrives as a list of edges, and your first step is almost always converting it to an adjacency list before writing a single line of the main algorithm. Interviewers have seen people try to run BFS directly on a raw edge list. It doesn't end well for anyone.

---

Adjacency List Space and Time Complexity

A graph has V vertices and E edges. The adjacency list stores every edge once for directed graphs and twice for undirected (once in each direction).

Space complexity: O(V + E).

That plus-sign matters. For a sparse graph where E is close to V, the total size is roughly O(V). For a dense graph where every vertex connects to almost every other, E approaches V², and the list uses O(V²) space, same as the matrix. But for sparse graphs, the list wins dramatically.

Most real-world graphs are sparse. A social network with 1 billion users doesn't have 10^18 friendships. A city road map doesn't connect every intersection to every other. The adjacency list is the right default because most graphs you'll see in interviews are sparse.

The adjacency list in a nutshell: only allocate space for what's actually there. The matrix pre-allocates for everything that could exist.

---

What Each Operation Costs

Operation	Adjacency List	Adjacency Matrix
Add edge	O(1)	O(1)
Check if edge (u, v) exists	O(degree(u))	O(1)
Iterate all neighbors of u	O(degree(u))	O(V)
Space	O(V + E)	O(V²)

The one place the adjacency list loses is edge existence checks. To know if there's an edge from A to B, you scan A's list. If A has 1,000 neighbors, that's 1,000 comparisons. The matrix gives you O(1) for the same check: matrix[A][B]. If your algorithm does a lot of "does this specific edge exist?" lookups, the matrix may be faster in practice.

But BFS, DFS, and Dijkstra all iterate over neighbors, not individual edges. For those, the adjacency list's O(degree(v)) neighbor iteration beats the matrix's O(V) row scan every time.

---

How BFS and DFS Use This

Both traversals follow the same pattern: visit a node, then visit its neighbors. The adjacency list is exactly what makes that efficient. For a deeper look at when to pick each, see BFS vs DFS.

BFS with an adjacency list:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:  # O(degree(node))
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Each node is processed once, and each edge is visited once (or twice for undirected). Total time: O(V + E). This is only possible because iterating neighbors is O(degree(v)), not O(V).

With an adjacency matrix, the same BFS takes O(V²) because you scan every row position looking for 1s. On a sparse graph, that's a 100x or 1000x slowdown for no reason other than a poor choice of data structure at the start. The list is why graph algorithms are expressed as O(V + E) rather than O(V²).

DFS works identically, just using a stack (or recursion) instead of a queue.

---

The Interview Patterns That Need This

Almost every graph problem in an interview starts with an edge list and expects you to build an adjacency list before doing anything else. The patterns where this shows up:

Number of Islands / Connected Components. The grid itself is an implicit adjacency list where each cell's neighbors are the four adjacent cells.

Course Schedule (Topological Sort). Prerequisites arrive as edge pairs. Converting them to an adjacency list is step one.

Shortest Path (BFS / Dijkstra). You need fast neighbor iteration. Dijkstra's priority queue is useless if iterating neighbors costs O(V) per step.

Graph Clone / Cycle Detection. You're traversing the graph structure, which means fast access to each node's neighbors.

When you get an edge list in an interview, don't code into it directly. Spend 30 seconds converting it:

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # remove for directed

Then your BFS or DFS runs on clean, O(degree(v)) neighbor lookups instead of O(E) scan-everything chaos.

If you want to practice applying this under real interview conditions, SpaceComplexity runs voice-based graph mock interviews with rubric feedback on exactly this kind of problem setup.

---

Directed vs Undirected: The One Bug That Bites Everyone

For undirected graphs, every edge is stored twice. add_edge(A, B) appends B to A's list and A to B's list. Space is still O(V + E), but E counts each undirected edge once, so you're storing 2E entries total.

For directed graphs, only add the outgoing direction. This is a common interview bug: forgetting to add both directions for an undirected graph, or accidentally adding both directions for a directed one.

Check the problem statement before you build the list. "Course prerequisites" is directed (course A requires course B doesn't mean B requires A). "Friendships" is undirected. Getting this wrong makes your BFS miss half the graph or double-count edges. You'll spend 10 minutes staring at a correct algorithm producing wrong answers, which is a fun experience in exactly the wrong setting.

---

The Decision Checklist

• An adjacency list maps each vertex to a list of its neighbors.
• Space is O(V + E), efficient for sparse graphs.
• Neighbor iteration is O(degree(v)), which is why BFS and DFS run in O(V + E).
• Edge existence check is O(degree(v)), slower than a matrix's O(1).
• Use a matrix when your algorithm needs frequent edge existence checks and the graph is dense. Use a list for almost everything else.
• In interviews: convert edge lists to adjacency lists before writing the main algorithm.
• Undirected graphs need both directions added; directed graphs only need one.

---

For a broader look at how graph problems are structured in interviews, Graph Data Structure Interview covers the full picture of representations, traversals, and interview patterns together.

---

Further Reading

• Adjacency List (Wikipedia)
• Adjacency List Representation (GeeksforGeeks)
• Graph Data Structures, CS50 at Harvard
• Adjacency Matrix and List Complexity (Baeldung on Computer Science)