PHASE 9Intermediate ~30 min· topic 1 of 13

Topic 9.1

The Collections Map

In one line

The Collections Framework is a family of interfaces (List, Set, Queue, Deque, Map) and the classes that implement them (ArrayList, HashSet, HashMap, ArrayDeque and more). You choose an interface for the behaviour you need and an implementation for the performance you need.

Think of it like this

Think of the ways you keep things at home. A shopping list keeps items in the order you wrote them, and "milk" can appear twice. A stamp album keeps each stamp at most once. A phone book lets you look up a number by a name. The queue at a ticket counter serves whoever came first. Java has one container type for each of these habits: List, Set, Map and Queue.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Collection: An object that holds a group of other objects. Also the name of the interface java.util.Collection.
Element: One item stored inside a collection.
Interface: A list of operations a type promises to support, without saying how. List is an interface.
Implementation: A real class that does the work an interface promises. ArrayList is an implementation of List.
Key and value: In a map, the key is what you look up by (a name) and the value is what you get back (a phone number).
View: A collection that shows another collection's data without copying it. map.keySet() is a view: change the map and the view changes too.
Big-O: A way to say how the time of an operation grows as the collection grows. O(1) means it stays about the same; O(n) means it grows in step with the size.
Autoboxing: Java automatically wrapping a primitive like int into its object form Integer so it can go into a collection.

Step by step

01Four habits, four interfaces

Ask one question first: what do I need to do with the group? Keep order and allow repeats: List. Never allow repeats: Set. Look up by a key: Map. Process in arrival or priority order: Queue or Deque.

Only then pick the class. The interface is the promise, the class is the engine. The rest of this phase opens each engine.

Four habits, four interfacesdiagram

Rendering diagram…

02Program to the interface

Write List<String> names = new ArrayList<>();, not ArrayList<String> names = .... The variable's type is the promise you rely on; the object's class is a detail you may swap later (say, for a LinkedList or an unmodifiable list) without touching any other line.

Parameters matter even more. A method static int countLong(Collection<String> words) accepts a list, a set or a queue. A method that demands ArrayList<String> forces every caller to copy their data into an ArrayList first.

Main.javawhole filejava

List<String> names = new ArrayList<>();   // good: interface on the left
Map<String, Integer> stock = new HashMap<>();

static int countLong(Collection<String> words) {   // accepts List, Set, Queue...
    int n = 0;
    for (String w : words) if (w.length() > 4) n++;
    return n;
}

03The operations every Collection shares

Collection gives every list, set and queue the same core: add(e), remove(o), contains(o), size(), isEmpty(), clear(), addAll, removeAll, retainAll, iterator(), and since Java 8 removeIf, stream() and forEach.

contains and remove(Object) use equals to decide what matches. That is why Topic 4.8 matters here: a class without a proper equals can't be found in any collection by value.

Some operations are optional: an unmodifiable list still has an add method, but it throws UnsupportedOperationException. The interface lists the method; the implementation may refuse it (Topic 9.11).

04Map is a separate tree

A Map<K, V> stores entries: pairs of a key and a value. Keys are unique (like a Set); values may repeat. put(k, v) adds or replaces, get(k) returns the value or null, containsKey, remove(k), and since Java 8 getOrDefault, putIfAbsent, merge, computeIfAbsent.

A map isn't a Collection because "add one element" doesn't make sense for pairs. Instead it offers three views: keySet() (a Set<K>), values() (a Collection<V>) and entrySet() (a Set<Map.Entry<K, V>>). Removing a key from keySet() removes the entry from the map.

Main.javawhole filejava

Map<String, Integer> stock = new TreeMap<>();
stock.put("tea", 5);
stock.put("cake", 2);
stock.merge("tea", 3, Integer::sum);            // tea is now 8
for (Map.Entry<String, Integer> e : stock.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}

05The cost table you'll fill in

Each implementation is a data structure from the DSA course with a Java name: ArrayList is a growable array, LinkedList a doubly linked list, HashMap a hash table, TreeMap a red-black tree, PriorityQueue a binary heap, ArrayDeque a circular array.

The table below is the summary of this whole phase. Topics 9.2 to 9.8 explain where each number comes from; Topic 9.13 turns it into a decision guide.

big-o.txtwhole filetext

                 get(i)   add(end)   add/remove middle   contains   sorted?
ArrayList        O(1)     O(1)*      O(n)                O(n)       no
LinkedList       O(n)     O(1)       O(1) at iterator    O(n)       no
HashSet/HashMap  -        O(1)~      O(1)~ remove        O(1)~      no
LinkedHash*      -        O(1)~      O(1)~ remove        O(1)~      insertion order
TreeSet/TreeMap  -        O(log n)   O(log n)            O(log n)   yes
PriorityQueue    -        O(log n)   poll O(log n)       O(n)       only the head
ArrayDeque       -        O(1)*      both ends O(1)*     O(n)       no

