Java LinkedList:从中移除到

Question

我在java.util.LinkedList逻辑上有一个包含数据

1 > 2 > 3 > 4 > 5 > null

我想删除2到4之间的元素,并使其LinkedList像这样

1 > 5 > null

实际上,我们应该能够以O(n)复杂度实现这一点,考虑到你必须将链断开为2并在一次操作中将它连接到5.

在Java LinkedList中,我无法找到任何允许在单个O(n)操作中使用from和to从链表中删除链的函数.

它只为我提供了单独删除元素的选项(使每个操作O(n)).

无论如何,我只需一次操作即可实现这一目标(无需编写自己的列表)？

这里提供的一个解决方案使用单行代码解决了问题,但不是单个操作. list.subList(1, 4).clear();

问题更多的是算法和性能.当我检查性能时,这实际上比逐个删除元素慢.我猜这个解决方案实际上并没有删除o(n)中的整个子列表,而是为每个元素逐个删除(每次删除O(n)).还要添加额外的计算来获取子列表.

以ms为单位的平均1000000次计算:

没有sublist = 1414
使用提供的子列表解决方案:= 1846**

Answer 1

一步到位的方法是

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

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

检查完源代码后,我发现最终会逐个删除元素.subList是继承自AbstractList.此实现返回一个List只removeRange在您调用clear它时调用支持列表的实现.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)).

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

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

如果你绝对需要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);
    }
}