java - 从列表中删除范围(尾部)

Question

是否有一种有效的方法可以从 List 中删除 X 元素的范围(例如尾部)，例如LinkedList 在 Java 中？

显然可以一个一个地删除最后一个元素，这应该会导致 O(X) 级别的性能。至少对于 LinkedList 实例，它应该有可能具有 O(1) 性能(通过设置要删除的第一个元素周围的引用并设置头/尾引用)。不幸的是，我在 List 或 LinkedList 中没有看到任何方法可以一次性删除最后一个元素。

目前我正在考虑使用List.subList() 替换列表但我不确定这是否具有相同的性能。至少在代码中会更清楚，另一方面我会失去 LinkedList 提供的附加功能。

我主要将 List 用作堆栈，其中 LinkedList 似乎是最好的选择，至少在语义方面。

Answer 1

subList(list.size() - N, list.size()).clear() 是删除最后一个 N 元素的推荐方法。确实，Javadoc for subList 特别推荐这个成语:

This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a list can be used as a range operation by passing a subList view instead of a whole list. For example, the following idiom removes a range of elements from a list:

 list.subList(from, to).clear();

确实，我怀疑这个习语可能比调用 removeLast() N 次更 更有效(尽管是一个常数因子)，只是因为一旦找到倒数第N个节点，它只需要更新链表中固定数量的指针，而不是更新最后N中每一个的指针 一次一个节点。