Overview of This Lesson

In this lesson, you'll learn about how an ArrayList can be used for lists of objects, and how an ArrayList is different from a regular array.

Pre-Requisites

Before doing this lesson, make sure you've gone through the Collections Overview.

ArrayList Class

The ArrayList<E> class is a concrete implementation of the AbstractList<E> class that implements the List<E> interface. It's an array that can change size automatically or programatically. When an array can change size automatically, we refer to that as dynamic array.

ArrayList<E> is a generic type: When creating an ArrayList, it is strongly suggested that you replace the type parameter E with a concrete type argument (see Generics & Parameterized Types in the Collections & Generics lesson if you need to review the terminology). This makes storage and retrieval much more efficient and will catch a lot of common mistakes at compile time instead of at runtime.

For example, to create an ArrayList that holds Circle objects, you would declare the ArrayList as:

ArrayList<Circle> roundThings = new ArrayList<Circle>();

If you declare your ArrayList without a concrete type, then your ArrayList will be allowed to contain any kind of Java Object, AND you will be required to cast your ArrayList elements into whatever class they're supposed to be:

ArrayList<Shape> list = new ArrayList<Shape>();
list.add(new Circle());
list.add(new Cylinder());
list.add(new Scanner(System.in));
for (Object o : list) {
    if (o instanceof Circle) {
        Circle c = (Circle)o;
        System.out.println(c.getArea());
    }
}

If this example used a parameterized type for the ArrayList, the if statement would not be needed because all instances inside the ArrayList would have to be of the same type as the type argument (or children of).

Another important distinction between arrays and ArrayList is that the ArrayList (and all other collection objects in Java) can only hold objects. If you want an ArrayList to contain primtive data such as integers or doubles for example, you will have to use the wrapper class:

ArrayList<Integer> integerNums = new ArrayList<Integer>();
ArrayList<Double> floatNums = new ArrayList<Double>();

ArrayList elements that have been assigned objects actually contain references to those objects in memory, just as a String[] or Shape[] array would.

When you construct an ArrayList using the default constructor, the ArrayList has a capacity of 10. Capacity refers to the number of objects an ArrayList is capable of holding. An ArrayList's size refers to the actual number of objects contained inside the ArrayList. We'll discuss what this means and how it affects the size of your list as you add and remove elements in the section on Size and Capacity.

Lastly, ArrayList elements must be contiguous. This means that an ArrayList can't have "empty" elements between other elements. When new objects are added to the list, they must either be added to the end of the list (after the last object in the list) or they must be inserted in between two other objects.

If ArrayLists are So Cool..?

If ArrayLists are so cool and easy to use, why don't we only use an ArrayList instead of a regular array?

ArrayLists do require a lot of overhead and resources, much more than a regular array. If you can do what you need to do with a regular array, you should use a regular array. Use an ArrayList when you need the extra feature of a dynamic array that changes size as new elements are added. If you're going to be adding and removing a lot of elements, the ArrayList can be a bit less efficient, so you would use a LinkedList, instead.

Summary

Summary of the characteristics of ArrayList objects:

• ArrayLists are dynamic, numerically-indexed lists.
• ArrayLists can only hold objects; ArrayLists can't contain primitive data.
• ArrayList uses generics, so it can be declared as a parameterized type. An ArrayList with no concrete type contains instances of Object.
• ArrayLists have a capacity and a size, and they are not necessarily equal.
• ArrayList elements must be contiguous.
• ArrayLists take up more memory and resources than regular arrays.

Adding and Removing Objects

One of the benefits of an ArrayList is that it's very easy to add, remove, and replace elements with very little code (this is part of the reason why they are more resource-intensive than regular arrays, but it's a trade-off)! It's even simple to insert or remove an element in between two other elements without having to shift the remaining elements up or down.

Adding Objects

There are several ways you can add elements to an ArrayList. The table below summarizes some of these.

ArrayList<Shape> shapes = new ArrayList<Shape>();

LinkedList<Circle> roundOnes = new LinkedList();
shapes.add(new RectangularPrism());
roundOnes.add(new Sphere());
roundOnes.add(new Cylinder());
shapes.addAll(roundOnes);

