What is the benefit of setting the capacity of an ArrayList explicitly

Question

In java ArrayList we have a constructor -

ArrayList(int capacity)

and two methods -

void ensureCapacity(int minCapacity)

void trimToSize()

Consider a code-sample:

ArrayList<String> arrayList3 = new ArrayList<>(5);
System.out.println(arrayList3.size());

arrayList3.add("Zebra");
arrayList3.add("Giraffe");
arrayList3.add("Bison");

System.out.println(arrayList3);
System.out.println(arrayList3.size());

arrayList3.add("Rhino");
arrayList3.add("Hippo");
arrayList3.add("Elephant");
arrayList3.add("Antelope");

System.out.println(arrayList3);
System.out.println(arrayList3.size());

Output:

0
[Zebra, Giraffe, Bison]
3
[Zebra, Giraffe, Bison, Rhino, Hippo, Elephant, Antelope]
7

Here, I fail to see how setting an initial capacity affects the execution of the program. ArrayList is a flexible list that changes size as per demand. So what is the significance of setting the capacity explicitly?

And in the case if I want to set the capacity explicitly, is there any method to view the current capacity? Since int size() clearly is not applicable here.

From the class docs: "An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation. " — tobias_k, May 17 '22 at 15:22
Look here https://www.baeldung.com/java-list-capacity-array-size#:~:text=ArrayList's%20size%20and%20capacity,make%20room%20for%20more%20elements. — Faheem azaz Bhanej, May 17 '22 at 15:27
Not sure how it's implemented but I'd guess, when the capacity is exceeded, it allocates a new backing array of larger (double?) size and copies all elements (their references) to the new array. If you know the capacity up front, you can skip that step (possibly multiple times). Also, it might save memory by not allocating too much "extra" space, but again, only guessing here... — tobias_k, May 17 '22 at 15:27
Is there any method to know the current set capacity? @tobias_k — Payel Senapati, May 17 '22 at 15:28
@tobias_k You are absolutely right. I was read this this thing once in article — Faheem azaz Bhanej, May 17 '22 at 15:29
@FaeemazazBhanej how to know the currently set capacity and not size in ArrayList? — Payel Senapati, May 17 '22 at 15:35
Hmm, seems only [Vector](https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html#capacity--) had `capacity()`, but they didn't bring it to `ArrayList`. Although it's internal information that isn't really any use for general programming, so it does make for a cleaner API. — Kayaman, May 17 '22 at 15:53
@PayelSenapati `how to know the currently set capacity and not size in ArrayList?` Call trimToSize(), then capacity == size. OK that's a little cheesy but I think the idea is that the user normally shouldn't worry about it. — markspace, May 17 '22 at 16:02
@Kayaman why not use Vector instead of ArrayList. I find Vector more useful in terms of flexibility in manually setting capacity. Also Vector has some more useful methods not present in ArrayList. — Payel Senapati, May 19 '22 at 11:59
@PayelSenapati if you're manually setting capacity a lot, then you're either working with a very peculiar workload, or you think that setting the capacity is more important than it really is. Even when I started writing Java at the time when 1.2 came out, I didn't feel like using `Vector` although it wasn't as deprecated as it is these days. — Kayaman, May 19 '22 at 13:44
@Kayaman Please have a look at my question - https://stackoverflow.com/questions/72305526/how-to-change-capacityincrement-value-post-initialization-in-vector — Payel Senapati, May 19 '22 at 13:47

Alexander Ivanchenko · Accepted Answer · 2022-05-18T02:37:21.000

ArrayList as an implementation of a Dynamic array data structure.

It resizes when its underlying array gets full (i.e. the current list index exceeds the last valid index of the underlying array).

When it happens, method add() (or addAll) internally will invoke the method grow(). Which will double the capacity. I.e. it will create a new array with the length two times bigger than the previous length plus a number of new elements that don't fit into the current size.

The growth has a cost of O(n) because all previously added elements need to be copied into the new array.

Reminder: when resizing isn't required, a new element will be added in constant time O(1).

No-argument constructor creates an ArrayList with capacity of 10.

If you expect that a newly created ArrayList would eventually contain let's say 50,000 elements, it makes sense to use an overloaded constructor to provide the initial capacity of 50,000 in order to improve performance by avoiding unnecessary resizing.

Also, for that you can use method ensureCapacity() which accessible in the ArrayList class (not in the List interface, because the notion of capacity isn't applicable to LinkedList which isn't backed by an array).

is there any method to view the current capacity

No, there isn't. That's called encapsulation. ArrayList, StringBuilder, HashMap, etc. are backed by a plain array, but they will not allow interacting with their underlying array directly.

But if you have a case when array initially increases size and then a lot of elements are being removed, and you want to release unoccupied heap space, you can use method trimToSize():

Trims the capacity of this ArrayList instance to be the list's current size. An application can use this operation to minimize the storage of an ArrayList instance.

But it has to be used with caution, because it can lead to cyclic growth and trimming, which will cause performance degradation.

Note that there's no need to worry about the amount of unoccupied space if the list is moderate in size, or if you are not expecting let's say 80% of the data to be removed in one go. I.e. even if the list is huge but 50% of its elements gets removed, and you apply trimToSize() on it, it'll restore its previous capacity with the next added element - that's the scenario of continuously growing and shrinking list which will perform badly.

As a possible option, if you heave a case when most of the data can be removed from a list, instead of using trimToSize() you can filter out the elements that have to be preserved, place them into a new list and dereference the previous one.

To use `ensureCapacity()` and `trimToSize()` a person who has not written the code has to go through early code to find out initially set capacity. This is a time-consuming inconvenient affair. A method like `int capacity()` would certainly be very convenient. I mark this as **drawback** of Java — Payel Senapati, May 17 '22 at 19:26
Just to be overly pedantic, it does not create a "new array with the length twice bigger than the previous length", as "twice bigger" would be three times the size. It is, as you said earlier, twice the size, or in "bigger" notation, "one time bigger". — GreyBeardedGeek, May 18 '22 at 00:56
@GreyBeardedGeek Thanks for pointing at this gaffe. I hope now it looks better. — Alexander Ivanchenko, May 18 '22 at 01:51
@PayelSenapati You don't have to worry about relatively small lists (what is small depends on your environment) but from the point of pure logic the smaller `ArrayList` is, the faster it grows. Because of that, it doesn't seem to be reasonable to try to trim it. Also note that cases of bulk removal should affect much more than `50%` of element, otherwise applying `trimToSize()` would be fruitless. As a possible remedy, you can filter out all the elements should be retained and store them into a new list. — Alexander Ivanchenko, May 18 '22 at 02:34

What is the benefit of setting the capacity of an ArrayList explicitly

1 Answers1