Why does Java ArrayLists not shrink automatically

A long time ago, I watched a video lecture on coursera MOOC: introduction to Algorithms in Princeton. You can find here It explains the cost of adjusting an ArrayList like structure when adding or deleting elements It turns out that if we want to provide resizing for our data structure, we will move from O (n) to amortized o (n) for addition and deletion

I have been using java ArrayList for several years I've always been sure that they will grow and shrink automatically Just recently, to my surprise, I was proved wrong in this post year Java ArrayLists do not shrink automatically (of course, they grow)

This is my question:

>In my opinion, providing shrinkage in ArrayLists will not cause any damage because performance has been amortized o (n) Why didn't the Java creator include this feature in the design? > I know that other data structures like hashmaps will not shrink automatically Are there any other data structures in Java built on arrays that support automatic shrinking? > What are the trends in other languages? What does it look like if lists, dictionaries, maps, collections in Python / C # are automatically shrunk If they are the opposite of what Java does, then my question is: why?

Solution

The comments have covered most of your requirements Here are some thoughts on your question:

>When creating an ArrayList like structure in Java, developers make some decisions about Runtime / performance They clearly decided to exclude shrinkage in "normal" operation to avoid the need for additional running time. > The question is why you want to shrink automatically ArrayList will not grow that much (because it is about 1.5; newcapacity = oldcapacity (oldcapacity > > 1), to be exact) Maybe you also insert in the middle, not just add to the end Then, LinkedList (not based on array – > no need to shrink) might be better It really depends on your use case If you think you really need what ArrayList does, but it must shrink when deleting elements (I doubt you really need this), just expand ArrayList and override these methods But be careful! If you shrink every time you remove it, return o (n). > C #list and C vector shrink the list when deleting elements But the factors of automatic growth are different Even some Java implementations use different factors