ArrayLists and Generics

So far, we have learned two ways of storing collections of data: arrays, and linked lists. They have different benefits and drawbacks, and so are used for different things.

In arrays, access is lighting fast; if we know the index of our element, retrieving it is very, very quick. However, if we want to resize the array, this is very slow (what do you need to do to accomplish this?).

In linked lists, however, the opposite is true; adding an element is very quick, but in order to get to the i-th element, you have to walk along the linked list, which is very slow.

This is important stuff! The way you store your data can determine how fast it runs. You will get very good at talking about these differences in Data Structures!

Java has lots and lots of ways to store data built in. One of the most commonly used is the ArrayList. The ArrayList is a class that is implemented as an array, so you can get to elements easily, but it will automatically resize the array if you fill it up so that you can easily add stuff and not have to worry about "resizing" the array. It does this in smart, fast ways, trading more memory usage for a faster implementation.

Using it looks something like this:

  ArrayList myList = new ArrayList();
  myList.add(new Book("Breakfast of Champions")); //appends new book to myList
  myList.add(new Book("Bluebeard"));
  Book b = myList.get(0);

What type do you suppose .add() accepts? ArrayLists are stated to work for all Objects, so it seems it must take an Object, right? And .get() must return an Object?

  public class ArrayList {
    private Object[] theArray;
    //...
    public Object get(int elt) {
    //...
    public void add(Object o) {
    //...
  }

However, this is NOT what is done. Every time we called .get(), we would have to do a cast: Book b = (Book) myList.get(0).

What we want is to state when we build the ArrayList that only Books will go into the ArrayList; then, we can assume when we call get() that it will be a Book. We do this with what in Java we call "Generics". In C++ they're called Templates.

This requires a new syntax to tell the compiler what the type of the array should be:

  ArrayList<Book> myList = new ArrayList<Book>();
  myList.add(new Book("Breakfast of Champions")); //appends new book to myList
  myList.add(new Book("Bluebeard"));
  Book b = myList.get(0);

That's it. Now you can just use the ArrayList as if it only contains Books. We can still do Polymorphism with it if we want (in this example, assume Book extends Literature):

  ArrayList<Literature> myList = new ArrayList<Literature>();
  myList.add(new Book("Breakfast of Champions")); //appends new book to myList
  myList.add(new Book("Bluebeard"));
  Literature b = myList.get(0);

Inside ArrayList, this looks like this:

  public class ArrayList<E> {
    private E [] theArray;
    //...
    public E get(int elt) {
    //...
    public void add(E e) {
    //...
  }

Java is littered with helpful classes like ArrayList that use generics (we've played some with LinkedList).

Many of these classes implement a special interface, that enables us to loop through them easily. The interface is the "Iterable" interface. For any class that correctly implements the Iterable interface, you can loop across it with the "foreach" loop:

  ArrayList<Book> lib = new ArrayList<book>();
        //...
  for (Book b : lib) {
      System.out.println(b);
  }

Each pass through the loop, the variable (in this case b) takes the value of the next item in the ArrayList.