Algorithms and Data Structures in an Object-Oriented Framework (“ADSOOF”)

ArrayLists in Java, and an Introduction to Generics

The generic class ArrayList

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 has to be an import statement for it. The type ArrayList<Thing> is the type “arrayList of Thing”, and in general ArrayList<X> is the type “arrayList of X” where X can be any type except a primitive type. So ArrayList<int> and ArrayList<char> are not allowed, this is where the equivalent wrapper classes need to be used as you can have ArrayList<Integer> and ArrayList<Character>. Then, if a is of type ArrayList<Thing>, 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.

Note the characters < and > are used here as if they are a sort of bracket (sometimes they are called “angled brackets”). They are the same characters that are used to mean “less than” and “greater than”, and you will have seen them used in this way for comparing numerical values in Java, but this is a completely different use. Note also that what goes inside the < and > pair must be a type name. Don't confuse it with the [ and ] characters (sometimes called “square brackets”) which come after a type name and with nothing between to form a new type name, and which otherwise have an integer value between them. When an array is being created, it is done with new followed by a type name followed by [ then there is the integer value giving the size of the array and the closing ]. When you are referring to a component of an array, you use the name of a variable which refers to the array, followed by [, followed by an integer expression to give the index, followed by ]. But you cannot use the < and > brackets with an integer value between them to create an arrayList of a particular size, and you cannot use them with an integer value between them to refer to a particular location in an arrayList object.

What is happening is that ArrayList is a generic type. To form a full type, it must be combined with another type, and the angled bracket notation is how this combining is done. If we have a full type consisting of ArrayList combined with another type, that other type is referred to as the element type of the full type (the term “base type” has also been used for it, but that term is now used with a different meaning in the context of inheritance). In the next set of notes, you will see another example of a generic type. The other way you will see angled brackets being used is described below, where they enclose the list of type variables for a generic method.

You may also see elsewhere a generic type such as ArrayList used without being combined with another type. This is referred to as a “raw type”. It is permitted in Java, and has its own rules for correct use, because generics were only introduced in Java version 5, and the raw types represent how older versions of Java handled arrayLists and similar types. So that code written for the old versions of Java can still be run under the new version of Java, raw types are still allowed. However, we will not use them in this module, and will not discuss them further.

ArrayLists as arrays

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<Integer> a,int m,int n)
 {
  for(int i=0; i<a.size(); i++)
    if(a.get(i).equals(m))
       a.set(i,n);
 }

public static void change(int[] a,int m,int n)
{
 for(int i=0; i<a.length; i++)
   if(a[i]==m)
      a[i]=n;
}

In the array example, a[i]==m is used to test whether the element at position i in the array referred to by the variable a is equal to the value stored in the variable m. We have seen the distinction between == and the equals method already in the context of Java's class String. As noted there, the method equals should always be used to test if two objects are equal, because the == only tests if two references to objects are aliases (that is, referring to the same object). With primitive values, the symbol == is used for equality testing, because variables that store primitive values store the actual value rather than a reference to an object. In fact, equals cannot be used, because a method cannot be called on a primitive value, and since a here is of type int[] then a[i] is of type int, which is a primitive type.

Here is a method which copies an arrayList of integers:

public static ArrayList<Integer> copy(ArrayList<Integer> a)
// BEWARE - this is not a good example!
{
 ArrayList<Integer> b = makeArrayListInt(a.size());
 for(int i=0; i<a.size(); i++)
    b.set(i,a.get(i));
 return b;
}

public static int[] copy(int[] a)
{
 int[] b = new int[a.length];
 for(int i=0; i<a.length; i++)
    b[i]=a[i];
 return b;
}

   {
    int n=a.get(i);
    b.set(i,n);
   }

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, unlike arrays you don't have to create one of a fixed size and then put things into it. That is why the method above for copying arrayLists was commented as “not a good example”, a better way of doing it is given below. But if you wanted to run the poor example, here is the code for the static method makeArrayListInt:

public static ArrayList<Integer> makeArrayListInt(int n)
{
 ArrayList<Integer> a = new ArrayList<Integer>();
 for(int i=0; i<n; i++)
    a.add(0);
 return a;
}

You can find the code for this and the other examples from this set of notes in the code index for this section. The file UseArrayLists1.java gives a destructive change method, and a copy method as given above, together with a main method which enables it to be demonstrated.

Code for finding whether an item is in an arrayList follows very closely code for finding whether an item is in an array, with a.get(i) replacing a[i]. Here is how you could write a method to find if an integer is in an arrayList of integers:

public static boolean isIn(ArrayList<Integer> a, int n)
{
 int i=0;
 for(; i<a.size(); i++)
    if(a.get(i).equals(n))
       return true;
 return false;
}

Similarly, code for finding the biggest item in an arrayList is very similar to what we saw for arrays:

