Generic Array Lists | Core Java(TM) 2, Volume I--Fundamentals (7th Edition) (Core Series) (Core Series)

In many programming languages in particular, in C you have to fix the sizes of all arrays at compile time. Programmers hate this because it forces them into uncomfortable trade-offs. How many employees will be in a department? Surely no more than 100. What if there is a humongous department with 150 employees? Do we want to waste 90 entries for every department with just 10 employees?

In Java, the situation is much better. You can set the size of an array at run time.

 int actualSize = . . .; Employee[] staff = new Employee[actualSize];

Of course, this code does not completely solve the problem of dynamically modifying arrays at run time. Once you set the array size, you cannot change it easily. Instead, the easiest way in Java to deal with this common situation is to use another Java class, classed ArrayList. The ArrayList class is similar to an array, but it automatically adjusts its capacity as you add and remove elements, without your needing to write any code.

As of JDK 5.0, ArrayList is a generic class with a type parameter. To specify the type of the element objects that the array list holds, you append a class name enclosed in angle brackets, such as ArrayList<Employee>. You will see in Chapter 13 how to define your own generic class, but you don't need to know any of those technicalities to use the ArrayList type.

Here we declare and construct an array list that holds Employee objects:

 ArrayList<Employee> staff = new ArrayList<Employee>();

NOTE

Before JDK 5.0, there were no generic classes. Instead, there was a single ArrayList class, a "one size fits all" collection that holds elements of type Object. If you must use an older version of Java, simply drop all <...> suffixes. You can still use ArrayList without a <...> suffix in JDK 5.0 and beyond. It is considered a "raw" type, with the type parameter erased.

NOTE

In even older versions of the Java programming language, programmers used the Vector class for dynamic arrays. However, the ArrayList class is more efficient, and there is no longer any good reason to use the Vector class.

You use the add method to add new elements to an array list. For example, here is how you populate an array list with employee objects:

 staff.add(new Employee("Harry Hacker", . . .)); staff.add(new Employee("Tony Tester", . . .));

The array list manages an internal array of object references. Eventually, that array will run out of space. This is where array lists work their magic: If you call add and the internal array is full, the array list automatically creates a bigger array and copies all the objects from the smaller to the bigger array.

If you already know, or have a good guess, how many elements you want to store, then call the ensureCapacity method before filling the array list:

 staff.ensureCapacity(100);

That call allocates an internal array of 100 objects. Then the first 100 calls to add do not involve any costly relocation.

You can also pass an initial capacity to the ArrayList constructor:

 ArrayList<Employee> staff = new ArrayList<Employee>(100);

CAUTION

Allocating an array list as

 new ArrayList<Employee>(100) // capacity is 100

is not the same as allocating a new array as

 new Employee[100] // size is 100

There is an important distinction between the capacity of an array list and the size of an array. If you allocate an array with 100 entries, then the array has 100 slots, ready for use. An array list with a capacity of 100 elements has the potential of holding 100 elements (and, in fact, more than 100, at the cost of additional relocations), but at the beginning, even after its initial construction, an array list holds no elements at all.

The size method returns the actual number of elements in the array list. For example,

 staff.size()

returns the current number of elements in the staff array list. This is the equivalent of

 a.length

for an array a.

Once you are reasonably sure that the array list is at its permanent size, you can call the TRimToSize method. This method adjusts the size of the memory block to use exactly as much storage space as is required to hold the current number of elements. The garbage collector will reclaim any excess memory.

Once you trim the size of an array list, adding new elements will move the block again, which takes time. You should only use trimToSize when you are sure you won't add any more elements to the array list.

C++ NOTE

The ArrayList class is similar to the C++ vector template. Both ArrayList and vector are generic types. But the C++ vector template overloads the [] operator for convenient element access. Because Java does not have operator overloading, it must use explicit method calls instead. Moreover, C++ vectors are copied by value. If a and b are two vectors, then the assignment a = b makes a into a new vector with the same length as b, and all elements are copied from b to a. The same assignment in Java makes both a and b refer to the same array list.

 java.util.ArrayList<T> 1.2

