GlueList – Fast New Java List Implementation

Iteration will be slower than Arraylist.<p>Just like LinkedList (which is even worse), there will be cache misses on jumps to new nodes.<p>Random access lookup will be (very slightly) slower as you determine which node to look inside.<p>This is hardly a new datastructure. Just one that&#x27;s been thought of before and not standardized due to lack of compelling performance differentiation.

I&#x27;m scepctical if I just read &quot;fastest X&quot;. Fastest at what? Here it seems it is way faster at adding elements. But what about moving elements, sorting, searching, deleting? In most optimizations you get faster in one operation and slower in some others.<p>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.<p>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.

Seems like a java implementation of std::deque <a href="http:&#x2F;&#x2F;en.cppreference.com&#x2F;w&#x2F;cpp&#x2F;container&#x2F;deque" rel="nofollow">http:&#x2F;&#x2F;en.cppreference.com&#x2F;w&#x2F;cpp&#x2F;container&#x2F;deque</a>

Is this a unrolled linked list implementation? <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Unrolled_linked_list" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Unrolled_linked_list</a>

This is fine and dandy, until your list becomes heavily fragmented. Suddenly traversing your list becomes a series of expensive cache misses.<p>So it&#x27;s not &#x27;faster&#x27;, it depends very much on the use case - like any data structure.

some thoughts:<p>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).<p>the test of appending is faster. but is it? I would offer that it&#x27;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.<p>worse case complexity seems incorrect for worse case search and access. assuming bins, you&#x27;d have to traverse the bin as well, so access should be O(m+n) .<p>but what about a remove test, or an actual search test? this looks somewhat like a b-tree.

What&#x27;s old is new again:<p><a href="http:&#x2F;&#x2F;javolution.org&#x2F;" rel="nofollow">http:&#x2F;&#x2F;javolution.org&#x2F;</a><p>This library has been around forever, and extends the same concept to other collection types.

It seems this may have been done already: have you looked at Clojure data structures implementations? Most, e.g vector, use a 32-branching factor with constant access&#x2F;upate time. Clojure data types are all accessible from Java. Check it out: <a href="http:&#x2F;&#x2F;clojure.org&#x2F;reference&#x2F;data_structures#Vectors" rel="nofollow">http:&#x2F;&#x2F;clojure.org&#x2F;reference&#x2F;data_structures#Vectors</a>

Bad title. Datastructures always come with trade offs. In this case Insertion Speed and memory efficiency vs iteration and random access Speed.

Why is everything in the root namespace? Have you used this library for any real-life project?<p>Try something like sort for a benchmark.

In addition to what everyone else has said, ArrayList may get faster with a Java update.

This makes me wish I could downvote things on HN. This is not new, nor is there any significant evidence that it&#x27;s &quot;fastest&quot; (a term that doesn&#x27;t really mean much without context anyway).

The benchmarks do not use caliper or jmh. This is _very_ important - microbenchmarks on the JVM rarely do what you think they do without extra work.

Using sun.misc.Unsafe to access array elements would make it much faster. Also ArrayList with preset size is faster for inserting elements.