Beyond arrays: the Collections Framework

Written Explanation

The three limits of arrays

An array has a size fixed when you create it.

String[] arr = new String[3];
arr[0] = "Ana"; arr[1] = "Omar"; arr[2] = "Lina";
arr[3] = "Sam";   // fails at run time

The fourth assignment throws an ArrayIndexOutOfBoundsException with the message Index 3 out of bounds for length 3. The array cannot grow. If you want room for a fourth name you must create a bigger array and copy everything over yourself.

Three limits follow from this design:

1. Fixed size. You must know the number of elements in advance, or waste space, or copy.
2. Awkward adding and removing. Removing the middle name means shifting every later name one place to the left by hand.
3. Only position access. "Is Omar in here?" means writing a loop. There is no notion of "unique" or "look up by key".

Collections grow and shrink for you

The same task with a collection:

List<String> names = new ArrayList<>();
names.add("Ana"); names.add("Omar"); names.add("Lina");
names.add("Sam");              // no problem: the list grows
names.remove("Omar");          // later items shift for us

Printing it gives [Ana, Lina, Sam]. The collection manages its own storage. The Java documentation describes ArrayList as a "resizable-array implementation" of List: inside there is still an array, but the class replaces it with a larger one when needed, so you do not have to.

The four main kinds

List, Set, and Queue are all kinds of Collection (a group of elements). A Map is the odd one out: it is not a Collection, because it stores pairs rather than single elements. Each of these four is an interface: a contract (BEG-024). The classes that do the work are implementations: ArrayList and LinkedList for lists, HashSet and TreeSet for sets, HashMap and TreeMap for maps, ArrayDeque for queues. Lessons 2 to 5 take them one family at a time, and Lesson 6 gives a decision chart.

Where they live: java.util

All of these are in the java.util package, so you import them (BEG-027):

import java.util.List;
import java.util.ArrayList;
// or all at once
import java.util.*;

Without the import, the compiler cannot find the name and reports an error.

Reading List<String>

The part in angle brackets says what the collection holds. List<String> is "a list of strings", and Map<String, Integer> is "a map from strings to integers". The compiler uses it to stop you putting the wrong kind of thing in. How this works is the subject of BEG-031 (generics); for now, just read and write it.

One consequence you can use today: the type in the brackets must be a reference type. List<int> does not compile; the compiler says unexpected type, required: reference, found: int. For numbers, use the wrapper class: List<Integer>. Java converts between int and Integer automatically in most places (called autoboxing), so list.add(5) works on a List<Integer>. We will rely on this and flag the few places where it surprises people.

Declare by interface, create by class

Look closely at this line:

List<String> names = new ArrayList<>();

The variable type is the interface List. The object is an ArrayList. The <> after ArrayList is the diamond: you leave it empty and the compiler fills in String from the left-hand side.

Why not ArrayList<String> names = new ArrayList<>();? Both compile. The interface version says "I only need list behavior", which is true of almost all code. The benefit is flexibility: if you later decide a LinkedList fits better, you change one word on the right-hand side and nothing else in the code breaks, because everything else only used List methods. This is "programming to an interface" from BEG-024-L05, applied to collections. A method that only needs to read items can go even more general and accept a Collection.