CodeGym/Java Blog/Java Collections/ArrayList in pictures
Author
Oleksandr Miadelets
Head of Developers Team at CodeGym

ArrayList in pictures

Published in the Java Collections group
members
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");
cars.add(ferrari);
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(ferrari);
   cars.add(bugatti);
   cars.add(lambo);

   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. So, 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 (59)
  • Popular
  • New
  • Old
You must be signed in to leave a comment
Pekotski
Level 14 , Zurich, Switzerland
20 February, 12:59
Very clear - kudos to the guy who wrote it. Shame, most of these guys here who wrote on this website never heard of the fact that writing is a communication in which clarity is a virtue. Eighty prozent cannot setup two sentences together to express merit. They substitute clarity for their coding skills because they think since they code they are entitled to write, and here we are - most of those lessons are only reference points, and if you need a proper explanation you have to go Google.
Toms Stašulāns
Level 23 , Latvia
12 August 2023, 07:28
Very understandable.
Rodrigo Muniz Frontend Developer at Wipro
27 February 2023, 18:08
Great topic and explanation!
Super Ego
Level 14 , Wu Han, China
15 February 2023, 08:03
图多,英语渣看着也挺简单的。就是讲了ArrayList的扩容原理。新的ArrayList以10为固定值,每到内容满就 乘1.5 再 加1。但只会自动扩容不会收缩,删除其中元素不会让它复原。收缩要使用自带的trimToSize()方法。
HOHOZ
Level 11 , Australia
27 November 2023, 14:46
感谢课代表
Qin-1999
Level 22
4 January, 06:08
我一开始想”这文章就讲了这个?“不信邪去看了看,还真是就讲了列表增加和减少原理,还有默认的大小10,建议用多大创建多大,内存利用率低下用trimToSize()来清除除了有元素的部分。
Ocean
Level 22 , China, Hong Kong
31 July 2022, 03:34
Great!
Tasmoda Android Developer
13 May 2022, 12:02
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!😂).
Jakhongir Ruziev QA Automation Engineer at Exadel
11 August 2022, 06:42
The default size is in the memory. Arrays should occupy a single block of memory. Therefore when you create an array internally it occupies a memory with the size of 10. When you add 2 elements and call the method array.size() you get the size of your elements but still have 8 more places in memory. I suggest you revisit the lessons about Arrays and ArrayList(Level 7). It seems like you misunderstood some concepts.
Victor Omoha
Level 8 , Raleigh , United States
11 November 2021, 13:28
that was epic
Eugenio Francioni Java Developer
18 September 2021, 13:51
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, 07:11
nice explaination, make me understand a lot.
ImDevin
Level 15 , Old Town, United States
1 May 2021, 02:58
clear, succinct, to the point. Now, if the tasks' conditions were like this... :)