我在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**