我正在浏览 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 指出的那样，迭代器有可能已经存在于给定位置。在这种情况下，说“我在这里，把我前面的都删除”仍然有用。
最佳答案
无论你做什么，它仍然是一个 O(n) 操作。
您无法直接访问链表的各个节点，因此您必须先遍历链表才能访问第 21 个节点。一旦你到达那里，“重新排列”列表的时间将是 O(1)，但对于整个原子操作，它仍然是 O(n)。
关于java - 从 LinkedList 的开头删除所有，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11546949/