Just like LinkedList (which is even worse), there will be cache misses on jumps to new nodes.

Random access lookup will be (very slightly) slower as you determine which node to look inside.

This is hardly a new datastructure. Just one that's been thought of before and not standardized due to lack of compelling performance differentiation.

(1) A sufficiently smart compiler could, in some cases, convert a data structure that logically uses reference types into one that uses value types in the compiled code (I think that's highly hypothetical in this case, as it almost isn't worth spending time on for compiler writers, given that it will be possible very rarely)

And if you decide to optimize one operation over the others some usecases for that would be great as well. The most expensive things I needed to do with lists were sorting. Having a list type that improves this operation over the others would be most reasonable for me.

Last but not least I think the List is such an old and often used data structure, it is very unlikely one can develop something a lot faster.

According to the README, it only uses 36 nodes for 10 Million records, so I guess it is like Unrolled linked lists but with a higher limit of elements per node?

You can say 'allocate me 10million elements' and there will be 1 node :)

So it's not 'faster', it depends very much on the use case - like any data structure.

IIRC the train algorithm used in some JVMs improves locality. Most GCs use a pointer-bump scheme anyways, leading to pretty good locality for objects that have been created together.

So yes, the JVM _may_ have some pretty cool mechanisms to minimize those. I would be also interested in G1s behavior and whether or not it improves locality somehow.

remove and add worst case complexity is O(mn) ! that is terrible, linked list should be able to do inserts and removes in O(1).

the test of appending is faster. but is it? I would offer that it's likely java doing some more datatype and bounds checking in their implementations, which is inline with the marginal speedup and relatively linear growth complexity. furthermore there are resize effects that will happen periodically as big malloc+move events.

worse case complexity seems incorrect for worse case search and access. assuming bins, you'd have to traverse the bin as well, so access should be O(m+n) .

but what about a remove test, or an actual search test? this looks somewhat like a b-tree.

That assumes you have a reference to the node, which isn't true in Java's LinkedList, as the nodes are encapsulated. The remove() operation in List either takes the object you want to remove (by equality) or an index. Both require an O(n) scan to find the node, then it can be removed in O(1).

[0] https://news.ycombinator.com/item?id=12274657

http://javolution.org/

This library has been around forever, and extends the same concept to other collection types.

Try something like sort for a benchmark.

sun.misc.Unsafe should not make any difference to performance here. OK, you skip bounds checks, but modern VMs are very good at optimising those away anyway.

Also ArrayList with preset size is faster for inserting elements.

Exactly what I was thinking. The only case this is really going to help is where you don't have an idea of what the size is going to be.