public static Integer biggest(ArrayList<Integer> a)
{
 Integer biggestSoFar=a.get(0);
 for(int i=1; i<a.size(); i++)
    {
     if(a.get(i)>biggestSoFar)
        biggestSoFar=a.get(i);
    }
 return biggestSoFar;
}

Constructing ArrayLists

Once an array object has been created, what each individual component refers to can be changed, but the size of the array cannot be changed, as we saw previously. ArrayList objects, however, can have their size changed. If a refers to an object of type ArrayList<Thing>, 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<Integer> a = new ArrayList<Integer>();

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<Integer> copy(ArrayList<Integer> a)
{
 ArrayList<Integer> b =  new ArrayList<Integer>();
 for(int i=0; i<a.size(); i++)
    b.add(a.get(i));
 return b;
}

ArrayList<Integer> b = new ArrayList<Integer>(a);

ArrayList<DrinksMachine> b = new ArrayList<DrinksMachine>(a);

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 not 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.

It is also possible to make a copy of an arrayList using the clone method. Declaring a variable b of type ArrayList<Integer> and setting it to a copy of the arrayList referenced by a is done by:

ArrayList<Integer> b = (ArrayList<Integer>)a.clone();

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 “synchronised”, 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<E> where E stands for whichever element 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<Integer> it returns an Integer, if it is called on an object of type ArrayList<String> it returns a String, and so on.

Above we saw 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 element 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 element 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 class 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.

Note that when the method remove “removes the first item in the arrayList which is equal to n”, what this means is as defined by the method equals. To put it more formally, a.remove(n) removes the object at position i in the arrayList referred to by a where i is the lowest value such that a.get(i).equals(n). The way the method equals works depends on the class of the object it is called on, this is something we will discuss in more detail later.

You might wonder how a.remove(n) works when a refers to an arrayList of integers. However, remember the element 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.

There is some code to demonstrate the two different remove methods in UseArrayLists12.java and UseArrayLists13.java. In the second of these, the element type of the ArrayList is String, so it is clear which one of the overloaded methods is meant. It is the one which removes a particular String wherever it is when the argument is a String object, it is the one which removes whatever String object is at a particular position when the argument is an int value giving that position. In the first of these, however, as the element type of the ArrayList is Integer, which method is meant depends on whether the argument is of type int or of type Integer.

As with the two-argument add method, you should be careful to remember that when you are using the method remove with an int argument giving a particular position it changes the position of following elements in the arrayList. So, a.add(n,t) has the effect of putting what t refers to into position n in the arrayList referenced by a, but what was at position n gets moved up to position n+1, what was at position n+1 gets moved up to position n+2 and so on. In a similar way, a.remove(n) when n is of type int means that what was at position n is removed from the arrayList referenced by a, but what was at position position n+1 gets moved down to position n, what was at position n+2 gets moved down to position n+1 and so on.

The class ArrayList also has 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 which take ArrayList arguments

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. We cannot add methods to the class ArrayList as that class is already given to us as part of Java, so instead we can write methods which take an ArrayList object as their argument. Note the difference between a method which is in class ArrayList, so is called on an ArrayList object, and a method which is in another class and takes an ArrayList object as an argument. When a method is called on an object, the reference to the object (usually a variable of its type) is followed by the . character, then the name of the method and any arguments it takes within ( and ). When an object is passed to a method as an argument, the reference to it is one of the things which is between the ( and ). So far we have only seen writing our own static methods, but later we shall see also writing our own instance methods which are called on objects.

You have already seen a static 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<String> a,String m,String n)
 {
  for(int i=0; i<a.size(); i++)
    if(a.get(i).equals(m))
       a.set(i,n);
 }

First, however, let us consider another operation, this time we want to take an arrayList and two integers, and insert the second integer after every occurrence of the first. So if the array is the one that can be represented by [2,5,8,3,2,4,2,7] and the numbers are 2 and 10, the result will be the array [2,10,5,8,3,2,10,4,2,10,7], that is, 10 has been added after every 2. With arrayLists, we could do the change either constructively or destructively. Here is a destructive method to perform the operation:

 public static void addAfter(ArrayList<Integer> a,Integer m,Integer n)
 // Adds n after every occurrence of m in a
 {
  for(int i=0; i<a.size(); i++)
    if(a.get(i).equals(m))
       a.add(i+1,n);
 }

Now here is a constructive method performing the same operation:

 public static ArrayList<Integer> addAfter(ArrayList<Integer> a,int m,int n)
 // Adds n after every occurrence of n in a constructively
 {
  ArrayList<Integer> b = new ArrayList<Integer>();
  for(int i=0; i<a.size(); i++)
    {
     b.add(a.get(i));
     if(a.get(i).equals(m))
       b.add(n);
    }
  return b
 }

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

 public static void addAfter(ArrayList<Integer> a,int m,int n)
 // Adds n after every occurrence of m in a
 {
  for(int i=0; i<a.size(); i++)
    if(a.get(i).equals(m))
       {
        a.add(i+1,n);
        i++;
       }
 }