shapes.add(new Circle());
shapes.add(new Cylinder());
shapes.addAll(1, roundOnes); // insert linked list in element 1

The add(E e) method accepts an object as an argument and adds that object to the end of the list. E is a generic type and must be replaced with a concrete type, and it must match the concrete type used when creating the ArrayList:

ArrayList<Shape> shapes = new ArrayList<Shape>();
shapes.add(new Circle(5));
Cylinder c = new Cylinder();
shapes.add(c);

Even though the add() method returns a boolean, you can ignore the return type since it's not often used with ArrayList. The return type is there because this is an override of the Collection's add() method. With an ArrayList, there's very few reasons why the add() would be unsuccessful.

You can also insert an element into an ArrayList at a specific index:

ArrayList<Shape> shapes = new ArrayList<Shape>();
shapes.add(new Circle(5));
Cylinder c = new Cylinder();
shapes.add(c);
shapes.add(1, new Cylinder(2, 4));

Line 5 will insert a Cylinder object into element 1 (the second element). The object that was in element 1 before line 5 (the cylinder) will be moved to element 2, and any object in element 2 will be moved to 3, etc. In other words, all objects in the current position and after will be shifted down one spot.

All objects in the ArrayList must be contiguous. In other words, your ArrayList elements must be adjacent to each other: You can't have objects in the first 3 elements, then nothing in the next element, and then an object in the 5th element. The elements have to fill the array one-after-another with no gaps. That means the following code is incorrect and will throw a runtime exception:

ArrayList<Shape> shapes = new ArrayList<Shape>();
shapes.add(new Circle(5));
Cylinder c = new Cylinder();
shapes.add(c);
shapes.add(4, new Cylinder(2, 4)); // would create empty elements 2 and 3

Removing Objects

There are several methods you can use to remove elements from an ArrayList. The following table summarizes these methods:

ArrayList<Shape> shapes = new ArrayList<Shape>();

LinkedList<Circle> roundOnes = new LinkedList();
...
shapes.removeAllAll(roundOnes);

The remove() method will allow you to remove an element from a list in two ways:

The remove(int index) method will remove the object at the specified index and return it. It will move all elements below position index up one slot and the array size will decrease by 1.

The remove(E e) method will search for the specified element in the list and, if it exists, remove it (and shifts all elements below E up one slot). This method returns true if the object was removed and false if the object was not found. Example:

Shape someShape = shapes.remove(2);
boolean isGone = shapes.remove(myShape);

The first statement removes the shape at index 2 and stores it in the Shape variable someShape. The second statement stores true in the isGone variable if the element in the myShape variable is found and removed from the list.

If you need to remove all the elements in the ArrayList (basically, empty the list), use the clear() method:

shapes.clear();

Editing (Replacing) Objects

If you need to update or change an existing element in the array, you can use the set() method:

shapes.set(4, new Sphere(7));

The statement above will replace the current object at index 4 with a new Sphere object. This will destroy the ArrayList reference to the object that was already in element 4, so if you need it, the set() method will also return the removed/destroyed object for you:

Shape oldShape = shapes.set(4, new Sphere(7));

This will take the object currently at index 4, store its memory address in the variable oldShape, and then put a new object in the element at index 4.

ArrayList Size and Capacity

How do we ask an ArrayList how many objects it contains? How do we determine how many objects an ArrayList can contain? To answer these questions, it's important to understand the difference between a list's capacity and its size.

ArrayList Capacity

An ArrayList has a capacity. The capacity refers to the number of elements the ArrayList can hold, or how many it is able to contain. When you construct an ArrayList using the default constructor, the default capacity is 10. This means the list is capable of holding 10 objects. If you use the single-parameter constructor that accepts an integer, you can specify the minimum capacity of the array:

ArrayList<Shape> shapes = new ArrayList<Shape>(5);

This statement creates an ArrayList called shapes with a minimum capacity of 5. This means you have five elements available in which to put objects.

ArrayLists are dynamic, so if you want to increase the capacity of the list so you can add more than 5 objects, you can use the ensureCapacity() method:

shapes.ensureCapacity(7);

This statement changes the minimum capacity of the array by 2, so that it can hold 7 objects.

