java - 从 LinkedList 的开头删除所有

Question

我正在浏览 LinkedList API对于 Java 7 并注意到一些奇怪的事情。似乎没有“删除之前(或之后)”类型的方法。例如，如果我有一个 100 元素的 LinkedList，我想删除前 20 个元素，Java 似乎强制你一次删除一个，而不是将起始指针移动到第 21 个元素并删除 20 个元素之间的链接和 21. 看起来这是一个可以在 O(1) 时间内完成的操作，而不是 O(n) 时间，因为 Java 似乎强制你这样做。

我是不是遗漏了什么，或者这只是 Java 中一个明显的漏洞？

编辑

我知道 List 接口(interface)中的 sublist(int, int) 方法。我仍然认为这比通用的“砍掉第一个(或最后一个)n”用例的效率略低。

编辑 2

感谢所有指出找到第 n 个元素不是 O(1) 的人。不管砍掉前 n-1 个元素是否容易，找到第 n 个元素仍然需要 O(n) 的时间。

但是，正如 Dilum Ranatunga 指出的那样，迭代器有可能已经存在于给定位置。在这种情况下，说“我在这里，把我前面的都删除”仍然有用。

Answer 1

无论你做什么，它仍然是一个 O(n) 操作。

您无法直接访问链表的各个节点，因此您必须先遍历链表才能访问第 21 个节点。一旦你到达那里，“重新排列”列表的时间将是 O(1)，但对于整个原子操作，它仍然是 O(n)。