Java LinkedList：从中移除到

list.subList(1,4).clear();

正如Javadoc for java.util.LinkedList#subList(int,int)中所记录的那样.

检查完源代码后,我发现最终会逐个删除元素. subList继承自AbstractList.此实现返回一个List,当您在其上调用clear时,它仅在后备列表上调用removeRange. removeRange也是从AbstractList继承的,实现是

protected void removeRange(int fromIndex,int toIndex) {
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0,n=toIndex-fromIndex; i<n; i++) {
        it.next();
        it.remove();
    }
}

如您所见,这一次删除了一个元素. listIterator在LinkedList中被重写,它首先通过跟随链来查找第一个节点,方法是跟随列表开头或结尾的链接(取决于fromIndex是在列表的第一个还是后半个).这意味着list.subList(i,j).clear()具有时间复杂性

O(j - i + min(i,list.size() - i)).

除了你最好从最后开始并以相反顺序删除元素的情况之外,我不相信有一个明显更快的解决方案.测试代码的性能并不容易,很容易被错误的结论所吸引.

无法使用LinkedList类的公共API一次性删除中间的所有元素.这让我感到惊讶,因为使用LinkedList而不是ArrayList的唯一原因是你应该能够有效地从中间插入和删除元素,所以我认为这个案例值得优化(特别是因为它很容易编写).

如果您绝对需要O(1)性能,那么您应该可以从诸如此类的调用中获得

list.subList(1,list.size() - 1)).clear();

你要么必须编写自己的实现,要么用这样的反射做一些脆弱和不明智的事情：

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    for (int a = 0; a < 5; a++)
        list.add(a);
    removeRange_NEVER_DO_THIS(list,2,4);
    System.out.println(list);       // [0,1,4]
}

public static void removeRange_NEVER_DO_THIS(LinkedList<?> list,int from,int to) {
    try {
        Method node = LinkedList.class.getDeclaredMethod("node",int.class);
        node.setAccessible(true);
        Object low = node.invoke(list,from - 1);
        Object hi = node.invoke(list,to);
        Class<?> clazz = low.getClass();
        Field nextNode = clazz.getDeclaredField("next");
        Field prevNode = clazz.getDeclaredField("prev");
        nextNode.setAccessible(true);
        prevNode.setAccessible(true);
        nextNode.set(low,hi);
        prevNode.set(hi,low);
        Field size = LinkedList.class.getDeclaredField("size");
        size.setAccessible(true);
        size.set(list,list.size() - to + from);
    } catch (Exception e) {
        throw new RuntimeException(e);
    }
}