Don't confuse the capacity of the ArrayList with the size of the ArrayList. The size of the list is the number of elements it actually contains. For example, an array can have a capacity of 7 (it can hold 7 items) but it's size might be 5 (it currently contains 5 objects).

// numbers has a capacity of 5
ArrayList<Integer numbers = new ArrayList<Integer>(5);
numbers.add(25);
numbers.add(42);
numbers.add(7);
// numbers has a size of 3, but still has a capacity of 5

Sometimes your list capacity might be much more than its current size. To save memory in this kind of situation, you should use the trimToSize() method, which trims down the array capacity to be equal to the size.

// numbers has a capacity of 5
ArrayList<Integer numbers = new ArrayList<Integer>(5);
numbers.add(25);
numbers.add(42);
numbers.add(7);
// numbers has a size of 3, but still has a capacity of 5
numbers.trimToSize();
// numbers now has a size of 3 and capacity of 3

To retrieve the size of an ArrayList (the number of objects), use the ArrayList's size() method.

// numbers has a capacity of 5
ArrayList<Integer numbers = new ArrayList<Integer>(5);
numbers.add(25);
numbers.add(42);
numbers.add(7);
// numbers has a size of 3, but still has a capacity of 5
System.out.println(numbers.size()); // prints 3
numbers.trimToSize();
// numbers now has a size of 3 and capacity of 3

If you try to add objects to an ArrayList and it goes beyond its capacity, the ArrayList will simply grow to accommodate more objects. The amount that it grows is stated in the API documentation as "The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost." Basically this means, "we won't say how much it grows by, but know that when it has to grow automatically it costs some resources". However, several (almost all) other resources available online state that the growth rate is 1.5x the current capacity. So if an ArrayList has a capacity of 100 and it is given a 101st element, that ArrayList will increase its capacity to 150. Regardless, if you only needed an extra 5 elements in that array of over 100 elements, that's a lot of wasted resources (even the empty elements take up space). So in that case, it's always a good idea to use trimToSize() when you're finished adding objects.

ArrayList<Integer numbers = new ArrayList<Integer>(100);
fillArrayList(); // fill ArrayList with 100 random numbers
// add 101st element:
numbers.add(4);
// numbers capacity is now 150
numbers.trimToSize();  // now capacity is 101

