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

Memory Layout and Cache Performance

Understand how array-based adjacency matrices offer better cache locality than pointer-based lists.

Memory Layout and Cache Performance

What You'll Learn

You'll understand why array-based adjacency matrices offer better cache locality than pointer-based adjacency lists, making them faster for certain graph operations despite using more memory.

How Your Computer Actually Accesses Memory

When your CPU needs data, it doesn't fetch one byte at a time from RAM—that would be too slow. Instead, it loads entire cache lines (typically 64 bytes) at once. Think of it like ordering groceries: you don't make a separate trip for each item; you fill a cart and bring everything home together.

Arrays: The Neighborhood Block Party

An adjacency matrix stores all graph data in one continuous array. When you access matrix[i][j], nearby elements like matrix[i][j+1] and matrix[i+1][j] are likely already in your CPU cache because they sit right next to each other in memory.

Iterating through a row to find all neighbors? Your CPU loads chunks of the row into cache proactively, making subsequent accesses lightning-fast. This is called spatial locality—accessing nearby memory locations in sequence.

Linked Lists: The Scattered Treasure Hunt

An adjacency list using pointers scatters nodes across memory like houses in different neighborhoods. Each neighbor node might live at a completely random memory address. When you traverse edges, each pointer dereference could trigger a cache miss—forcing the CPU to fetch from slow RAM instead of fast cache.

Following 10 edges means potentially 10 separate, unpredictable memory locations—no opportunity for the cache to help you.

The Performance Impact

For dense graphs or operations that scan many edges sequentially, the matrix's cache-friendly layout can outperform lists even though it uses O(V²) space versus O(V+E). Modern processors love predictable, contiguous memory access patterns.

Key Takeaway: Array-based adjacency matrices provide superior cache locality through contiguous memory layout, making them faster than pointer-based adjacency lists for memory-intensive traversals—modern CPU architecture rewards predictable access patterns.