Removing range (tail) from a List
collections, java, list, stack
Solution
`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:
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();
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 `N`th-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.
Problem
Is there an efficient method to remove a range - say the tail - of X elements from a `List`, e.g. `LinkedList` in Java? 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. 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. I'm mainly using the List as a stack, for which `LinkedList` seems to be the best option, at least regarding semantics.