There is no method that allows to you read the capacity of the ArrayList (generally because we don't care - we can just trim the list down if needed.)

Retrieving Objects and Searching/Sorting an ArrayList

There are several ways you can find and retrieve objects from an ArrayList, and you can also sort ArrayList elements.

Retrieving Objects from the ArrayList

Once you have an ArrayList of objects, you will probably at some point need to retrieve the objects. For example, you might have a collection of grades for which you'd like to calculate the average.

The get() method will retrieve an object at a specified index. This method returns generic type E, where E is the concrete type of the ArrayList:

Shape oneShape = shapes.get(2);

This statement will get the Shape at element 2 and store a reference to that object in the oneShape variable.

If your ArrayList is declared to hold Strings, then the get() method returns a String object:

ArrayList<String> names = new ArrayList<String>();
names.add("Sydney Greenstreet");
names.add("Artemesia Gentileschi");
names.add("Sophie Kurucova");
names.add("Sparrow Widmann");
String cat = names.get(2); // retrieves the 3rd element value Sophie Kurucova

Exercise

Write a program that records course grades from a user using an ArrayList<Double>. Keep asking for grades until the user has no more grades to enter (e.g. you can use a negative input value as a signal to quit, or you can use a yes/no question/answer). Display the average grade, and the standard deviation.

Standard Deviation calculation:

1. Calculate the average.
2. Calculate the variance
   1. For each grade, calculate the difference between the grade and the average grade e.g. grade - avgGrade
   2. Square the difference (result of a.)
   3. Add the square of the difference (result of b.) to a total. After all grades are processed, you'll have the sum of the squares.
   4. Divide the sum of squares (result of 2.c.) by the number of grades. This is the variance.
3. Get the square root of the variance. This is your standard deviation.

Searching for Objects in the ArrayList

There are a variety of ways in which you can search for elements in the ArrayList. Lists allow for direct access to elements so you can easily retrieve an item by its numeric index, but you can also search for objects when you don't know their index. The table below summarizes some of these methods

if (list.indexOf(someItem) >= 0) {
    // code to execute if item exists in list
} else {
    // code to execute if item is NOT in list
}

The contains() method will search for an object in the ArrayList and will return true if the object is found in the list, false otherwise. The following code can be used to see how the contains() method works:

// tests the use of the contains() method
Circle c1 = new Circle(5);
Cylinder cyl1 = new Cylinder(2, 3);
Sphere sphere1 = new Sphere(10);
  
ArrayList<Shape> shapes = new ArrayList<Shape>();
shapes.add(c1);
shapes.add(cyl1);
shapes.add(sphere1);
if (shapes.contains(c1))
System.out.println("found");

The above example prints "found" because the object c1 is found in the list. Note that contains() searches using the object's equals() and hashCode() methods, so it will look through the list for an object that is considered "equal" to the invoking object based on the implementation of equals() and hashCode().

The indexOf() method will take an object and, if it exists in the list, will return the index of the first occurrence of the object in the list. If the object is not found in the list, a -1 value is returned. The lastIndexOf() works similarly, but will return the index of the last occurrence of an object in the list (or a -1 if not found).

// tests the use of the indexOf() method
Circle c1 = new Circle(5);
Cylinder cyl1 = new Cylinder(2, 3);
Sphere sphere1 = new Sphere(10);
  
ArrayList<Shape> shapes = new ArrayList<Shape>();
shapes.add(c1);
shapes.add(cyl1);
shapes.add(sphere1);
System.out.println(shapes.indexOf(new Circle(5)));
if (shapes.indexOf(new Sphere(10) >= 0)
    System.out.println("found");
else
    System.out.println(not found);

Sorting ArrayLists

An ArrayList can be sorted using the sort() method in the Collections class. NOTE that this is not the same as the Collection interface: the interface is called "Collection" and the class is called "Collections" (plural with the s on the end).

The Collections.sort() method will sort the list objects in their natural ascending order: this means that all the objects in the list must implement the Comparable<T> interface and override the compareTo() method.

ArrayList<String> animals = new ArrayList<String>();
animals.add("fish");
animals.add("bird");
animals.add("cat");
animals.add("ferret");
animals.add("hamster");
animals.add("dog");
animals.add("pig");
animals.add("hedgehog");

System.out.println("before:\n" + animals);
Collections.sort(animals);
System.out.println("after:\n" + animals);

To sort in reverse order (descending), you use Collections.reverseOrder(). However, this is not a method you invoke the same way as sort(): reverseOrder() returns a Comparator<T> object that forces the natural ordering of objects that implement Comparable<T> to order in reverse of their natural order. To use it, you pass its return value into the sort method:

ArrayList<String> animals = new ArrayList<String>();
animals.add("fish");
animals.add("bird");
animals.add("cat");
animals.add("ferret");
animals.add("hamster");
animals.add("dog");
animals.add("pig");
animals.add("hedgehog");

System.out.println("before:\n" + animals);
Collections.sort(animals, Collections.reverseOrder());
System.out.println("after:\n" + animals);

Dealing with Common Errors

Be careful when using methods that receive an index as a parameter, such as add(), set(), get(), and remove(). If you try to access an array index that doesn't exist, you'll get an error! For example:

ArrayList<Shape> shapes = new ArrayList<Shape>();
shapes.add(new Cylinder());
shapes.add(new Circle());
shapes.add(new Rectangle());

// exception: inserting new sphere in index 7 creates empty elements
shapes.add(7, new Sphere());

// exception: there is no object in element 10 
Shape oops = shapes.get(10);

// exception: there is no object in element 10
shapes.set(10, new Sphere(2));

// exception: there is no object in element 8
shapes.remove(8);

There are several methods that you can use to avoid these kinds of errors. They are summarized in the following table:

We often use the size() method to ensure that we don't accidentally go beyond the bounds of the ArrayList:

// one example of using size()
for (int i = 0; i < shapes.size(); i++)
    System.out.println(shapes.get(i));

// another example:
System.out.println("Enter the shape you'd like to view.");
int index = scanner.nextInt();
if (index < shapes.size()) {
    Shape s = shapes.get(index);
    System.out.println(s);
} else
    System.out.println("Item not found!");

You can also check to see if an array has any elements in it at all using the isEmpty() method:

if (!shapes.isEmpty())
for (int i = 0; i < shapes.size(); i++)
    System.out.println(shapes.get(i));

Iterators

You will often need to iterate through a collection, and this can be done with an Iterator. An iterator provides a standard and consistent way to iterate through a collection, no matter what kind of collection you want to work with. For example, you can use an iterator to loop through an ArrayList and use an iterator to loop through a HashMap.

Recall that most collections implement the Collection interface. The Collection interface is a sub interface of the java.lang.Iterable interface. Iterable includes a few useful methods, one of which is the iterator() method.

To use an iterator, you use the iterator() method on the collection object, which returns a java.util.Iterator for that collection. (note that java.lang.Iterator is not the same interface as java.util.Iterator) The Iterator contains several methods you can use to process a collection:

Here is an example of how you might use an Iterator:

ArrayList<Shape> shapes = new ArrayList<Shape>();
Scanner in = new Scanner(System.in);

char more = 'Y';
do {
    System.out.print("Enter radius: ");
    double radius = in.nextDouble();
    System.out.print("Enter height (enter 0 if this is a circle): ");
    double height = in.nextDouble();
    if (height <= 0) {
        shapes[shapes.size()] = new Cylinder(radius, height);
    } else {
        shapes[shapes.size()] = new Circle(radius);
    }
    System.out.print("More? (Y/N) ");
    more = in.next().toUpperCase().charAt(0);
} while (more == 'Y');

Iterator<Shape> iterator = shapes.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

There's another technique you can use with functional interfaces, which is covered in an upcoming lesson.

Exercise

Often in applications you need a class that models a list of objects. For example, you might create an EmployeeList class that models a list of Employee objects. Or you could have an InventoryList class that models a list of Inventory item objects. We encapsulate list functionality along with other functions inside our list class. For example, if you wanted to create a list of all of your courses, you could create a Course class with fields for course code, course title, and final grade, then create a CourseList class that models a list of all your courses. The CourseList class could include methods that add and remove courses from the list and calculate the average grade of all the course objects.

There are two ways you can implement this kind of class (here I'm using ArrayList as a collection object, but you can do this with whatever collection is appropriate):

• Composition: Create CourseList class and give it an ArrayList data member that contains all the Course objects.
• Inheritance: Create CourseList as a child of ArrayList so that it is itself an ArrayList of Course objects.

Which technique should you choose? There are several debates online about this issue and which one is "better", including a Wikipedia entry on the subject. In the big picture, one is not always better than the other: there are advantages and disadvantages to both techniques. You will sometimes find that one technique works great for one program but you might prefer the other technique for a different program.

Of course, we are going to do both so you can experience both! :)

Use the UML and notes below to create two versions of CourseList class (Get the Course class here). Compare the two; try using each one in a simple main(). Can you think of where you might prefer one over the other?

Composition Version

• The default constructor just sets up an empty ArrayList with a default capacity of 10.
• The second constructor takes variable-length list of Course objects (or a normal array of Course objects) and adds them to the courseList. Make sure the array isn't empty!
• There is no get/setCourseList(), we won't need these: if we want to set the course list, we'll use the add() method to add courses one-by-one or use the Constructor.
• add() takes a Course object and adds it to the end of the list. add(), according to the Collection contract, returns true if the item was successfully added, and false if it wasn't. You don't need to implement this functionality unless you are up for some extra practice (typically a list is allowed duplicate items but if you wanted, you could change your add() so that duplicate Course objects are not permitted - adding a duplicate would return false instead of adding it to the list).
• remove() removes a course at a specific index and returns that removed Course object.
• size() returns the number of Course objects in courseList.
• average() calculates and returns the average grade of all the Course objects in the list.
• toString() returns a formatted string with each Course object's course code and grade as "PROG241278: 89.5"

Note that most of these methods will be using existing ArrayList methods, and that's totally acceptable and quite normal.

Inheritance Version

Note that this version has no data member for the list of courses because CourseListInherit IS AN ArrayList - the entire object IS the list.

The rest of the methods should function the same way, but you'll find that the implementation is a bit different.

Other Modifications

You might also considering an indexOf(), addAll(Course...), and set() method.