Perhaps naively, would a struct-of-arrays perform better than an array-of-structs? I imagine that the separate `next` and `data` arrays might be packed better, and instead of processing one cache line at a time, you could load two cache lines simultaneously to process double the sequential data with every round-trip to RAM.

More to the point of the discussion, it seems to me that you're describing situations where the cells of your container do have a natural inherent order, but may have additional relationships imposed on top of them. In the case of Algorithm X, the matrix has an inherent, consistent sense of order across rows and columns, but any particular line may skip elements depending on the state of the algorithm.

I think that doubly-layered structure is important to recognize; it's not something all data will have, and it's an inherent property of the problem or domain, not of the linked list data structure itself.