The big picture

Picture a notice on a shop door. Wanted: someone to keep the list of visitors. Must be able to add a name, check if a name is there, and say how many are on the list. The notice says what the job is. It says nothing about who does it. A student, a retired teacher or a very organised parrot could all fill it, as long as they can do those three things.

Java's collections are built the same way. A job description is called an interface. It is a list of methods, with names but no working-out inside. The people who fill the job are classes. A class that does the job is said to implement the interface. List is an interface. ArrayList is one class that implements it. LinkedList is another. Both can do everything the List notice asks for, in their own way.

Most of the framework comes down to four jobs.

• List: items in order, repeats allowed, found by position. Think of a queue of names in a register.
• Set: items with no repeats. Think of a guest list where nobody is invited twice.
• Queue: items waiting their turn. The first to join is the first to be served.
• Map: pairs of a key and a value, where you look up the value by its key. Think of a phone book: name in, number out.

List, Set and Queue share a parent job called Collection: a group of items you can add to, remove from, count and loop over. Map does not share it, because it holds pairs rather than single items.

The habit this lesson wants you to keep is simple. Write your code against the interface, and choose the class in one place. You will see why in a few minutes.

Remember: an interface is the job description, a class is the person. Ask for the job, not the person.

The solid boxes are the interfaces. Collection sits on top, with List, Set and Queue underneath. Under each one are two of the classes you will learn in this course. Map stands apart with its own classes.

Above Collection there is one more interface, Iterable, which is the promise that lets you use a for-each loop on something. You will meet it properly in lesson 5, so we leave it out of the picture for now.

A few things to notice.

• ArrayList and LinkedList do the same job, List, in different ways. Choosing between them is lesson 3 and 4.
• HashSet and TreeSet both refuse repeats, but only one of them keeps its items sorted.
• ArrayDeque and PriorityQueue are both queues, but the second one serves the smallest item first, not the oldest.
• LinkedList also appears under Queue, but we have drawn it only once. It does several jobs.

You don't have to memorise the tree. You have to know that each box is a job, and that the dashed boxes are the people who can do it.

Here is each job in action. Every block below can be pasted into jshell. The <String> part just means "a list of strings". Lesson 2 explains it fully.

A list keeps order and allows repeats.

List<String> queue = new ArrayList<>();
queue.add("Asha");
queue.add("Ravi");
queue.add("Asha"); // a List keeps repeats, and keeps them in order
System.out.println(queue);
System.out.println(queue.get(1));
System.out.println(queue.size());

[Asha, Ravi, Asha]
Ravi
3

Positions start at 0, so get(1) is the second item. That is why it printed Ravi.

A set refuses repeats.

Set<String> seen = new HashSet<>();
seen.add("Asha");
seen.add("Ravi");
boolean changed = seen.add("Asha"); // add reports whether the set grew
System.out.println(changed);
System.out.println(seen.size());
System.out.println(seen.contains("Ravi"));

false
2
true

The second add("Asha") did nothing, and told us so by returning false. A HashSet also makes no promise about the order of its items, which is why we only ask it for its size and whether it contains something.

A queue serves the longest-waiting item first.

Queue<String> line = new ArrayDeque<>();
line.offer("Asha");
line.offer("Ravi");
line.offer("Meera");
System.out.println(line.poll()); // the one who waited longest leaves first
System.out.println(line.peek()); // peek looks, and leaves them there
System.out.println(line.size());

Asha
Ravi
2

offer joins the back of the line. poll takes the person at the front and hands them to you. peek only looks.

A map answers "what goes with this key?"

Map<String, Integer> marks = new HashMap<>();
marks.put("Asha", 82);
marks.put("Ravi", 74);
marks.put("Asha", 90); // same key again: the old value is replaced
System.out.println(marks.get("Asha"));
System.out.println(marks.get("Kiran")); // no such key gives null
System.out.println(marks.getOrDefault("Kiran", 0));
System.out.println(marks.size());

90
null
0
2

Putting "Asha" a second time replaced her mark, so the map still has two entries. Asking for a key that isn't there gives null, which means "nothing here". getOrDefault lets you pick the answer to use instead.

Now the habit. Look at this method.

static int countLong(Collection<String> words) {
    // Collection is the widest promise that still lets us loop, so this
    // one method serves lists, sets and queues alike.
    int count = 0;
    for (String word : words) {
        if (word.length() > 4) {
            count++;
        }
    }
    return count;
}

It says Collection<String> and not ArrayList<String>. It only needs to loop, and every collection can be looped over, so it asks for the widest job and works with everything that fills it.

