Course contentsShow
← Computer Science
Lesson 675 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Adjacency List: Memory Efficiency

Understand why adjacency lists use O(V+E) space, making them ideal for sparse graphs.

Adjacency List: Memory Efficiency

What you'll learn: You'll understand why adjacency lists are the memory-efficient choice for sparse graphs, using only O(V+E) space.

The Space Formula Explained

An adjacency list stores exactly what exists in your graph—no more, no redundant empty slots. For each of the V vertices, you maintain a container (array or linked list), and across all vertices combined, you store exactly E edges (or 2E entries for undirected graphs, since each edge appears in both vertices' lists).

This gives us O(V + E) space complexity:

  • V for the array of vertex containers
  • E (or 2E) for the actual edge entries

Why This Matters: Sparse Graphs

Most real-world graphs are sparse—they have far fewer edges than the theoretical maximum of V². Think of social networks: you might have millions of users (V), but each person only knows hundreds of friends, not millions.

Compare this to an adjacency matrix, which always uses O(V²) space regardless of how many edges actually exist. If you have 10,000 vertices but only 50,000 edges, an adjacency list uses space proportional to ~60,000 items, while a matrix wastes space for 100,000,000 cells!

The Analogy

Imagine tracking friendships in a school:

  • Adjacency matrix: Print a giant grid with every student's name on both axes, check or leave blank each cell (wastes paper for non-friends)
  • Adjacency list: Each student carries a list with only their actual friends' names (efficient!)

Key Takeaway: Adjacency lists achieve O(V+E) memory efficiency by storing only what exists, making them ideal when E << V², which describes most practical graphs.