Why Java ArrayLists are not compressed automatically

Question

Once upon a time, I watched a video lecture from the Princeton Coursera MOOC: an introduction to the algorithms that can be found here . It explains the cost of resizing an ArrayList structure when adding or removing elements from it. It turns out that if we want to resize our data structure, we will move from O(n) to amortized O(n) for add and remove operations.

I have been using Java ArrayList for several years. I was always sure that they grow and contract automatically. Only recently, to my great surprise, did I turn out to be wrong in this post . Java ArrayList do not shrink (although, of course, they do grow) automatically.

Here are my questions:

• In my opinion, providing a reduction in ArrayList does no harm since the performance is already amortized O(n) . Why didn't the Java creators include this feature in the project?

• I know that other data structures, such as HashMap , also do not shrink automatically. Is there any other data structure in Java that is built on top of arrays that support auto-reduction?

• What are the trends in other languages? How automatic reduction looks in the case of lists, dictionaries, maps, sets in Python / C #, etc. If they go in the opposite direction to what Java does, then my question is: why?

Answer 1

Comments already cover most of what you ask. Here are some considerations for your questions:

• When creating a structure such as an ArrayList in Java, developers make certain decisions regarding runtime / performance. They obviously decided to eliminate the reduction from "normal" operations in order to avoid the extra lead time that was needed.

• The question is why you want to automatically shrink. ArrayList does not grow much (more precisely, the coefficient is 1.5; newCapacity = oldCapacity + (oldCapacity >> 1) ). Perhaps you are also pasting in the middle, and not just adding at the end. Then a LinkedList (which is not based on an array -> lack of reduction) might be better. It really depends on your use case. If you think that you really need everything that an ArrayList does, but when you delete items, it should shrink (I doubt you really need it), just extend the ArrayList and override the methods. But be careful! If you contract each time you delete, you will return to O(n) .

• C # List and C ++ vector behave the same with respect to shortening the list when deleting items. But auto-growth factors vary. Even some Java implementations use different factors.