There is an issue we need to consider in our first version of a constructive method for the operation addAfter. In this case, it is simply a matter of good coding practice, it is not something that would cause it to give the wrong or an unexpected result. The code we gave calls a.get(i) twice in circumstances where it is always going to return the same value. If you find your code calls a method twice with the same arguments and you know nothing will change by calling the method and nothing in between the two calls will change the result returned, it's better to call it once, record that value using a variable, and then refer to that variable each time you want the result of the method call. This gives the following revised code for constructive addAfter:

 public static ArrayList<Integer> addAfter(ArrayList<Integer> a,Integer m,Integer n)
 // Adds n after every occurrence of m in a constructively.
 {
  ArrayList<Integer> b = new ArrayList<Integer>();
  for(int i=0; i<a.size(); i++)
    {
     Integer k=a.get(i);
     b.add(k);
     if(k.equals(m))
       b.add(n);
    }
  return b;
 }

Another way of avoiding multiple calls of the get method is to use the “for-each” loop construct. That would result in the code being:

 public static ArrayList<Integer> addAfter(ArrayList<Integer> a,Integer m,Integer n)
 // Adds n after every occurrence of m in a constructively.
 // Uses for-each loop
 {
  ArrayList<Integer> b = new ArrayList<Integer>();
  for(Integer k : a)
    {
     b.add(k);
     if(k.equals(m))
       b.add(n);
    }
  return b;
 }

The file UseArrayLists4.java shows the first destructive version of the addAfter method, and the file UseArrayLists5.java shows the amended version. The file UseArrayLists6.java shows the first constructive version of the addAfter method, and the file UseArrayLists7.java shows the amended version.

The file UseArrayLists14.java shows an example of a static method which uses the remove method with an int argument called on an arrayList. It destructively removes all integers which occur one position before a particular integer in an arrayList of integers. It is programmed carefully so that the integer argument itself is destructively removed if it occurs before itself in the arrayList. For example, with [2,3,4,5,6,7,4,1,4,8,9,4,4,5,2] and the removal of all integers which occur before a 4, the result should be [2,4,5,6,4,4,8,4,5,2] because although the 4s are not normally removed, the second to last 4 occurs before another 4 so it should be removed. The code uses a while-loop rather than a for-loop, so that the index variable is not increased by one when an integer is removed. This is because when this happens, what was at position i+1 moves down to position i. In the file UseArrayLists15.java which performs the operation constructively, a for-loop which increases the index variable by one each time round the loop is used because here we do not have to take into account any destructive effect of our code on the arrayList argument as we process it.

Finally, here's how to get round the problem of having to write a separate method for each element type. Here's the amended version of constructive addAfter for dealing with arrayLists of strings rather than arrayLists of integers:

 public static ArrayList<String> addAfter(ArrayList<String> a,String m,String n)
 // Adds n after every occurrence of m in a constructively.
 {
  ArrayList<String> b = new ArrayList<String>();
  for(int i=0; i<a.size(); i++)
    {
     String k=a.get(i);
     b.add(k);
     if(k.equals(m))
       b.add(n);
    }
  return b;
 }

 public static <T> ArrayList<T> addAfter(ArrayList<T> a,T m,T n)
 // Adds n after every occurrence of m in a constructively.
 {
  ArrayList<T> b = new ArrayList<T>();
  for(int i=0; i<a.size(); i++)
    {
     T k=a.get(i);
     b.add(k);
     if(k.equals(m))
       b.add(n);
    }
  return b;
 }

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 element 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 by using bounded generic types.

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 <T> void destChange(ArrayList<T> a,T m,T n)
{
 for(int i=0; i<a.size(); i++)
   if(a.get(i).equals(m))
      a.set(i,n);
}

public static <T> ArrayList<T> constChange(ArrayList<T> a,T m,T n)
{
 ArrayList<T> b = new ArrayList<T>();
 for(int i=0; i<a.size(); i++)
   {
    T k = a.get(i);
    if(k.equals(m))
       b.add(n);
    else
       b.add(k);
   }
 return b;
}

These methods can be found in a file called ArrayListOps.java. If a static method is declared as public in one class file, a call to it may be made in another class file by attaching the call to the name of the class the method is in. Examples of this are shown in the file UseArrayList11.java. For example, ArrayListOps.destReverse(a) calls a destructive reverse method, which takes a reference to an arrayList object and changes the object so that its components are placed in the reverse of their original order. The call ArrayListOps.destReverse(a) causes this to be done to the arrayList object referenced by the variable a.

Previously, we saw a method which searched an array of strings to see if a particular string was in it, and noted that it was almost identical to a method which searched an array of integers to see if a particular integers was in it. We noted then that generics would offer a way to avoid rewriting the method for every element type, and here is how it is done:

public static <T> boolean isIn(T[] a,T item)
{
 for(int i=0; i<a.length; i++)
    {
     if(a[i].equals(item))
        return true;
    }
 return false;
}

Last modified: 26 September 2019