ewo*_*wok 2 java linked-list java-7
我正在浏览Java 7 的LinkedList API,并发现了一些好奇的东西.似乎没有"删除之前(或之后)"类型的方法.例如,如果我有一个100元素LinkedList,并且我想删除前20个元素,Java似乎强制您一次删除一个元素,而不是将开始指针移动到第21个元素并删除20之间的链接看起来这是一个可以在O(1)时间内完成的操作,而不是O(n)时间,因为Java似乎迫使你这样做.
我在这里遗漏了什么,还是只是Java中的一个明显漏洞？
编辑
我知道sublist(int, int)List接口中的方法.我仍然认为这比通用的"砍掉第一个(或最后一个)n"用例的效率略低.
编辑2
所有指出找到第n个元素的人都不是O(1).无论切断前n-1个元素的容易程度如何,找到第n个元素仍需要O(n)时间.
然而,正如Dilum Ranatunga指出的那样,在给定位置存在迭代器的可能性.在这种情况下,说"我在这里,在我之前删除所有"仍然是有用的.
无论你做什么,它仍然是O(n)操作.
您无法直接访问链接列表的各个节点,因此您必须首先遍历列表才能访问第21个节点.一旦你在那里,O(1)就会"重新排列"列表,但它仍然是整个原子操作的O(n).
| 归档时间： |
|
| 查看次数： |
267 次 |
| 最近记录： |