ArrayList<T>()
constructs an empty array list.
ArrayList<T>(int initialCapacity)
constructs an empty array list with the specified capacity.
Parameters:
initialCapacity
the initial storage capacity of the array list
boolean add(T obj)
appends an element at the end of the array list. Always returns true.
Parameters:
obj
the element to be added
int size()
returns the number of elements currently stored in the array list. (This is different from, and, of course, never larger than, the array list's capacity.)
void ensureCapacity(int capacity)
ensures that the array list has the capacity to store the given number of elements without relocating its internal storage array.
Parameters:
capacity
the desired storage capacity
void trimToSize()
reduces the storage capacity of the array list to its current size.

Accessing Array List Elements

Unfortunately, nothing comes for free. The automatic growth convenience that array lists give requires a more complicated syntax for accessing the elements. The reason is that the ArrayList class is not a part of the Java programming language; it is just a utility class programmed by someone and supplied in the standard library.

Instead of using the pleasant [] syntax to access or change the element of an array, you use the get and set methods.

For example, to set the ith element, you use

 staff.set(i, harry);

This is equivalent to

 a[i] = harry;

for an array a. (As with arrays, the index values are zero-based.)

To get an array list element, use

 Employee e = staff.get(i);

This is equivalent to

 Employee e = a[i];

As of JDK 5.0, you can use the "for each" loop for array lists:

 for (Employee e : staff)    // do something with e

In legacy code, the same loop would be written as

for (int i = 0; i < staff.size(); i++)
{
Employee e = (Employee) staff.get(i);
do something with e
}

NOTE

Before JDK 5.0, there were no generic classes, and the get method of the raw ArrayList class had no choice but to return an Object. Consequently, callers of get had to cast the returned value to the desired type:

 Employee e = (Employee) staff.get(i);

The raw ArrayList is also a bit dangerous. Its add and set methods accept objects of any type. A call

 staff.set(i, new Date());

compiles without so much as a warning, and you run into grief only when you retrieve the object and try to cast it. If you use an ArrayList<Employee> instead, the compiler will detect this error.

TIP

You can sometimes get the best of both worlds flexible growth and convenient element access with the following trick. First, make an array list and add all the elements.

 ArrayList<X> list = new ArrayList<X>(); while (. . .) {    x = . . .;    list.add(x); }

When you are done, use the toArray method to copy the elements into an array.

 X[] a = new X[list.size()]; list.toArray(a);

CAUTION

Do not call list.set(i, x) until the size of the array list is larger than i. For example, the following code is wrong:

 ArrayList<Employee> list = new ArrayList<Employee>(100); // capacity 100, size 0 list.set(0, x); // no element 0 yet

Use the add method instead of set to fill up an array, and use set only to replace a previously added element.

Instead of appending elements at the end of an array list, you can also insert them in the middle.

 int n = staff.size() / 2; staff.add(n, e);

The elements at locations n and above are shifted up to make room for the new entry. If the new size of the array list after the insertion exceeds the capacity, then the array list reallocates its storage array.

Similarly, you can remove an element from the middle of an array list.

 Employee e = staff.remove(n);

The elements located above it are copied down, and the size of the array is reduced by one.

Inserting and removing elements is not terribly efficient. It is probably not worth worrying about for small array lists. But if you store many elements and frequently insert and remove in the middle of a collection, consider using a linked list instead. We explain how to program with linked lists in Volume 2.

Example 5-4 is a modification of the EmployeeTest program of Chapter 4. The Employee[] array is replaced by an ArrayList<Employee>. Note the following changes:

You don't have to specify the array size.
You use add to add as many elements as you like.
You use size() instead of length to count the number of elements.
You use a.get(i) instead of a[i] to access an element.

Example 5-4. ArrayListTest.java

  1. import java.util.*;  2.  3. public class ArrayListTest  4. {  5.    public static void main(String[] args)  6.    {  7.       // fill the staff array list with three Employee objects  8.       ArrayList<Employee> staff = new ArrayList<Employee>();  9. 10.       staff.add(new Employee("Carl Cracker", 75000, 1987, 12, 15)); 11.       staff.add(new Employee("Harry Hacker", 50000, 1989, 10, 1)); 12.       staff.add(new Employee("Tony Tester", 40000, 1990, 3, 15)); 13. 14.       // raise everyone's salary by 5% 15.       for (Employee e : staff) 16.          e.raiseSalary(5); 17. 18.       // print out information about all Employee objects 19.       for (Employee e : staff) 20.          System.out.println("name=" + e.getName() 21.             + ",salary=" + e.getSalary() 22.             + ",hireDay=" + e.getHireDay()); 23.    } 24. } 25. 26. class Employee 27. { 28.    public Employee(String n, double s, int year, int month, int day) 29.    { 30.       name = n; 31.       salary = s; 32.       GregorianCalendar calendar = new GregorianCalendar(year, month - 1, day); 33.       hireDay = calendar.getTime(); 34.    } 35. 36.    public String getName() 37.    { 38.       return name; 39.    } 40. 41.    public double getSalary() 42.    { 43.       return salary; 44.    } 45. 46.    public Date getHireDay() 47.    { 48.       return hireDay; 49.    } 50. 51.    public void raiseSalary(double byPercent) 52.    { 53.       double raise = salary * byPercent / 100; 54.       salary += raise; 55.    } 56. 57.    private String name; 58.    private double salary; 59.    private Date hireDay; 60. }

 java.util.ArrayList<T> 1.2

void set(int index, T obj)
puts a value in the array list at the specified index, overwriting the previous contents.
Parameters:
index
the position (must be between 0 and size() - 1)

obj
the new value
T get(int index)
gets the value stored at a specified index.
Parameters:
index
the index of the element to get (must be between 0 and size() - 1)
void add(int index, T obj)
shifts up elements to insert an element.
Parameters:
index
the insertion position (must be between 0 and size())

obj
the new element
T remove(int index)
removes an element and shifts down all elements above it. The removed element is returned.
Parameters:
index
the position of the element to be removed (must be between 0 and size() -1)

Compatibility Between Typed and Raw Array Lists

When you write new code with JDK 5.0 and beyond, you should use type parameters, such as ArrayList<Employee>, for array lists. However, you may need to interoperate with existing code that uses the raw ArrayList type.

Suppose that you have the following legacy class:

 public class EmployeeDB {    public void update(ArrayList list) { ... }    public ArrayList find(String query) { ... } }

You can pass a typed array list to the update method without any casts.

 ArrayList<Employee> staff = ...; employeeDB.update(staff);

The staff object is simply passed to the update method.

CAUTION

Even though you get no error or warning from the compiler, this call is not completely safe. The update method might add elements into the array list that are not of type Employee. When these elements are retrieved, an exception occurs. This sounds scary, but if you think about it, the behavior is simply as it was before JDK 5.0. The integrity of the virtual machine is never jeopardized. In this situation, you do not lose security, but you also do not benefit from the compile-time checks.

Conversely, when you assign a raw ArrayList to a typed one, you get a warning.

 ArrayList<Employee> result = employeeDB.find(query); // yields warning

NOTE

To see the text of the warning, compile with the option -Xlint:unchecked.

Using a cast does not make the warning go away.


 ArrayList<Employee> result = (ArrayList<Employee>) employeeDB.find(query); // yields  another warning

Instead, you get a different warning, telling you that the cast is misleading.

This is the consequence of a somewhat unfortunate limitation of parameterized types in Java. For compatibility, the compiler translates all typed array lists into raw ArrayList objects after checking that the type rules were not violated. In a running program, all array lists are the same there are no type parameters in the virtual machine. Thus, the casts (ArrayList) and (ArrayList<Employee>) carry out identical runtime checks.

There isn't much you can do about that situation. When you interact with legacy code, study the compiler warnings and satisfy yourself that the warnings are not serious.