Effective Java Item 17: How can overriding removeRange() improve performance?

Question

In the book Effective Java by Joshua Bloch, there is a discussion on how a class can provide "judiciously chosen protected methods" as hooks into its internal workings.
The author then cites the documentation in AbstractList.removeRange():

This method is called by the clear operation on this list and its subLists. Overriding this method to take advantage of the internals of the list implementation can substantially improve the performance of the clear operation on this list and its subLists.

My question is, how can overriding this method improve performance (more than simply not overriding it)? Can anyone give an example of this?

Answer 1

Let's take a concrete example - suppose that your implementation is backed by a dynamic array (this is how ArrayList works, for example). Now, suppose that you want to remove elements in the range [start, end). The default implementation of removeRange works by getting an iterator to position start, then calling remove() the appropriate number of times.

Each time remove() is called, the dynamic array implementation has to shuffle all the elements at position start + 1 and forward back one spot to fill the gap left in the removed element. This could potentially take time O(n), because potentially all of the array elements might need to get shuffled down. This means that if you're removing a total of k elements from the list, the naive approach will take time O(kn), since you're doing O(n) work k times.

Now consider a much better approach: copy the element at position end to position start, then element end + 1 to position start + 1, etc. until all elements are copied. This requires you to only do a total of O(n) work, because every element is moved at most once. Compared with the O(kn) approach given by the naive algorithm, this is a huge performance improvement. Consequently, overriding removeRange to use this more efficient algorithm can dramatically increase performance.

Hope this helps!