1. How ArrayList is structured
ArrayList is the Java class used most commonly for storing elements. So how does ArrayList work and why does everyone like it so much?
The structure of ArrayList is simple and ingenious. Each ArrayList object contains two fields:
- An array of elements
- A
sizevariable, which stores the number of elements in the list
Internally, an ArrayList object contains a most ordinary array! But that's not all. There is also a size variable, which stores the length of the list. This is how it works:
Initially, the length of the array inside the list is 10. And the size variable is 0.
If you add an element to the list, it will be stored in the 0th cell of the array, and size will increase to 1.
If you add one more element, it will be stored in the 1st cell, and size will again increase by 1 and become equal to two.
If you add another element when there is no more space in the array, then the following happens in the add() method:
- A new array is created that is one and a half times the length of the previous one
- All the elements of the old array are copied into the new array.
- In the
ArrayListobject, a reference to the new array replaces the reference to the old one. - The passed element is saved in the 10th cell of the new array.
- The size variable increases by 1 and will now equal 11
Something similar happens when adding (inserting) an element in the middle of the list. The existing elements are shifted by 1 to the right, and the passed element is written to the newly freed cell of the array.
Now we'll consider the most basic scenarios involving lists:
2. Adding an element to an ArrayList
Let's take a look at what happens inside the list when elements are added to it. Immediately after an ArrayList object is created, we have something like this in memory:
We have an ArrayList object that contains two fields (two variables): a container (the data array) and the number of stored elements (size). The data variable stores a reference to a container (array) that can store 10 elements.
If we decide to add the number 5 to the array, we get the following picture:
The array now stores the element 5, and size == 1.
If someone calls the size() method on our ArrayList object now, the return value will be the number of elements stored in the list: 1. The number of elements in the list is not the same as the storage capacity of the array.
Neither the current storage capacity nor the array itself will ever be accessible (visible) outside the ArrayList object. This is and always will be the ArrayList's internal data.
Let's add 7 more numbers to the list: 10, 20, 30, 40, 50, 60, 70.
Now memory will look like this:
If you call the size() method now, it will return the number 8, which is the new number of elements in the list. This value has nothing to do with the size of the internal array.
There is one oversimplification in this picture.
The ArrayList class can't store primitive types, so it uses the Integer type rather than int. The container does not directly store the values {5, 10, 20, 30, 40, 50, 60, 70}, but rather references to Integer objects. All the empty cells in the container store null.
3. Increasing the length of a list
Let's take a look at what happens inside a list when there are no more empty cells in its internal array.
Suppose we have a list of 10 elements:
We decide to add the number 100 to it. This is what happens in the add() method:
Step 1 — Create a new array:
Step 2 — Copy all elements from the old array to the new one:
Step 3 — Replace the old array (change the reference to the ArrayList object's internal array):
Step 4 — Add the new number, which is what we worked so hard to accomplish:
GO TO FULL VERSION