Java ArrayList in pictures

Hello! Today's lecture ArrayListwill be, on the one hand, simpler, and on the other, more difficult than the previous ones. It’s more difficult, because today we’ll look “under the hood” ArrayListand study what happens to it during operations. On the other hand, there will be almost no code in this lecture - mostly pictures and explanations. So, let's go :) As you already know, inside ArrayList'a there is an ordinary array, which acts as a data store. In most cases, we do not specify the exact size of the list. But the internal array must have some size! This is true. Its default size is [10] .

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

First, let's look at what adding a new element looks like. First of all, a check is made to see whether there is enough space in the internal array and whether one more element will fit. If there is space, the new element is added to the end of the list. When we say “to the end”, we do not mean the last cell of the array (that would be strange). This refers to the cell next to the last current element. Its index will be equal to cars.size(). Our list is currently empty ( cars.size() = 0). Accordingly, a new element will be added to the cell with index 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

Everything is clear here. What will happen if the insertion is carried out in the middle, that is, between several 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);//добавляем ford в ячейку 1, которая уже занята
}

Again, it first checks to see if there is enough space in the array. If there is enough space, the elements are shifted to the right starting from the cell where we insert the new element. We paste into the cell with index 1. That is, the element from cell 3 is copied to cell 4, element 2 to cell 3, element 1 to cell 2. After that, our new element is pasted into place. The previous element ( bugatti) has already been copied from there to a new location. Now let's figure out how this process would happen if there were no space for insertion in the array. First, of course, a check is made to see if there is enough space. If it turns out that there is not enough space, ArrayLista new array of size (size of OldArray * 1.5) + 1 is created inside 'a. In our case, the new array will have a size of 16 cells. All current elements will be copied there immediately. The old array will be deleted by the garbage collector, and only the new, expanded one will remain. Now there is free space for the new element. We paste it into cell 3, which is occupied. Now the familiar procedure begins. All elements starting at index 3 are shifted one cell to the right, and a new element is quietly added. And now the insertion is successful! We sorted out the insertion. Now let's talk about removing elements . As you remember, when working with arrays, we encountered a problem: when we deleted them, “holes” remained in it. The only solution was to shift elements to the left each time they were deleted, and you had to write the code for the shift yourself. ArrayListworks on the same principle, but in it this mechanism is already implemented automatically. This is what it looks like: And in the end we get the desired result: The element lambowas successfully deleted. Here we did a removal from the middle. It is clear that deleting from the end of the list will be faster, since the desired element is removed without shifting all the others. Let's take another look at the size of the internal array and its storage in memory. Array expansion is a process that takes a certain amount of resources. Therefore, you should not create ArrayListwith the default size if you know for sure that it will have at least 100 elements. By the time you get to inserting the 100th element, the internal array will expand 6 times , each time transferring all the elements.

• 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 (according to the formula (size of the Old Array * 1.5) + 1)

Naturally, this is quite expensive in terms of resources. Therefore, if you already know some (at least approximate) number of stored elements, it is better to immediately create a list with an array of a certain size:

ArrayList<Car> cars = new ArrayList<>(100);

Now an array of 100 elements will be immediately allocated in memory, which will be more efficient because resources will not be wasted on expansion. There is also the other side of the coin. When objects are removed from ArrayListthe internal array, the size is not automatically reduced. For example, we have ArrayListan internal array of 88 elements, which is completely filled: During the program’s operation, we remove 77 elements from it, and only 11 remain in it: Have you already guessed what the problem is? Inefficient use of memory, of course! We use only 11 cells, while we have memory allocated for 88 elements - that's 8 times more than we need! To carry out optimization in this case, you can use a special class method ArrayList- trimToSize(). It “cuts” the length of the internal array to the number of elements currently stored in it. Now as much memory is allocated as needed! :)