[COLLECTIONS-672] There are no List collection with optimized indexOf method.

• Type: Improvement
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Component/s: Collection
• Assignee: Unassigned
• Reporter: Aleksandr Maksymenko
• Created: 28/Jan/18 13:46
• Updated: 19/Nov/20 05:45

Description

All known implementations of List are all have O( n ) for indexOf() operation.

Here is my implementation of such List on github which has O(log n) for indexOf() and contains():
https://github.com/masyamandev/indexable-set

There are two modifications: one implements both List and Set, so it can contains unique elements, second modification can contains any amount of unique objects, but it's a bit slower.

It's based on TreeList and provide complexity:

• get by index is O(log n)
• insertion, removing (both by index or by value) are O((log n) * (1 + log m)) where is amount of elements equals to inserted/removed element.
• insertion, removing are O(log n) if all elements are unique.
• indexOf and lastIndexOf are O(log n).
• contains is O(1) or (log n) depending on Map implementation.

As those collections have complexity similar to TreeSet (at least in cases of unique elements), overall performance is 20-30% slower due to element indexing and eliminating some optimizations. However it provides fast indexOf and contains.

Can I help in porting my code to Apache common Collections library?