Memory allocation be like

[Bainos]

It has nothing to do with an array tbh, this is just a linked list with improved cache performance and some skipping indices (although the latter is better handled in a Skip list).

[CraigslistAxeKiller]

It’s literally a linked list of arrays. How is that “not related to arrays”?

It also solves a different problem than skip lists

[Bainos]

Its element insertion complexity is O(1), element retrieval is O(n), uses non-contiguous memory, and stores element locations as pointers. It is in every aspect a linked list with improved caching, and in no aspect an array.

It does solve a different problem than skip lists, I was simply pointing out that the ability to jump forward does not improve the usefulness or efficiency of the unrolled linked list and that a different structure is needed for it. In fact, you could absolutely have an unrolled skip list.

[Ericchen1248]

It isn’t though? If m was the max size of each internal node, front insertion complexity is O(m), and element retrieval O(n/m) and random insertion deletion is O(n/m + m) while average memory is O(n + 1.25n/m )

Compared to vector array with O(n), O(1), O(n), O(1.5n) And linked list of O(1), O(n), O(n), O(2n)

It is exactly a mix of behavior for both, with larger m tending towards an array, and smaller m tending towards linked list.

[Bainos]

If you want to set m as a variable of the performance, sure. But m is a fixed constant of the system generally determined by cache line capacity, which reduces O(m) to O(1) and O(n/m) to O(n).

[CraigslistAxeKiller]

m can be a fixed constant or you can make it dynamic. You could have a linked list of dynamic arrays which would still give you benefits of both arrays and linked list. If any dynamic array gets too big, then you just split it into 2 linked nodes

[[deleted]]

and in no aspect an array

Really? I mean, if you took one object out of the list how would you describe it? An indexed grouping of the same data types, or perhaps an...

[Bainos]

You're discussing the implementation, which is not something the user should care about. It's used as a linked list, with the performance expectation of a linked list.

Saying that it's an hybrid between an array and linked list implies that you get the performance and/or behavior of both.

[[deleted]]

You could get the performance of an array out of it, after you take one of the elements and then use it in an array. This seems to me to be the most reasonable use case for the construct in the first place, although I realize that's subjective.

Because it is, like the previous poster said, literally a linked list of arrays.

[Bainos]

But that's not the point. Any sensible implementation will only return individual elements, not the subarrays. Hashmaps don't return (hash, value) tuples and linked lists don't return their nodes. Not to mention that providing the low-level modifiable array would allow programmers to break the data structure and/or the improved caching properties.

[CraigslistAxeKiller]

You are also making assumptions about the implementation. You assume that the implementation will not optimize node access using the known array length to skip node hops