针对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是LinkedList，则remove(int index)方法也具有时间复杂性O（n），因为尽管更改元素处的链接需要O（1）时间，但必须通过对List进行转换来找到索引index处的元素。

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

Answer 1

我建议使用apache的commons集合中的TreeList。

经过优化，

此列表实现在内部使用树结构来确保所有插入和删除都是O（logn）。

Answer 2

您可以使用TreeList。虽然Java没有它的实现，但您可以使用Apache Commons TreeList。您可以检查它是否有意在插入时执行，并在插入中间删除。

Answer 3

如果您不关心排序的更改，您可以在O（1）中使用数组进行移除，方法是将要移除的元素与最后一个元素交换。

例如，

@Override
public E remove(int index) {
    int size = size();
    if(index < 0 || size <= index) {
        throw new IndexOutOfBoundsException(String.valueOf(index));
    }
    E last = super.remove(size - 1);
    return set(index, last);
}

（但是，请注意，这不是List接口指定的行为。）