*  amortised: occasionally a resize copies everything
~  expected, assuming a decent hashCode

06Collections, Arrays and the legacy classes

java.util.Collections (with an s) is a class of static helpers: sort, reverse, shuffle, max, min, frequency, nCopies, unmodifiableList, emptyList. java.util.Arrays does the same for arrays, plus Arrays.asList, which wraps an array as a fixed-size list (Topic 9.11).

Vector, Stack and Hashtable predate the framework. Every method is synchronized, which costs time even in single-threaded code and still doesn't make compound actions (check-then-add) safe. Use ArrayList, ArrayDeque and HashMap, and for threads use ConcurrentHashMap and friends (Topic 13.8).

Try it yourself

1
Swap the implementations
In the first example, change new LinkedHashSet<>() to new HashSet<>() and new TreeMap<>() to new HashMap<>(). Predict whether the printed order changes, then run. With so few keys, the order you see depends on the strings' hash codes, not on insertion. Change them back: printing a HashSet is the kind of output you should never rely on.
2
Pass a Map to countLong
In the second example, try countLong(new TreeMap<String, Integer>()). Predict the compiler's reaction. A Map isn't a Collection. Then pass map.keySet() instead and see it compile.
3
Binary search on unsorted data
In the third example, move the binarySearch line above Collections.sort. Predict the printed index, then run. The result is undefined for unsorted input: binary search's precondition is a sorted list.

Code & diagrams

List vs Set vs Map on the same data New tab

Expected output

List (order + duplicates): [tea, samosa, tea, cake, tea, samosa]
LinkedHashSet (first-seen order): [tea, samosa, cake]
TreeSet (sorted, unique): [cake, samosa, tea]
TreeMap (counts by key): {cake=1, samosa=2, tea=3}
list.get(1) = samosa
set has cake? true
tea ordered 3 times

Program to the interface: one method, many collections New tab

The TreeSet dropped the duplicate samosa, so it counts one fewer long word.

Expected output

list:  3 long words of 4
set:   2 long words of 3
queue: 3 long words of 4
after removeIf: [chai, pakora]

The Collections helper class New tab

Expected output

max: 91, min: 55
how many 91s: 2
sorted: [55, 68, 72, 91, 91]
index of 72: 2
reversed: [91, 91, 72, 68, 55]
swapped ends: [55, 91, 72, 68, 91]
nCopies: [-, -, -]
read-only view refused add

Boxed vs primitive: what a List<Integer> really holdsjava

int[] raw = new int[1_000_000];            // one block: about 4 MB
List<Integer> boxed = new ArrayList<>();   // an array of references...
for (int i = 0; i < 1_000_000; i++) {
    boxed.add(i);                          // ...each pointing at an Integer object
}
// Roughly: 4 MB of references + about 16 MB of Integer objects (values -128..127 are cached and shared).
// For big numeric data, use int[] or a primitive-collection library.

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Put a primitive type in angle brackets

Declare List<int> nums = new ArrayList<>();.

terminal

$ javac Main.java

── what you'll see ──

Main.java:5: error: unexpected type

List<int> nums = new ArrayList<>();

required: reference

found: int

1 error

Break #2

Treat a Map as a Collection

Call countLong(stock) where stock is a Map<String, Integer> and countLong takes Collection<String>.

terminal

$ javac Main.java

── what you'll see ──

Main.java:16: error: incompatible types: Map<String,Integer> cannot be converted to Collection<String>

System.out.println(countLong(stock));

Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output

1 error

Myth vs fact

Myth

Map is a kind of Collection.

Fact

It isn't. Map is a separate interface. You get collections out of it through keySet(), values() and entrySet().

Myth

Vector and Hashtable are the thread-safe versions, so use them for threads.

Fact

Their per-method locking doesn't make compound actions like "if absent, put" atomic, and it slows single-threaded code. Use ConcurrentHashMap, CopyOnWriteArrayList or explicit locking (Topic 13.8).

Myth

Declaring ArrayList<String> list is more precise, so it's better.

Fact

