Hi! Today's lesson about ArrayList will be both easier and harder than previous lessons.
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<>();
}
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);
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.
Then our new element is inserted in its place. The previous element (bugatti) has already been copied from there to a new position.
Now let's look at how this process happens if there are no places to insert new elements into the array.
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.
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.
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.
This is how it looks:
And in the end we get what we want:
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:
As the program runs, we remove 77 elements, so only 11 remain:
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.
Now we've only allocated as much memory as we need! :)
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.
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!😂).
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.
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??
It's worth mentioning that when the array is full and you want to add an element to it, array expands using mathematical formula:
newSize = (int) 1.5*oldSize +1;
The rest of the article is clear. Good job.
Great article, I just have a hard time understanding a sentence in the beginning, when it reads "As you already know, ArrayList has is an ordinary array inside, which acts as a data store."
The part "ArrayList has is an ordinary array inside,", did you mean ArrayList has is an ordinary array inside,"?
Yes, as you know, when you don't indicate an exact size, when you create a new ArrayList trimming happens automatically when needed.
This trimToSize() method is only used when you have already indicated the minimum size of the ArrayList when you created it and later remove many items from it. It is used in this case to reduce unnecessary memory use after removal of many items from the ArrayList.
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 
That's clear enough.
What happens if we insert in the middle, i.e. between other elements?
Then our new element is inserted in its place. The previous element (bugatti) has already been copied from there to a new position.
Now let's look at how this process happens if there are no places to insert new elements into the array.
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 
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.
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.
This is how it looks:
And in the end we get what we want:
The 
As the program runs, we remove 77 elements, so only 11 remain:
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 
Now we've only allocated as much memory as we need! :)
GO TO FULL VERSION
isan ordinary array inside,"?