Removing range (tail) from a List

Question

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.

Answer 1

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 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.

Answer 2

Be aware that subList() returns a view of the original list, meaning:

1. Any modification done to the view will be reflected in the original list
2. The returned list is not a LinkedList - it's an inner implementation of List that's not serializable

Anyway, using either removeFirst() or removeLast() should be efficient enough, because popping the first or last element of a linked list in Java is an O(1) operation - internally, LinkedList holds pointers to both ends of the list and removing either one is as simple as moving a pointer one position.

For removing m elements at once, you're stuck with O(m) performance with a LinkedList, although strangely enough an ArrayList might be a better option, because removing elements at the end of an ArrayList is as simple as moving an index pointer (denoting the end of the array) one position to its left, and no garbage nodes are left dangling as is the case with a LinkedList. The best choice? try both approaches, profile them and let the numbers speak for themselves.