In a previous episode we studied fixed-size arrays in Java. We saw that for this type of arrays, once the size is set when we initialize the array, it isn't possible to modify it anymore when the program executes. Today we'll study dynamic arrays, which will free us from this constraint. Dynamic arrays have the particularity to be able to increase or decrease their size while the program executes. Their use requires a number of concepts related to object-oriented programing. However, as with character strings, it isn't necessary to have any preliminary knowledge of these concepts to be able to use their functionalities. We decided to present them very early in the context of this course, because dynamic arrays can be used in very natural manners to resolve many problems that aren't necessarily related to object-oriented programming. As with fixed-size arrays, dynamic arrays are a collection of homogeneous data. To use them, we use a particular predefined type in Java called ArrayList. This type isn't defined by default. To use it in a program, you must include, at the beginning of the file, an import directive that will make the ArrayList type accessible. In Java, we can declare a variable of ArrayList type by using the following syntax: we put the variable name, and as type, we put the reserved name "ArrayList", followed by two characters "less than" and "greater than". Between these two characters, we put the type of data we want to put in the array. Note that the type must imperatively be an advanced type. Here's a concrete example: here we declare a variable "tableau" [TN: means "array"], the type of this variable is a dynamic array of strings. Note that the so-declared variable isn't initialized: we didn't assign any initial value to it. How can we initialize an ArrayList? A usual way of initializing an ArrayList is to initialize it with an empty array, an array without any elements. This is done like this: to the variable associated with the array, we'll assign an empty array created in the following manner. It has to be used exactly like this. The reserved word new, the reserved word ArrayList, here we'll put the exact same type as the one we used for the array declaration, followed by two parenthesis, not to forget. Here we resort to a way related to object-oriented programming, but it isn't necessary to fully understand the ins and outs of it to use it. What you must remember here is that with this instruction line, you constructed a dynamic array without any elements. Here you have a concrete example of declaration-initialization of an ArrayList of Strings. The "tableau" variable contains a reference to a dynamic array of Strings without any element yet. As this so-declared array doesn't contain any elements, we'll naturally ask ourselves the following question: how do we put the values in this array? As for the strings, there exists a number of specific methods related to the ArrayList type. To be able to use these functions, you must use a particular syntax; the array's name, followed by a dot, followed by the name of the function and then we must indicate, in parenthesis, the data that the function needs to be able to be executed. Here you have a concrete example. I declare an ArrayList of strings, named "prenoms" [TN: means "first name"] and I initialize this array with an empty array. Then I use a particular function defined for ArrayList, called "size". This function simply returns the current size of the ArrayList. I used the syntax I just mentioned, that is the array's name, followed by a dot, followed by the function's name. "size" doesn't need any external information to return us the array's size, so I must put an empty pair of parenthesis. Of course, this instruction line's execution will print 0, as I've initialized the array with an empty array. Now here's a non-exhaustive list of a few typical functions associated with arrays. We just saw the "size" function [a.k.a. "size" method] that allows us to get the array's size and that returns it as an integer. There exists other functions/methods such as "get" and "set" that I'll use according to the same principle, that is the array's name, a dot, followed by the function's name. Here I notice that unlike the "size" method, I need to give data to the "get" or "set" methods in order for them to work. The "get" and "set" methods are the equivalent of the indexation mechanism for static arrays. For a simple static array, if I want to access the element of index 'i', I use indexation. This mechanism doesn't exist for dynamic arrays. Instead, you must use methods such as "get" and "set". For a dynamic array, if I want to access the element of index 'i', I'll use this notation rather than this one. The same applies if I want to modify a static array. I'll use this notation, so if I want to modify the i-th cell of a static array I'll use this notation. This doesn't exist for dynamic arrays, instead we'll have to use this type of notation; the array's name, a dot, "set", and in parenthesis the index of the cell that I want to modify and the corresponding value. So this notation doesn't exist either for dynamic arrays. The restrictions on the index's bounds stay however the same as for a fixed-size array, the index varies between 0 and the array's size - 1. array's size - 1 is written like this for a dynamic array, for example. So, as with fixed-size arrays, any access attempt with an index out of the bounds will translate into an error at the program's execution. It's possible to test if a dynamic array is empty by using the "isEmpty" function. This is a function that doesn't need any data to work. It will return a value of boolean type, true or false, depending if the array contains values or not. The returned value will be true if the array doesn't contain any values and false otherwise. The "clear" method empties an ArrayList, which means that it deletes all its elements, and transforms it into an empty array. If we imagine for example that at a given moment in a program, I have an ArrayList that is in this state of filling -- let's imagine that it's an ArrayList of integers named "tab" -- if I call the "isEmpty" function, it's obvious that the result will be the false boolean, as the array isn't empty. I can now apply the "clear" function, for example, that will delete all the elements and transform it into an empty array. There is no more element in it. So if I call again the "isEmpty" function, this time the result will be true, as the array is now empty. The "remove" method allows us to delete the element of index 'i' in an ArrayList. So if we imagine for example that at a given moment, we have an ArrayList of integers with three cells, that has this particular form, the indexes vary between 0 and size - 1, which gives us this. Let's assume that the array is named "tab". Now, if I call the "size" function on this array, it will return 3 because my array contains three cells. Now if I call the "remove" method and pass it the index 1, this element will be removed, so all the elements that follow this element will be shifted to the left and I'll finally obtain an array with two cells. And if I apply my "tab.size()" function again, it will obviously return 2. Here we see that for an ArrayList, the size can indeed vary during the execution with the calls to methods of this nature. The index of the element that we want to remove obivously has to exist in the array when we call the "remove" function. Let's suppose for example that instead of doing "tab.remove(1)*, I try doing "tab.remove(4)". This will result in an error during the program's execution. If it's possible to remove elements from an ArrayList, it is also possible to add values in such an array. To achieve this we'll use the "add" method, and we'll have to give the value that we want to add to the array. The value will systematically be added at the end of the array. Let's take a concrete example of an array of integers. Here, "tab.size()" returns 3. I add the value 8 to my array by using the "add" method. The result will be an array with an additional cell. This cell is at the end so I'll have this in "tab", and of course "tab.size()" will now return 4; we can see that the array increased by one cell. Now here's an example with a few basic manipulations that we can usually do on an ArrayList. So we saw that to be able to use the ArrayList type, it was necessary to begin the file with an import directive that will make the ArrayList type available in the program. I can now use the ArrayList type to declare a variable and here I'm declaring a variable of type ArrayList of Strings. We also saw that in order to initialize the array to an empty array, we have to use this sort of notation. So at the end of the execution of this instruction line, I get as a list the reference to an empty ArrayList. I then execute the following instruction line. I call the "add" method that allows me to add a particular element, here the string "un" [TN: means "one"] at the end of the ArrayList. As the array is empty, it doesn't make a big difference; ultimately I'll have a dynamic array that will look like this. I execute the following instruction line that adds a string, the string "deux" [TN: means "two"] at the end of the array. So here I get the following content in the array. If I want to print the content of my ArrayList at this stage, I use a for-loop. We saw that we could use for example a for-loop iterating over a set of values. Here my for-loop will alternately take each element of the list and print it by separating them with a space. So here, after the execution of this instruction line, will be printed the string "un" separated by a whitespace from the string "two", that will get printed like this on the screen. If I want to access the i-th cell of an ArrayList, either to look at its content, or to modify it, I'll have to use the "get" and "set" methods. So if I execute this instruction line, knowing that the array filling at this stage is like this, I'll use the "get" method that will access the element of index 1 in the array. This element of index 1 is the string "deux" and at that moment I'll print the sequence "deux". When I execute the following instruction line, I'll modify the element at the index 0 in order that its new value is the string "premier" [TN: means "first"]. So my array will now look like this, after the execution of this instruction line. The element of index 0 that was "un" has been changed into "premier". In every example of ArrayList showed until now, the content was of type "String". Of course, it's a deliberate choice that responds to the constraint that the content of an ArrayList in Java must systematically be of an advanced type. It can however turn out that we need to work with dynamic arrays of integers. How would we then proceed? It's enough to know at this stage that Java offers for each basic type, a corresponding advanced type. For example, for the 'int' type, you have the Integer type, with an uppercase 'I', that is equivalent to "int" but is of advanced type. The same applies for the "double" type. There is an equivalent, "Double with an uppercase 'D'; and this is valid for each basic type. These advanced types of a patricular kind are particularly useful in some contexts, typically for ArrayList. Why? Because we saw that in an ArrayList, it's only possible to store values of advanced type. Thereby, in a Java program, I can never declare an ArrayList of "double" with a lowercase 'd', nor an ArrayList of "int". I can however declare an ArrayList of "Integer". Once the array's declaration is done and respects the constraint that the content is of an advanced type, I can put values of elementary type in my array, for a very simple reason. That reason is that the conversion of basic types into advanced types can be done automatically. That was't the case in the first versions of Java, but that's how it's done now. And I can therefore work with dynamic arrays of "Integers" or of "Doubles" while being nearly free from the constraint of using advanced types. Now let's see that with a concrete example. Here we want to write a small program that fills an ArrayList of integers with stricly positive numbers. We suppose that the values will be requested from the user and we also want to adhere to a number of conventions. If the user enters the value 0, that will be the convention that we want to restart filling the array from the beginning. If the user enters a negative number, that will be the convention that we want to remove the last element introduced in the array. The program's execution could look like this. We ask the user to enter three strictly positive values, and we'll ask him each of these values alternately. Here we ask him to enter the value of index 0 and we suppose that he entered 5. This value being strictly positive, we'll store it in the array. We then ask him the second value, the one of index 1. This value is strictly positive, we put it in the array, once again. We then ask him to enter the last value, the value of index 2. But it turns out that the user enters a 0, which corresponds to the convention to restart from the beginning. Which means that at this point, we want the array to be empty again. So as the array is emptied again, the next value that we'll ask from the user will be the value of index 0 again. Here the user enters a 7, we'll therefore have this array. He then enters a 2, we get this array. He then enters, for the last value again, a negative value, which corresponds for us to the second convention, the one that says to remove the last element. The last entered element is the 2, so we want the array to now look like this, and that's why, at the next step, we'll ask the user to enter the second value again, as the array now contains only one value. At that moment the user enters a 4, that we'll store in the array, he then enters a 12 as last value, and we'll end up with this array. As we indeed have the three desired values, we constructed our array as we intended to, and we'll finally end up with an array that contains 7, 4 and 12, which are all strictly positive values. Here we see that during the entire program's execution, our array's size increases and decreases following our needs. So that's typically a case where the use of an ArrayList is particularly adapted. Now let's see how all this looks like in the form of a Java program. The computations showed in the previous example can be implemented with a small Java program that looks like this. We begin by declaring an ArrayList of integers. As we can't create an ArrayList of "int" type, of any elementary type, we use the "Integer" type. Our ArrayList is named "vect" and is initialized as an empty ArrayList. So ultimately the "vect" variable will contain the reference to an empty ArrayList of integers. We then ask the user how many values he wants to enter in the array. We input the size that the user wants for the array with a keyboard interaction. We then ask the user to input the different values to fill the array. To achieve that, we use a loop, as he is potentially going to enter many values. The loop is such that while the actual array size hasn't reached the desired size, we continue to loop. During each loop iteration, we ask the user to input one of the values in the array. But what value precisely? Here we want to indicate to the user the index of the value to input. Let's suppose that the array's filling state is the following: so at this moment vect.size() has the value 2 and the last element has index 1, which is vect.size() - 1. That means that the next value of the array that we want to input does indeed have "vect.size()" as index, and that's what we can see here. We'll ask the user to input the value that's at the position vect.size(), that will occupy the position vect.size(). The value to put in the array is again input with a keyboard interaction. And that's when we begin testing the different cases to adhere to the different conventions presented in the previous example. One of the conventions that we wanted to implement is that if the value introduced by the user is negative, that would mean that we want to remove the last element introduced in the array. So concretely, we'll use the "remove" method to do this suppression. And at that moment we'll remove the last element of the array, the element of index vect.size() - 1, as we saw here. However, we have to take a precaution. We can process with this suppression only if the ArrayList isn't empty. Therefore, we must combine this first test with a second test that will test if the ArrayList, is empty or not. So we'll proceed with the suppression only if the value is negative and if the array isn't empty. Whether it is empty or not is tested with the isEmpty function. The fact it isn't empty is expressed with this negation. If the condition expressed here isn't verified, we must then proceed with other tests. We saw that we wanted to have the convention that if the user enters the value '0', that means that we want to empty the array. We therefore proceed with an alternative test here. To completely empty an ArrayList, you use the "clear" function. So here, simply, if the value entered by the user is null, then we completely empty the array. Otherwise, if we reach this stage of the execution, that means that either the entered value is strictly positive, or the vector is null. It therefore isn't strictly guaranteed that the entered value is positive. You must therefore test it again; that's what we do here. If this is the case, if the condition is verified, we can then add the value to our ArrayList and that is done with the "add" function. So, we are going to iterate over these computations while the ArrayList hasn't reached the size wanted by the user. Note an important thing. We constructed our array, we declared it by using the advanced type 'Integer'. This means that in our array, we don't directly have integer values like this, or like I have shown very schematically in the example. But to be exact, we have references to integers in the array. So here the situation would be as follows: at the position '0' we would have a reference to a memory address that contains '12', and not directly the value '12'. In this case, how did we enter a value of 'int' type in the array like we have done here? Indeed, as our array has been declared as containing 'Integer', we expect to be able to add to this array only values of the same type, and therefore not directly an integer, but a reference to an integer, which we don't know how to construct or initialize for the moment. However, we were able to directly enter an 'int'. This is allowed thanks to the automatic conversion that is done between the basic types and the corresponding advanced types. So in reality, when we execute this instruction line, what we put in the array isn't directly the value "val" entered by the user, which is of 'int' type, but we put in the array an "Integer", which is a reference to the value "val". All this is done in a completely automatic and transparent way. We didn't have to worry about conversions. So thanks to this automatic conversion, it becomes completely natural to also work with ArrayLists of integers, of doubles, or of a basic type. The only precaution that we must take is to declare the array with the corresponding advanced type. This automatic conversion between a basic type and a corresponding advanced type is what we call "autoboxing", in technical terms. We saw that an ArrayList can only contain elements of advanced types. To conclude, let's examine the incidence that this has on the comparison of the elements of such an array. At the first instruction line, I'll have the automatic conversion of a value of basic type to a value of 'Integer' type. But I am in reality adding to my ArrayList isn't directly the value 2000, but a reference to this value. So I end up with a memory situation that is the following. Here the value 2000 was not directly stored in our ArrayList, but its address. So when I execute the second instruction line, it's exactly the same situation that happens, except that at that moment I have 2 references. It turns out that these references have a similar content, but they were created by two distinct "add". And at that moment, they are two different, distinct, memory addresses. So here, if I want to compare the content of the first entry of the array with the second, with something like this, the result of this instruction line's execution will in reality be false. Why? Because I indeed have 2 distinct memory addresses, and it isn't the same memory location, and the comparison will return false. If we are more interested in comparing the contents, then, as we did with the Strings, we mustn't resort to an equality test with '==', but rather to an equality test with 'equals'. So we access the first element of the array, which is an 'Integer', and we apply the 'equals' method on this element to compare it with the second element of the array. And here, the result of this instruction line's execution will indeed be 'true' because the values are identical. The values to which the references point are identical.
