A List implementation that is optimised for remove(int index)

Question

I want to use a List<E> but the only method I'm ever going to use is

E remove(int index)

I am interested in the return value of this method (the E removed). I never need the method remove(E e).

The only constructor I'll ever need is one taking a Collection<? extends E>.

If List is an ArrayList, the remove(int index) method has time complexity O(n) because you have to shuffle the elements after the removed element one place to the left.

If List is a LinkedList, the remove(int index) method also has time complexity O(n) because although it takes O(1) time to change the links at an element, you have to find the element at index index by transversing the List.

If I'm only interested in using the remove(int index) method, is it possible to write an implementation of List<E> that it optimised for this method, so that the remove(int index) method has time complexity better than O(n)?

Answer 1

I would suggest using the TreeList from apache's commons-collections.

It is optimized such that

This list implementation utilises a tree structure internally to ensure that all insertions and removals are O(log n).

Answer 2

You can use a TreeList. While Java does not have a implementation of it, you can use Apache Commons TreeList. You can check that it is intent to be performant on insert and removes at the middle of it.