Oleksandr Miadelets
Head of Developers Team at CodeGym

ArrayList in pictures

Published in the Java Developer group
Hi! Today's lesson about ArrayList will be both easier and harder than previous lessons.
ArrayList in pictures   - 1
It will be more difficult because today we're going to look under the hood of ArrayList and study what happens during various operations. On the other hand, this lesson will have almost no code. It's mostly pictures and explanations. Well, let's go:) As you already know, ArrayList has an ordinary array inside, which acts as a data store. In most cases, we don't specify the exact size of the list. But the internal array must have some size! And so it does. Its default size is 10.

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
ArrayList in pictures   - 2 First, let's see what adding new elements looks like. The first order of business is to check whether the internal array has enough space in the internal array and whether one more element will fit. If there is space, then the new element is added to the end of the list. When we say "to the end", we don't mean the last position in the array (that would be weird). We mean the position following the last current element. Its index will be cars.size(). Our list is currently empty (cars.size() == 0). Accordingly, the new element will be added at position 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
ArrayList in pictures   - 3 That's clear enough. What happens if we insert in the middle, i.e. between other elements?

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");
   cars.add(1, ford);// add ford to cell 1, which is already occupied
Again, first there is a check whether there is enough space in the array. If there is enough space, then the elements are shifted right, starting with the position where we're insert the new element. We're inserting at position 1. In other words, the element from position 3 is copied to position 4, element 2 to position 3, and element 1 to position 2. ArrayList in pictures   - 4 Then our new element is inserted in its place. The previous element (bugatti) has already been copied from there to a new position. ArrayList in pictures   - 5 Now let's look at how this process happens if there are no places to insert new elements into the array. ArrayList in pictures   - 6 Naturally, there is first a check to see whether there enough space. If there isn't enough room, then a new array is created inside the ArrayList whose size is the size of the old array times 1.5 plus 1 In our case, the new array's size will be 16. All the current elements will be copied to there immediately. ArrayList in pictures   - 7 The old array will be deleted by the garbage collector, and only the new, expanded array will remain. Now there's room for a new element. We're inserting it at position 3, which is occupied. Now the familiar procedure begins. All the elements, starting with index 3, are shifted one position to the right, and the new element is quietly added. ArrayList in pictures   - 8 And the insertion is done! And we're done with insertion. Now let's talk about removing items. You'll remember that we ran into a problem when working with arrays: removing elements makes "holes" in an array. The only way out was to shift items left with each removal, and we had to write our own code each time to perform this shift. ArrayList follows the same principle, but it already implements this mechanism. ArrayList in pictures   - 9 This is how it looks: ArrayList in pictures   - 10 And in the end we get what we want: ArrayList in pictures   - 11 The lambo element has been removed. Here we removed an element from the middle. Clearly, removing an element from the end of the list is faster, since the element is simply removed without the need to shift all the others. Let's talk again for a moment about the dimensions of the internal array and how it's arranged in memory. Expanding an array takes some resources. Accordingly, don't create an ArrayList with the default size if you're certain it will have at least 100 elements. The internal array would have to be expanded 6 times by the time you inserted the 100th element, and all the elements would have to be shifted each time.
  • from 10 elements to 16
  • from 16 elements to 25
  • from 25 to 38
  • from 38 to 58
  • from 58 to 88
  • from 88 to 133 (i.e. size of the old array times 1.5 plus 1)
As you can imagine, this is quite resource-intensive. ArrayList in pictures   - 12So, if you already know (even approximately) the required number of items, it's better to create a list with an array of a specific size:

ArrayList<Car> cars = new ArrayList<>(100);
Now the memory for an array of 100 elements will be allocated all at once, making the array more efficient (it won't need to be expanded). This strategy also has a flip side. When you remove objects from an ArrayList, the internal array's size does not decrease automatically. Suppose we have an ArrayList with an completely full internal array of 88 elements: ArrayList in pictures   - 12 As the program runs, we remove 77 elements, so only 11 remain: ArrayList in pictures   - 13 Have you already guessed what the problem is? You got it, inefficient use of memory! We're only using 11 positions here, but we've allocated memory for 88 elements. That's 8 times more than we need! In this case, we can optimize our memory use with one of the ArrayList class's special methods: trimToSize(). This method "trims" the length of the internal array down to the number of elements currently stored in it. ArrayList in pictures   - 14 Now we've only allocated as much memory as we need! :)
Comments (55)
Rodrigo Muniz Level 21, United States of America, Brazil
27 February 2023
Great topic and explanation!
Super Ego Level 14, Wu Han, China
15 February 2023
图多,英语渣看着也挺简单的。就是讲了ArrayList的扩容原理。新的ArrayList以10为固定值,每到内容满就 乘1.5 再 加1。但只会自动扩容不会收缩,删除其中元素不会让它复原。收缩要使用自带的trimToSize()方法。
Ocean Level 22, China, Hong Kong
31 July 2022
Tasmoda Level 28, Midrand, South Africa
13 May 2022
When I create an ArrayList without specifying its size. The default size is 10. Now when I add just 2 elements to my ArrayList and check the size, the size is 2. How did it move from size 10 at default to size 2? Did it trim to size automatically after I inserted my 2 elements?. Also, what is the reason for multiplying the current size by 1.5 and + 1 when I only want to add just 1 more element? Do I need to trim to size every time I add an element? It turns out that ArrayLists are not as dynamic as I initially thought. I imagined an ArrayList size to be the size of the elements entered plus one empty position at the end which is never filled. Every time you add an element there is a plus one added. (Look at me giving advises on how ArrayLists should work when I'm only 2 months into Java, such a nerve!😂).
Victor Omoha Level 8, Raleigh , United States
11 November 2021
that was epic
Eugenio Francioni Level 17, Berlin, Germany
18 September 2021
hm, I always thought, that an ArrayList internal is a single linked list which has an index-attribute, while a Linked List is a double linked list if an ArrayList would be an array, how could it be dynamic? So far I can see in Java it needs a length in order to instiating an array??
诸葛靓 Level 11, China
13 May 2021
nice explaination, make me understand a lot.
ImDevin Level 15, Old Town, United States
1 May 2021
clear, succinct, to the point. Now, if the tasks' conditions were like this... :)
John Level 17, Mansfield, Philippines
30 March 2021
aye! that was cool
frozenivy Level 10, Tampa, United States
23 December 2020
Excellent explanation