Session 12 — Interfaces, List, Map, and TreeMap

By this point in the Java track you can build classes, tuck fields behind getters, and grow data with ArrayList. The next hurdle is not syntax—it is how to think about types when a program grows.

Large programs stay pleasant when you depend on capabilities (“something I can iterate,” “something that maps keys to values”) instead of on one concrete class name everywhere. Java’s interfaces are the language feature for that: they list what you can do without pinning down how it is implemented under the hood.

This session walks the collections library through that lens. You will see List and its workhorse implementation ArrayList, then Map and two implementations—TreeMap (keys stay sorted when you walk them) and HashMap (fast lookups, no promised iteration order). We also nod to Set, which is the right shape when you care about membership and uniqueness rather than order.

Polymorphism here simply means: if a method asks for a List<String>, you may hand it any list implementation that honours the contract. Your calling code stays stable when you swap implementations for performance or testing.

Give yourself permission to read slowly. Draw little boxes on paper—list versus map—whenever you feel fuzzy. The ideas are older than Java; the syntax is just the local dialect.

Time: about 90 minutes.

1. Interface as a contract (in everyday words)

An interface is a promise written down in code. It says: “any type that claims to implement me must provide these methods, with these signatures.” It deliberately does not say how the methods work inside—that is the job of each concrete class.

Here is a toy interface:

public interface Named {
    String name();
}

Anything that implements Named must supply a real name() method. Callers can write methods that accept a Named without caring whether the object is a Person, a Robot, or a Project—only that you can ask for a name.

That substitutability—passing a subtype where a supertype is expected—is the heart of polymorphism in this session. You are not chasing object-oriented buzzwords; you are buying flexibility so that one piece of code can serve many concrete types.

---

2. List versus ArrayList: say what you need, choose what you use

A List<E> is an ordered sequence: duplicates are allowed, you can ask for get(i), size(), add(x), and you can iterate in order. The interface does not promise how growth happens when you append.

ArrayList<E> is the common implementation: a resizable array under the hood, fast random access, amortised fast appends at the end. LinkedList<E> is another List—different trade-offs (fast inserts in the middle if you already have a node reference; slower random access by index).

When you declare a variable or a parameter, prefer the interface if callers should not care which implementation you picked:

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

Why bother? Because tomorrow you might profile and decide LinkedList fits better—or a unit test might pass a different List implementation—and method signatures that say List<String> often stay untouched. If you spray ArrayList across every public method, you have accidentally promised a growth strategy your callers never asked for.

---

3. Map: look up by key, not by position

A Map<K,V> answers a different question than a list. Instead of “what lives at index 7?” you ask “what value is paired with this key?” Keys are unique in the usual map story: put(k, v) inserts or replaces the value for k.

Core vocabulary: put(k,v), get(k), containsKey(k), remove(k), keySet(), entrySet().

Map<String, Integer> counts = new TreeMap<>();
counts.put("apples", 3);
counts.put("bananas", 1);

Unlike a list, there is no inherent integer index for “second banana” unless you invent one. Maps are associative—think dictionary, phone book, configuration table.

---

4. Set: when duplicates should not exist

A Set<E> models a bag where either an element is present or it is not—no duplicate membership, no positional story unless you impose one externally. HashSet<E> is the usual default implementation: fast contains, iteration order not promised.

Use a set when you are counting distinct visitors, tracking seen IDs, or taking the union of two groups without fussing about how many copies someone tried to insert.

---

5. TreeMap versus HashMap: sorted keys versus fast chaos

TreeMap keeps keys sorted—for String, lexicographic order unless you supply a Comparator. When you iterate keySet() or entrySet(), you visit keys in sorted order. That is wonderful when you diff two runs of a program, print a report for humans, or want reproducible output in homework autograders.

HashMap offers expected O(1) lookups for many workloads and is often the right default for speed. The catch: iteration order is not part of the contract—do not build logic that assumes keys print in insertion order on every JDK or every run.

If coursework says “compare your output file to ours,” TreeMap can save you from “same multiset, different print order” false failures.

---

6. Generics on collections (a calm reminder)

List<String> is a promise to the compiler: this list is meant to hold strings. The compiler stops you from add(42) by mistake. At runtime, generics are mostly erased to raw types for compatibility with old code—but the compile-time checks already saved you from a class of ClassCastException surprises.

Raw types like plain List without a type argument still compile for legacy reasons; treat them like uncovered hot pans. Prefer type arguments, or wildcards (? extends, ? super) when you learn them in a later session, over raw collections.

