[tayo42]

The interleave thing isnt intuitive to me.

The problem with linked lists is the memory address of nodes isn't necessarily contiguous because of malloc and the value could be NULL? Why does interleave loop make it faster for the cpu? It still a linked list, arbitrary memory, could be NULL? Not sure what im missing here?

[latch]

It's a bit like row vs column store.

If there are two lists, in the first example, you're doing:

    a1 -> b1 -> c1 -> d1
    a2 -> b2 -> c2

In the 2nd example, you're doing

    [a1, a2]
    [b1, b2]
    [c1, c2]
    [d1]

Visiting the same number of nodes, but because the nodes are referenced from an array, when you load `a1` you're [probably] also going to load `a2` into the cache.

[lossolo]

> Visiting the same number of nodes, but because the nodes are referenced from an array, when you load `a1` you're [probably] also going to load `a2` into the cache.

Yep, the problem with a linked list is that you don't know the address of the next pointer, it could be allocated anywhere. However, if you have a continuous array, when you read the first item, you're also fetching the next items in the cache line.