I'm not convinced. I obviously can't say what I'd do if I had to think these up, but I think I'd be more likely to try and impart ordering on a contiguous array

I'm not convinced. I obviously can't say what I'd do if I had to think these up, but I think I'd be more likely to try and impart ordering on a contiguous array than building a multiple-allocation one. Going down this route would probably result in a contiguous linked list. You can argue that this is still a linked list, but I still find it conceptually more obvious. For a billion elements, it's probably also a lot faster, too.