-2

I have searched for ArrayList capacity questions but could not find a complete answer. so asking it again here.

I understand that size the number of elements we add in ArrayList and capacity is how much data we can put in that list with the default value to be 10.

So the question here is while declaring if give the capacity to be like this

List<String> list = new ArrayList<>(1);

Then also I can keep on adding the elements up to 10 or 20. So is this capacity declaration useful only to internal reallocation which happens when it reaches the capacity?

Or by giving the capacity limit can we restrict only to that point of add elements?

Yash
  • 11,486
  • 4
  • 19
  • 35
Mohan Kumar
  • 29
  • 1
  • 4
  • `So is this capacity declaration useful only to internal reallocation which happens when it reaches the capacity` Just read [javadocs](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#ArrayList-int-) – rkosegi Nov 01 '17 at 08:50
  • 4
    Well, your test answered the question, didn't it? Since you were able to add more than 1 element, it can't possibly be the second option. The javadoc also answers it. Why not read it? https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html : *The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically* – JB Nizet Nov 01 '17 at 08:51

3 Answers3

5

The initial capacity doesn't determine how many elements you can add to the ArrayList. The capacity is automatically increased when necessary as elements are added.

The motivation to specify an initial capacity is performance. If you know that your ArrayList will contain a million elements, it's more efficient to create the ArrayList with an initial capacity of 1000000, since that will save the need to resize the ArrayList capacity multiple times as elements are added.

Eran
  • 387,369
  • 54
  • 702
  • 768
  • I doubt the difference in performance would even be measurable. It would be a few microseconds at best I think, and specifying an initial capacity clutters the code. – David Conrad Nov 01 '17 at 08:57
  • 1
    @DavidConrad each time the capacity is increased, a new larger backing array is generated and initialized with the contents of the old array. When these arrays become large, the performance difference may start getting measurable. – Eran Nov 01 '17 at 09:01
  • @Eran Thanks for the info.. as David said i also used just adding 10-20 elements so didn't find any differnce hence posted this question. as u explained now understood the point – Mohan Kumar Nov 01 '17 at 09:07
  • That's why it would take a few microseconds. You should profile it with jmh. – David Conrad Nov 01 '17 at 09:12
  • 2
    @DavidConrad Specifying an initial capacity is definitely measurable with jmh, even at relatively small sizes (around 100). The speedup provided by specifying the correct initial capacity seems to be 20%-40% across wide range of sizes. Whether this speedup is *significant* is a different question, though. For most cases it probably doesn't matter. – Stuart Marks Nov 01 '17 at 17:55
  • 2
    Another reason to specify initial capacity is to save space. If you know you're going to be creating a lot of small (< 5) element lists, you can save a lot of space compared to the default capacity of 10 elements. – Stuart Marks Nov 01 '17 at 17:56
1

ArrayList are backed by an array which max size is Integer.MAX_VALUE - 8.

This is referred in these answers:

greg
  • 306
  • 1
  • 13
0

ArrayLists and other collections will grow as their capacity is used up. However how they do this depends on what data-structures are used 'behind the scenes'

An array list is backed by a Java Array. When that array is close to being filled a new Array is created, normally with twice the capacity, then all the elements are copied from the old to the new array, and the ArrayList then points at the new array.

Since the arrays double each time, adding an element to an array is still a constant time operation or "O(1)" in bigO notation. It is done in "amortized time"

However if you know your ArrayList is likely to contain n elements, you can declare it with an initial size of n. This makes the initial Array big enough to hold the elements you expect it to without having to do any "resizing". (Creating bigger arrays and copying elements over).

However it's not an issue if you underestimate n as the ArrayList will still grow to handle the extra elements.

Spangen
  • 4,420
  • 5
  • 37
  • 42