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.
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.
Comments
It's a bit like row vs column store.
If there are two lists, in the first example, you're doing:
In the 2nd example, you're doing 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.