从列表中删除范围(尾部)
是否有一种有效的方法可以从 List 中删除 X 元素的范围(例如尾部)，例如LinkedList 在 Java 中?
Is there an efficient method to remove a range - say the tail - of X elements from a List, e.g. LinkedList in Java?
显然可以一个一个地删除最后一个元素，这应该会导致 O(X) 级别的性能.至少对于 LinkedList 实例，它应该有可能具有 O(1) 性能(通过设置要删除的第一个元素周围的引用并设置头/尾引用).不幸的是，我在 List 或 LinkedList 中没有看到任何方法可以一次性删除最后一个元素.
It is obviously possible to remove the last elements one by one, which should result in O(X) level performance. At least for LinkedList instances it should be possible to have O(1) performance (by setting the references around the first element to be removed and setting the head/tail references). Unfortunately I don't see any method within List or LinkedList to remove the last elements all at once.
目前我正在考虑替换使用 List.subList() 但我不确定这是否具有相同的性能.至少在代码中会更清楚，另一方面我会失去 LinkedList 提供的附加功能.
Currently I am thinking of replacing the list by using List.subList() but I'm not sure if that has equal performance. At least it would be more clear within the code, on the other hand I would loose the additional functionality that LinkedList provides.
我主要将 List 用作堆栈，其中 LinkedList 似乎是最好的选择，至少在语义方面.
I'm mainly using the List as a stack, for which LinkedList seems to be the best option, at least regarding semantics.
推荐答案
subList(list.size() - N, list.size()).clear() 是推荐的删除方式最后一个 N 元素.事实上，Javadoc对于subList 特别推荐这个成语:
subList(list.size() - N, list.size()).clear() is the recommended way to remove the last N elements. Indeed, the Javadoc for subList specifically recommends this idiom:
此方法无需显式范围操作(通常存在于数组中的那种).通过传递 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中每一个的指针 一次一个节点.
Indeed, I suspect that this idiom might be more efficient (albeit by a constant factor) than calling removeLast() N times, just because once it finds the Nth-to-last node, it only needs to update a constant number of pointers in the linked list, rather than updating the pointers of each of the last N nodes one at a time.
相关文章