[bee_rider]

Hmm. What do we think about the alternative guess that the address of the next node’s value field is the next address after our current node’s value field memory address? This is, I guess, essentially a guess that we’re pointing at sequential elements of a big array, which sort of begs the question “why not just use an array?” But I’m wonder if a slightly permuted array is not so unusual, or at least might come up occasionally.

[mistercow]

I feel like there are a number of data structures that you might initially set up (or load in) in some preferred contiguous order, which will still remain largely contiguous after modification, so that you get a good tradeoff between cheap operations and fast traversal. You’d then have the option to do partial defragmentation at convenient times, without having to have a convoluted hybrid data structure. But it’s definitely something you’d do in specific critical cases after a lot of analysis.