It ties every caller to one class. Declare with the interface (List<String>) unless you truly need a class-only method like ensureCapacity.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
RandomAccess is an empty marker interface implemented by ArrayList but not LinkedList. Algorithms in Collections (such as binarySearch and shuffle) check list instanceof RandomAccess and switch to an iterator-based strategy for linked lists, which would otherwise turn an O(log n) search into O(n log n) of get(i) calls.
▸
Most JDK collections extend skeleton classes (AbstractList, AbstractSet, AbstractMap) that build every method from a few primitives. Writing your own collection means implementing get and size for a read-only AbstractList, plus set, add and remove to make it modifiable.
▸
The Collection interface methods contains(Object) and remove(Object) take Object, not E, for compatibility with pre-generics code and because equals can legitimately match across types. So List<Long>.contains(5) compiles and returns false (the int boxes to an Integer, which never equals a Long).
▸
Java 21 inserted new interfaces into the hierarchy: SequencedCollection, SequencedSet and SequencedMap (Topic 9.12), giving every ordered collection getFirst, getLast and reversed().

Remember this

1
A collection is an object that holds a group of other objects, called its elements. Before Java 1.2, Java had only arrays and a few ad-hoc classes (Vector, Hashtable). Java 1.2 added the Collections Framework: a consistent set of interfaces in java.util, ready-made implementations, and algorithms (sorting, searching) that work on all of them. Java 5 made it generic, so List<String> holds only strings (Phase 8).
2
The framework separates what from how. An interface (List, Set, Map) says what operations exist and what they promise. An implementation (ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap) decides how the data is stored, which decides the speed. The habit every senior engineer has: declare variables and parameters with the interface (List<String> names = new ArrayList<>();) so the implementation can change in one place.
3
The family tree: Iterable is the root (anything you can loop over with for-each). Collection extends it and adds add, remove, contains, size. Under Collection sit List (ordered, indexed, duplicates allowed), Set (no duplicates) and Queue (elements waiting to be processed), and Deque extends Queue to work at both ends. **Map is not a Collection**: it stores key-value pairs, and you reach its contents through the views keySet(), values() and entrySet().
4
Every collection holds references to objects, never primitives. List<int> doesn't compile; you write List<Integer>, and autoboxing (Java 5) converts int to Integer for you. That has a cost: each Integer is a separate object on the heap (about 16 bytes) plus the 4 to 8 bytes of the reference, so a List<Integer> of a million numbers uses several times the memory of an int[].
5
Hash-based collections (HashSet, HashMap) find elements with hashCode and equals, so your element and key classes must follow the contract from Topic 4.8. Sorted collections (TreeSet, TreeMap, PriorityQueue) order elements with compareTo or a Comparator (Topic 9.10). Most collection bugs in real code are really bugs in these three methods.
6
Don't mix up Collection (the interface) with Collections (a utility class full of static helpers such as sort, reverse, max, frequency, unmodifiableList, synchronizedList and emptyList). Likewise Arrays holds helpers for arrays, including Arrays.asList. Legacy classes Vector, Stack and Hashtable still exist for compatibility, but their methods are all synchronized and new code uses ArrayList, ArrayDeque and HashMap (or the concurrent collections of Topic 13.8).

Explain it without notes

Draw the main interfaces of the Collections Framework and say where Map fits.

What is the difference between Collection and Collections?

Why should you declare variables as List<String> rather than ArrayList<String>?

Why can't collections hold primitives, and what does that cost?

Practice

Given the words {"red", "blue", "red", "green", "blue", "red"}, print the distinct words in first-seen order and the count of each word in sorted order.

Write static <T> List<T> lastN(List<T> list, int n) that returns a new list with the last n elements (or all of them if there are fewer). Print lastN(List.of(1, 2, 3, 4, 5), 2) and lastN(List.of(1), 3).

Using only Collections helpers, print the largest and smallest of List.of("kiwi", "apple", "mango") and the list sorted in reverse alphabetical order.

Trade-offs

↔
General-purpose collections are flexible and safe, but boxing makes them several times heavier than primitive arrays. For millions of numbers, an int[] (or a primitive-collection library) can be faster and far smaller.
↔
Declaring with interfaces keeps code flexible, but hides useful class-specific methods. NavigableMap and Deque are good middle grounds: specific enough to expose navigation or both-end operations, general enough to swap implementations.
↔
Sorted collections give order for free at O(log n) per operation; hash collections give O(1) lookups with no order. Choosing one is choosing which cost you pay (Topic 9.13).

Done when you can

Done when you can draw the interface tree from Iterable down, with Map on the side.
Done when you can name the main implementation of each interface and its underlying data structure.
Done when you declare variables and parameters with interfaces.
Done when you can explain why List<int> fails and what boxing costs.
Done when you know which helper lives in Collections and which in Arrays.

Command Palette

Words you'll meet

Step by step

01Four habits, four interfaces

02Program to the interface

03The operations every Collection shares

04Map is a separate tree

05The cost table you'll fill in

06Collections, Arrays and the legacy classes

Try it yourself

Swap the implementations

Pass a Map to countLong

Binary search on unsorted data

Code & diagrams

Break it on purpose

Put a primitive type in angle brackets

Treat a Map as a Collection

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can