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 is 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! :)