---

7. Wrapper classes and autoboxing

Collections store objects, not primitives — so List<int> and Map<String, int> do not compile. Java bridges the gap with wrapper classes: Integer, Double, Boolean, Character, and friends each wrap one primitive value in an object.

Integer count = 42;          // autoboxing: int 42 → Integer object
int back = count;            // unboxing: Integer object → int
List<Integer> scores = new ArrayList<>();
scores.add(9);               // autoboxing inside add
int top = scores.get(0);     // unboxing on read

Autoboxing converts a primitive to its wrapper automatically; unboxing goes the other way. Both happen silently in assignments, arguments, and arithmetic:

Map<String, Integer> freq = new TreeMap<>();
freq.put("apple", freq.getOrDefault("apple", 0) + 1);  // int → Integer → int → Integer

Wrappers also carry static helpers you already used: Integer.parseInt("42"), Integer.compare(a, b), Double.parseDouble.

Three caveats:

• == compares identities, not values for Integer — two boxed values that look equal may be different objects. Always compare with .equals (or intValue()), or unbox first.
• Autoboxing has a small cost. In tight loops, keep arithmetic in primitives (int), not Integer.
• null becomes a trap. An unboxed null throws NullPointerException; a missing map key returns null and unboxing it crashes.

---

8. Polymorphism in practice: where to use interfaces in APIs

When you write a helper, ask: “does my caller care that this is an ArrayList, or do they only care that it is some ordered collection?” If the latter, take List (or even Collection when order truly does not matter).

Construct concrete classes at the edges: reading a file, parsing input, choosing a particular map for reproducible output. The middle of your program can stay expressed in interfaces so it stays easy to test and easy to refactor.

---

9. Common pitfalls (read once, then reread after your first bug)

• Declaring every public API as ArrayList locks callers to that implementation and leaks growth details.
• Using == on strings instead of .equals—collections do not fix that; string content equality is still .equals (or helpers such as Objects.equals).
• Assuming map.get(missingKey) throws—it usually returns null. Prefer containsKey or getOrDefault so absent keys are explicit, not silent.
• Comparing wrappers with ==—use .equals or unbox to a primitive first.

---

If this feels abstract

That is fair. After you read once, open a tiny main in your IDE and build a TreeMap, insert keys out of order, print the map, and watch the keys come out sorted. Physical manipulation beats staring at bullets.

Example A — a roster you can pass around without naming ArrayList

Suppose you are building a teaching helper: you have a method that should print every name in a group. You do not want to force callers to build an ArrayList specifically—they might already have a LinkedList, or a list returned from another library.

import java.util.ArrayList;
import java.util.List;

public class Roster {
    public static List<String> sample() {
        List<String> people = new ArrayList<>();
        people.add("Asha");
        people.add("Ben");
        people.add("Chen");
        return people;
    }

    public static void printAll(List<String> people) {
        for (String p : people) {
            System.out.println(p);
        }
    }
}

Why this matters. sample still constructs an ArrayList because that is what you chose today. But printAll only promises “I need something list-shaped.” A teammate could pass a different List implementation without changing printAll at all.

Try a tiny experiment. In main, call printAll(List.of("solo")). List.of does not return an ArrayList, yet the method works—because the parameter type was the interface, not the concrete class.

---

Example B — word counts with a TreeMap so output behaves politely

Imagine counting words in a tiny corpus. You want the final printout sorted alphabetically by word so it matches a reference file in an autograder—or simply so humans can scan it.

import java.util.Map;
import java.util.TreeMap;

public class WordCounts {
    public static void main(String[] args) {
        Map<String, Integer> freq = new TreeMap<>();
        bump(freq, "delta");
        bump(freq, "alpha");
        bump(freq, "delta");
        for (Map.Entry<String, Integer> e : freq.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }
    }

    private static void bump(Map<String, Integer> freq, String word) {
        freq.put(word, freq.getOrDefault(word, 0) + 1);
    }
}

Walk the story. First insertion: "delta" maps to 1. Second: "alpha" maps to 1. Third: "delta" again—keys are unique, so the value becomes 2.

Walk the print order. Because the map is a TreeMap, iteration visits keys in sorted string order: alpha before delta. If you swapped in a HashMap, you might still see correct counts, but the lines could appear in an order that surprises you when diffing files.

Tiny style note. bump takes Map<String, Integer> rather than TreeMap so you could swap implementations later without touching call sites—same lesson as Example A, now for maps.