List<String> fromList = List.of("tea", "coffee", "water");
Set<String> fromSet = Set.of("juice", "tea");
System.out.println(countLong(fromList));
System.out.println(countLong(fromSet));

2
1

We passed it a list, then a set. (List.of and Set.of build small, fixed collections. Lesson 10 looks at them.) The method did not care which. If it had demanded an ArrayList, the set could not have gone in.

The same idea applies to variables. Write the job on the left and the person on the right:

List<String> a = new ArrayList<>();
List<String> b = new LinkedList<>();
for (List<String> list : List.of(a, b)) {
    // The loop only knows "List", so it cannot tell the two apart.
    list.add("tea");
    list.add("coffee");
    System.out.println(list.size() + " " + list.get(0));
}

2 tea
2 tea

The loop treats a and b as plain Lists, so it works for both. If you later find that a LinkedList suits your program better, you change the word ArrayList in one place and nothing else.

Remember: List<String> names = new ArrayList<>(); says "I need a list" on the left, and "here is who will be the list" on the right. Keep the left side as wide as you can.

When you call names.add("Asha"), Java looks at the real object behind names and runs its version of add. If the object is an ArrayList, you get the ArrayList way. If it is a LinkedList, you get that way. This is called polymorphism, a long word for "the same call, different behaviour depending on the object". It is what makes the habit work.

Two honest cautions follow.

The interface does not promise speed. List.get(5) is instant on an ArrayList and slow on a LinkedList. Both are correct Lists. The interface only promises the behaviour. The cost belongs to the class, and the class pages in this course give you the cost tables.

Some jobs are filled only in part. A list made with List.of(...) is a real List, but it cannot change, so add on it throws an UnsupportedOperationException. The interface lists add, but says it is optional for a class to support it. That is a quirk to be aware of. We come back to it in lesson 10.

Finally, why is Map not a Collection? A Collection is a group of single items. A Map is a group of pairs, so methods like add(item) have no sensible meaning for it. It is still part of the framework. You can ask a map for its keys, its values, or its entries, and each of those is a Collection or a Set.

The four jobs answer four different questions. A typical class for each one is shown with what it is quick at.

"On average" matters for hashing. A HashSet or HashMap is quick in the usual case, and lesson 6 explains the rare case where it is not.

Notice what each class is not quick at. Asking an ArrayList "do you contain Ravi?" means looking at items one by one, which is O(n). Lesson 11 turns this table into a full guide for choosing.

Each problem is solved best by picking the right job first. Ask yourself what question the problem is really asking, then pick the interface that answers it.

static int countDistinct(List<String> words) {
    throw new UnsupportedOperationException("how many different words are there?");
}

static int countDistinct(List<String> words) {
    // A Set refuses repeats on its own, so its size is the answer.
    return new HashSet<>(words).size();
}

static Map<String, Integer> wordCounts(List<String> words) {
    throw new UnsupportedOperationException("map each word to how often it appears");
}

static Map<String, Integer> wordCounts(List<String> words) {
    Map<String, Integer> counts = new HashMap<>();
    for (String word : words) {
        // getOrDefault covers the first sighting, when there is no count yet.
        counts.put(word, counts.getOrDefault(word, 0) + 1);
    }
    return counts;
}

static String firstRepeat(List<String> words) {
    throw new UnsupportedOperationException("the first word that shows up a second time");
}

static String firstRepeat(List<String> words) {
    Set<String> seen = new HashSet<>();
    for (String word : words) {
        if (!seen.add(word)) { // add is false when the word was already there
            return word;
        }
    }
    return null; // null stands for "no repeat" here; later lessons show tidier ways
}

Questions about the framework's shape come early in a Java interview. They are easy to answer if you keep the job-and-person picture in your head.

• "Why List<String> x = new ArrayList<>() and not ArrayList<String> x = ...?" Because the variable should state what job you need, and the right side states who does it. Then you can change the class in one place, and methods that take a List accept any kind.
• "Is Map a Collection?" No. Collection is for single items, and Map holds key and value pairs. They are separate branches of the framework.
• "What is the difference between Collection and Collections?" Collection is the interface at the top of the tree. Collections, with an s, is a class full of helper methods such as sorting and reversing. Lesson 10 covers it.
• "List or Set?" Do you need repeats and positions, or do you need each item at most once? Say what you need before you say a class name.
• "What does a queue's poll do when the queue is empty?" It returns null. The method remove on a queue throws a NoSuchElementException instead. Knowing that both exist, and which one is the gentle one, shows you've used them.
• Say the cost with the class. "A List gives me get-by-position, but whether that is O(1) depends on whether it is an ArrayList or a LinkedList." That sentence shows you know an interface makes no promise about speed.

Made by VeraStack Labs