× {{alert.msg}} Never ask again
Get notified about new tutorials RECEIVE NEW TUTORIALS

Android Arraylist Size() anomaly

Xaver Kapeller
Mar 13, 2015
<p>It's always important to remember that <code>List</code> is just an interface. It contains all the methods which you would expect from a <code>List</code> but there is no default implementation for it. There are multiple classes that implement this <code>List</code> interface and they have different strategies on how to implement it. For example:</p> <ul> <li><code>ArrayList</code>: Uses an array to store the elements.</li> <li><code>LinkedList</code>: Holds two references for each element in the list, one to the previous item and one to the next item.</li> <li><code>Vector</code>: Also uses an array internally, but all operations are synchronised and therefore thread-safe.</li> <li><code>Stack</code>: Subclass of <code>Vector</code>, but uses a LIFO (Last In, First Out) data structure.</li> </ul> <p>You are asking why even though <code>size()</code> returns 15 there are 18 elements in the <code>ArrayList</code> when you look at it with the debugger. This is a consequence of how the <code>ArrayList</code> is implemented, as I told you above there is no such thing as a <code>List</code>, the <code>ArrayList</code> is just a wrapper around an array.</p> <p>You might ask now: "But why is it bigger in the first place?". The answer to that is one simple thing: <strong>Performance</strong>. To understand the reason you just have to imagine what happens internally in an <code>ArrayList</code> when you add items, I will demonstrate this with a few lines of pseudo code.</p> <p>Think about when the <code>ArrayList</code> is created:</p> <pre><code>ArrayList&lt;String&gt; list = new ArrayList&lt;String&gt;(); </code></pre> <p>The <code>ArrayList</code> does not know at this point how many elements will be added to it, so what is happening internally to the array? When we declare an array it has to have a size, so some arbitrary size is picked, maybe 4:</p> <pre><code>String[] array = new String[4]; </code></pre> <p>In reality the <code>ArrayList</code> will probably pick a number larger than 4 initially. This is just for demonstration purposes. So what we have now is an <code>ArrayList</code> with 0 items in it, but the array it uses to save those items has already a size of 4. If you looked at it with a debugger at this time you would see 4 spots in the array of the <code>ArrayList</code>, but all would be null. If you called <code>size()</code> now it would return 0. Because there are no items in the <code>ArrayList</code>. That there are 4 spaces in the array has nothing to do with amount of items actually stored.</p> <p>So now we begin to add items, maybe the letters <code>"a"</code> up to <code>"e"</code>:</p> <pre><code>list.add("a"); list.add("b"); list.add("c"); list.add("d"); list.add("e"); </code></pre> <p>Internally it just assigns this object to one free space in the array, first the <code>"a"</code>:</p> <pre><code>array[0] = "a"; </code></pre> <p>So after adding <code>"a"</code> we have it at the first position in our array, but the other 3 places are still empty. If you were to place a breakpoint on <code>list.add("b");</code> you would see that the first item in the array is <code>"a"</code> and the 3 spaces after that are null. If you were to call <code>size()</code> at this point it would return 1, because there is 1 item in the <code>ArrayList</code>. So we continue to add items and they are assigned to the internal array:</p> <pre><code>array[1] = "b"; array[2] = "c"; array[3] = "d"; </code></pre> <p>Everything is fine until <code>"d"</code>, but when we want to add <code>"e"</code> we hit a snag. We initially just picked a size of 4 for our array. So after adding <code>"a"</code>, <code>"b"</code>, <code>"c"</code> and <code>"d"</code> the array is full, we cannot add another item to it. What the <code>ArrayList</code> does in this case is create a new array with twice the size - in our case 8 because the previous size was 4 - and copies all the items from the previous array to the new one:</p> <pre><code>String[] biggerArray = new String[array.length * 2]; for(int i = 0; i &lt; array.length; i++) { biggerArray[i] = array[i]; } </code></pre> <p>After this there is no problem assigning <code>"e"</code> to a free space in the array:</p> <pre><code>biggerArray[4] = "e"; </code></pre> <p>But what we again have after the adding is finished is an <code>ArrayList</code> with 5 elements, but the array used to save those elements has a size of 8. So again if you were to add a breakpoint after the adding is finished you would see an array with the size 8 in the <code>ArrayList</code>, the first 5 spots would be occupied by the letters <code>"a"</code>, <code>"b"</code>, <code>"c"</code>, <code>"d"</code> and <code>"e"</code> but the remaining 3 are not currently used and would be null. If you called <code>size()</code> at this point it would return 5, because there are 5 elements in the <code>ArrayList</code>. Again <code>size()</code> has nothing to do with the size of the array used to store the elements, but returns the actual amount of items in the <code>ArrayList</code>.</p> <h1>Conclusion:</h1> <p>And finally we come to the point I was trying to make and why this is all a performance issue:</p> <p>If we can just resize the array why is it not the always exactly the size of the items in it and resized only when we add an additional item? Because as I should above, each time the array has to be resized you need to copy all the items from the old array to the new one. This can be an expensive and time consuming process, especially when you have hundreds or maybe even thousands of items in the <code>ArrayList</code>. So at the start some arbitrarily large size for the array is picked and then every time the array fills up it is doubled in size, hoping that this doubling in size is enough to not have to resize it again any time soon, leaving half the places in the array filled with an item and all the others empty.</p> <p>As you might already have noticed you can among other things pass a capacity to the <code>ArrayList</code> in its constructor:</p> <pre><code>ArrayList&lt;String&gt; list = new ArrayList&lt;String&gt;(100); </code></pre> <p>If you do this than the internal array will already be initialised with the capacity you want. This is for the case that you already know or at least have a vague idea how many items you are going to add to the <code>ArrayList</code>. By doing this you can prevent the internal resizing of the array and items can be added to the <code>ArrayList</code> a lot quicker! This is also a great way to see the effects of the <code>ArrayList</code> being internally an array. Initialise an <code>ArrayList</code> like above with a capacity 100 and when you add a breakpoint after that you will see that the internal array has a length of 100.</p> <p>If you have any further questions, feel free to ask!</p> <p>This tip was originally posted on <a href="http://stackoverflow.com/questions/23636887/Android%20Arraylist%20Size()%20anomaly/23639266">Stack Overflow</a>.</p>
comments powered by Disqus