**ArrayLists** An `ArrayList` stores a collection of references to objects. # Arrays * An array is a collection of similar objects. Actually, one of two things: 1. A collection of primitives, all of the same type ~~~~ Java int[] integers; integers = new int[20]; ~~~~ * . 1.   - The first line declares a reference to an array of ints, called **integers**. - The second line allocates space for an array of twenty ints and makes **integers** point to this newly allocated array. 2. A collection of references, all of the same type ~~~~ Java Integer[] integers; integers = new Integer[20]; ~~~~ * . 2.   - The first line declares a reference to an array of `Integer` references, called **integers**. - The second line allocates space for an array of twenty references to `Integer` objects and makes **integers** point to this newly allocated array. - Each element in the array is currently referencing `null` since we haven't created any `Integer` objects. - The following loop will create twenty `Integer` objects and assign the references in the array to point to the newly created `Integer` objects: ~~~~ Java for(int i=0; i < integers.length; ++i) { integers[i] = new Integer(i); } ~~~~ * Arrays are nice because they allow you to store a collection of items in a group **and** act on all of the items in the group in the same way. For example, consider the following method: ~~~~ Java public static void display(PrintStream out, String[] names) { for(int i=0; i < names.length; ++i) { out.println(names[i]); } } ~~~~ * . + We can call `display()` as follows: ~~~~ Java String[] names = {"Peter", "Paul", "Mary-Anne"}; display(System.out, names); ~~~~ * . + The method will display all three names. If **names** had twenty names in it, all twenty would be displayed. + If we wanted to do the same thing without an array, we'd need to hard-code the number of names, like this... ~~~~ Java public static void display(PrintStream out, String name1, String name2, String name3) { out.println(names1); out.println(names2); out.println(names3); } ~~~~ * . + I'm not going to show you what it would look like if we had twenty names because I don't want you to lose your lunch, but just thinking about it is probably enough to make you nauseous. * Arrays are not so nice because they cannot be resized easily. If we want to change the length of the array, we could: 1. Create a new array with the desired size 2. Copy over all the primitive values or references in the old array ~~~~ Java /** * Resizes an array of Strings * @param array Array to be resized * @param size Desired size for the array * @return A reference to the newly sized array */ public static String[] resize(String[] array, int size) { String[] newArray = new String[size]; // Since the size could be less than array.length, we need to make sure // we only go up to the smaller of the two values. for(int i=0; i < array.length && i < size; ++i) { newArray[i] = array[i]; } return newArray; } ~~~~ * . 3. We would then resize an array, **data**, so that it has a length of **12**, we would do the following: ~~~~ Java data = resize(data, 12); ~~~~ * Wait, wouldn't it be nice if we could just start out with an empty array and then just add elements to it as needed? Keep reading because the girls and boys at Oracle have already fulfilled [your wildest dreams](List.htm)![^dreams] # Example Simplified ArrayList Implementation * The [Java Collections Framework](http://docs.oracle.com/javase/8/docs/guide/collections/index.html) provides a few classes that implement the [`List<E>`](http://javadoc.taylorial.com/java.base/util/List.html) interface. * The [`ArrayList<E>`](http://javadoc.taylorial.com/java.base/util/ArrayList.html) class. + This is basically a souped up array. + You can think of this class as containing one instance variable that is a reference to an array and a number of methods that implement the `List<E>` interface. + The actual `ArrayList<E>` implementation is more involved, but a simplified version of the `ArrayList<E>` class might look something like this: ~~~~ Java public class ArrayList<E> implements List<E>, RandomAccess { private E[] elements = null; @Override public boolean isEmpty() { return elements!=null; } @Override public void clear() { elements = null; } @Override public int size() { return elements==null ? 0 : elements.length; } @Override public boolean add(E element) { E[] temp = (E[])new Object[size()+1]; for(int i=0; i < size(); ++i) { temp[i] = get(i); } temp[size()] = element; elements = temp; return true; } @Override public E get(int index) { checkIndexOutOfBounds(index); return elements[index]; } @Override public E set(int index, E element) { checkIndexOutOfBounds(index); E oldElement = get(index); elements[index] = element; return oldElement; } private void checkIndexOutOfBounds(int index) { if(index < 0 || index>=size()) { throw new IndexOutOfBoundsException("Index: " + index + " Size: " + size()); } } // Other methods of the List interface ... } ~~~~ * . + Again, this is a very simplified version of what really goes on. + A more legitimate version of the `ArrayList<E>` class would not force a new array to be created each time `add(E)` was called. + Instead, it is typical to - Create an array that is larger than what is currently required (the size of the array is often referred to as the capacity of the array). - An additional attribute is stored in the `ArrayList<E>` that keeps track of the **size** of the `ArrayList<E>`. - Whenever `add(E)` is called, the size is compared with the capacity in order to determine if it is necessary to create a new array. - Such an implementation is much more efficient. [^dreams]: assuming your wildest dreams are about easily adding elements to a collection of items.