DCS128: ArrayLists notes ArrayLists in Java, and introducing Generics ArrayLists as Arrays You have seen arrays in Java, where for any type, for example Thing, adding [] to the end of the type creates an array type, so Thing[] is the type "array of Thing". Then, if i is an integer value, and a a variable of type Thing[], we can change the value of the ith component of the array referred to by a using the assignment a[i]=expr where expr evaluates to a value of type Thing and the component is set to that value. Any usage of a[i] in an expression gives the current value of the ith component of the array which a is currently referring to. ArrayLists work in a similar way. The class ArrayList occurs in the package java.util, so if it is used in a file, there must be an import statement for it. The type ArrayList
is the type "arrayList of Thing", and in general ArrayList is the type "arrayList of X" where X can be any type except a primitive type. So ArrayList and ArrayList are not allowed, this is where the equivalent wrapper classes need to be used as you can have ArrayList and ArrayList. Then, if a is of type ArrayList, the statement a.set(i,expr) is equivalent to the previous a[i]=expr when a referred to an array. The method call a.get(i) is the equivalent of a[i] in an expression. So note that, unlike arrays, there are no special symbols for referring to the components of an arrayList, it is done using ordinary method calls. Note that a.get(i)=expr does not make sense as a.get(i) is a method call, and you cannot assign a value to a method call. Here is a static method which takes an arrayList of Integers and two integer values and destructively changes all occurrences of the first integer value to the second in the arrayList:
public static void change(ArrayList a,int m,int n)
{
for(int i=0; i copy(ArrayList a)
{
ArrayList b = makeArrayListInt(a.size());
for(int i=0; i as a type for arguments to methods and for the return type of methods, just as you can use int[] in these ways. Note that in our example b.set(i,a.get(i)) is equivalent to
{
int n=a.get(i);
b.set(i,n);
}
that is, it gets the ith component of a and sets the ith component of b to it. In this example, makeArrayListInt(a.size()) is used as the equivalent of new int[a.length], that is, it creates a new arrayList with the same number of components as a but with those components set to 0. However, Java does not provide us with this method, because arrayLists aren't intended to work like this. Here is the code for the static method makeArrayListInt:
public static ArrayList makeArrayListInt(int n)
{
ArrayList a = new ArrayList();
for(int i=0; i, then the statement a.add(expr) where expr evaluates to a value of type Thing causes an extra component to be added to the end of the arrayList object referred to by a which is set to refer to the object returned by the evaluation of expr. The value returned by a.size() is increased by 1, and the value returned by a.get(a.size()-1) with the new value of a.size() is the value returned by expr. This is a destructive change, so any variable which aliases a will see the same change in the object it refers to as it is the same object. So in our code for makeArrayListInt above, the statement
ArrayList a = new ArrayList();
declares a variable of type ArrayList called a, and sets it to a new arrayList of integers whose size is initially 0. Then every time a.add(0) is called in the loop, an extra component is added to this arrayList object, every component added referring to an Integer of value 0. In fact, there was no need for our copy method to create an initial arrayList of the same size as the argument arrayList. It could just have created an initial arrayList of size 0, and added the new components to make the copy:
public static ArrayList copy(ArrayList a)
{
ArrayList b = new ArrayList();
for(int i=0; i b = new ArrayList(a);
declares variable b of type ArrayList and sets it to refer to a new ArrayList object which has the same components as the ArrayList object referred to be a. It's important to note that the components within the arrayList are not copied, this is referred to as a shallow copy. Since objects of type Integer are immutable, this is not an issue in this case, but it would be if we had an arrayList of mutable objects. Since the base type of an arrayList could be any object type, then it could be a mutable type such as DrinksMachine as covered previously. If a refers to an arrayList of DrinksMachine objects of size 4, then the result of
ArrayList b = new ArrayList(a);
could be illustrated diagrammatically as: Code which uses a constructor to make a shallow copy of an arrayList and then uses the destructive change method can be found in UseArrayLists3.java. Note that although there is a constructor for the type ArrayList which takes an argument of type int, using it does not create a new arrayList of a particular length, it actually creates an arrayList of length 0 just as the zero-argument constructor does. The int argument is actually to do with the internal structure of an arrayList, which you need to be concerned with at this point. So in this way arrayLists work differently from arrays: with arrays you always create an array of a particular size with its elements intialised to 0 or null, but this cannot be done with arrayLists, instead the usual technique is to create an arrayList of length 0 and expand it by adding new elements. You can find the complete documentation for the class ArrayList here. As we have previously noted with the official Java documentation, it is complex because it has to cover every aspect of the class, which includes plenty of things you have not covered yet. For instance, there's a large section at the beginning of the documentation noting that the implementation is not "synchronized", and then stating what to do "If multiple threads access an ArrayList instance concurrently". Concurrency and multiple threads is not something we shall cover at all in this course, you will need to become much more advanced Java programmers before this becomes as issue so you can ignore this section, but the problem when you are just starting out and faced with complex documentation like this is that it's hard for you to know what aspects you can safely ignore because they go beyond what you need to know. However, from the documentation you can see that there is a variety of methods provided in class ArrayList which perform useful operations changing both the size and content of the ArrayList object they are called on, so making arrayLists much more flexible than arrays. The class is named as ArrayList where E stands for whichever base type you use. So the method get, which is the method we described above, is documented as having argument type int and return type E meaning that if get is called on an object of type ArrayList it returns an Integer, if it is called on an object of type ArrayList it returns a String, and so on. We have already seen the single-argument add method which adds its argument to the end of the arrayList object it is called on, but there is also a two-argument add which takes an integer and an object of the base type of the arrayList and adds the object at the position in the arrayList specified by the integer. The object which was at this position and all the objects in higher-indexed positions are moved up one place, and the size of the array increases by one. So this is a different thing from set which also takes an integer representing a position and an object of the base type, but replaces the object at the given position, so this object is no longer in the arrayList, and the size of the arrayList remains the same. Note that set does actually have a return value, given as type E, the base type of the arrayList object it is called on. Where we have used it above, we have done nothing with the value it returns, so used it as if it has return type void. This is fine, mostly this is how set is used. But the value it returns is the object that was replaced, just in case that was something you needed to keep a reference to. There are also two remove methods. One takes an argument of type int and removes the item from the arrayList it was called on at the position given by the int argument, moving everything following it down one place in the arrayList and causing the arrayList's size to be reduced by one. The class arrayList has two single-argument methods called remove. We saw a method called remove previously with arrays, which was static and constructive, so a call remove(a,n) where a referred to an array of integers and n held an integer returned a reference to a new array which was like the one referenced by a but had the first occurrence of n removed and everything following it moved down one place. The remove methods in arrayList are not static and are destructive, so a.remove(n) changes the arrayList referred to by a to remove an item, all items in the arrayList following it are moved down one place, and the size of the arrayList is reduced by one. However, if n is of type int, the call a.remove(n) removes the item in the component of the arrayList indexed by n, otherwise it removes the first item in the arrayList which is equal to n. So method remove in class ArrayList is like method removePos we saw previously with arrays when it has an argument of type int, and like the previous remove otherwise. This is why we said there are two different single-argument methods called remove in class ArrayList: which one is used depends on the type of the argument. The situation where methods have the same name but can be distinguished by the number and/or the types of their arguments in known as overloading. You might wonder how a.remove(n) works when a refers to an arrayList of integers. However, remember the base type of an arrayList of integers must be Integer, not int. So if a refers to an arrayList of integers, then n must be of type Integer to have the effect of removing an item equal to n rather than the item at position n. Note that both remove methods in class arrayList have return types. The method with argument of type int which removes the item at the position given by its argument returns a reference to the item that was removed, and throws an IndexOutOfBoundsException if the int argument is a value below 0 or equal to or great than the size of the arrayList it is called on. Otherwise, a call of remove on an arrayList returns true if the item given as an argument can be found and is removed, and it returns false if no item equal to the argument can be found. The class arrayList also has static methods indexOf and lastIndexOf, which work like the position methods we gave previously, except again they are not static, so a.indexOf(n) gives the index of the first occurrence of an item equal to n in the arrayList referenced by a, while a.lastIndexOf(n) gives the position of the last occurrence; both of these return -1 if no item equal to n can be found in the arrayList. Methods on ArrayLists The class arrayList gives us some of the methods we would most likely need to use on arrayLists, but if there is not something there already to do a task we require, we need to write our own method. You have already seen a method which takes an arrayList of integers and two integers, and changes all occurrences of one integer argument to the other. Now here is a method which takes an arrayList of strings and two strings and changes all occurrences of the first string to the second:
public static void change(ArrayList a,String m,String n)
{
for(int i=0; i a,Integer m,Integer n)
// Adds n after every occurrence of m in a
{
for(int i=0; i addAfter(ArrayList a,int m,int n)
// Adds n after every occurrence of n in a constructively
{
ArrayList b = new ArrayList();
for(int i=0; i) to refer to the new one. There is a problem with the destructive version. Suppose we want to add a 2 after every occurrence of 2, so that starting with [2,5,8,3,2,4,2,7] we change it to [2,2,5,8,3,2,2,4,2,2,7]. If we call the method with the call addAfter(a,p,q) where a refers to the arrayList written [2,5,8,3,2,4,2,7] and p and q are set to 2. You will find the code runs for much longer than you'd expect and terminates with an error message. The reason for this is that our code does not take into account the case where both integer arguments are the same value. In our example, having added a 2 after the first 2, it looks at the next integer and finding it is a 2 adds another 2 after it. Then it does the same and in fact keeps on adding 2 and expanding the size of the arrayList until it exceeds the maximum size the system can handle. The error message you will get here is:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
If you get an error message like this, unless you are doing something which you know for sure involves creating a huge arrayList or some other collection type, you should conclude your code somehow gets into an infinite loop which just carries on taking more and more store until it reaches the system limit. Always look for that infinite loop rather than ask "how can I increase the amount of store the system allows me to use?". The other thing to learn here is always check special cases, and the case where two arguments are the same where normally they'd be expected to be different is a good example. It's best that your code takes into account every possible special case, don't just assume "Oh, that will never really happen, so I don't need to bother adjusting the code to deal with it". Here is code for the destructive addAfter method which deals properly with the two integer arguments being the same and gives the result you would expect:
public static void addAfter(ArrayList a,int m,int n)
// Adds n after every occurrence of m in a
{
for(int i=0; i addAfter(ArrayList a,Integer m,Integer n)
// Adds n after every occurrence of m in a constructively.
{
ArrayList b = new ArrayList();
for(int i=0; i addAfter(ArrayList a,String m,String n)
// Adds n after every occurrence of m in a constructively.
{
ArrayList b = new ArrayList();
for(int i=0; i. Here is the generic version of constructive addAfter:
public static ArrayList addAfter(ArrayList a,T m,T n)
// Adds n after every occurrence of m in a constructively.
{
ArrayList b = new ArrayList();
for(int i=0; i and p and q are of type Integer. If a and b are of type ArrayList and p and q are of type String, it will set T to String. The generic version of the addAfter method, together with code that shows it used for both an arrayList of integers and an arrayList of strings can be found in the file UseArrayLists10.java. In the code for the generic version of addAfter you can see that the type variable may be used in the arguments to the method, the return type, and also to declare local variables, either as a type on its own or as the base type for ArrayList. However, we can assume nothing about objects whose type is given by the type variable. We can call the method equals on them, as we do on the example where we have k.equals(m)) where k and m are declared as of type T where T is a type variable. This is because the method equals can be called on objects of any type. We could not call a method on these variables of a sort which can only be called on objects of certain types. Later we shall see how type variables may be specified in a way which enables a wider range of methods to be called on them. Going back to methods to take an arrayList and two values, and change all occurrences of one value to the other in the arrayList, here is a destructive generic version:
public static void destChange(ArrayList a,T m,T n)
{
for(int i=0; i ArrayList constChange(ArrayList a,T m,T n)
{
ArrayList b = new ArrayList();
for(int i=0; i 
