一个针对remove（int index）优化的List实现

Question

我想使用一个，List<E>但我唯一要使用的方法是

E remove(int index)

我对此方法（已E删除）的返回值感兴趣。我永远不需要这种方法remove(E e)。

我唯一需要的构造函数是一个Collection<? extends E>。

如果List为ArrayList，则该remove(int index)方法具有时间复杂度O（n），因为您必须在将删除的元素向左移一个位置之后对元素进行随机排序。

如果List为a LinkedList，则该remove(int index)方法也具有时间复杂度O（n），因为尽管花费O（1）的时间来更改元素上的链接，但是您必须index通过遍历来找到索引处的元素List。

如果我只对使用该remove(int index)方法感兴趣，是否可以编写List<E>针对该方法优化的实现，以使该remove(int index)方法的时间复杂度优于O（n）？

Answer 1

我建议使用apache 的 commons-collections 中的TreeList 。

它经过优化使得

该列表实现在内部利用树结构来确保所有插入和删除都是 O(log n)。