LLD Dojo

Java, from nothing · chapter 7 of 33

The three collections you need: List, Map, Set

Chapter 1.7 · Part 1, Java from nothing · about 35 minutes

What you need before this chapter: chapters 1.1 through 1.6. You should be comfortable with classes, objects, fields, methods, constructors, private, references versus values, == versus equals, and null. You should also know how inheritance and polymorphism work, and how interfaces and abstract classes differ.

When you finish this chapter you will be able to:

1. The idea in plain words

A parking lot issues tickets all day. Every ticket needs to sit somewhere while the program runs: a place to add new ones, look old ones up, and go through all of them at closing time. An array can hold a fixed number of tickets, but you rarely know in advance how many cars will show up, and an array cannot grow once you have created it. That gap is what the three types in this chapter fill.

A List is an ordered, growable sequence. It remembers the order you added things in, and it allows duplicates: two identical tickets are two entries, not one. Reach for a List when the answer to "which one" is a position, and when the same value might legitimately appear more than once.

A Map stores a value under a key, so you can retrieve it later without scanning through everything. A parking lot that needs to answer "which spot is plate KA-01-4432 in?" instantly, no matter how many cars are parked, needs a Map from plate to spot number. Reach for a Map whenever you find yourself about to loop through a list just to find one thing by name.

A Set stores values with no duplicates and, usually, no promise about order. A parking lot that wants to know how many distinct plates have been on site today needs a Set. Add every plate as cars arrive, and the size of the set is the answer, duplicates already removed for you.

All three are interfaces, in the same sense chapter 1.5 covered. List, Map, and Set say what a type can do, and you almost always work through the interface type while creating a concrete implementation on the right-hand side. The two implementations you will use for nearly everything in this course are ArrayList for List and HashMap for Map.

Know one fact about both from the first time you touch them: neither ArrayList nor HashMap is safe to use from more than one thread at once. Two threads adding to the same ArrayList at the same time can corrupt its internal state, or silently lose one of the additions. Part 4 of this course deals with what to do about that. For now, in single-threaded code, both are exactly what you want: fast, simple, and the default choice unless something tells you otherwise.

2. Type this

Make a new file, ParkingLot.java, in the folder you have been working in. You will also need the Ticket class from earlier chapters; if you no longer have it, this version is enough to run the example:

INLINECODE0

Now type ParkingLot.java:

INLINECODE1

3. Run it

INLINECODE2

Output:

INLINECODE3

4. What just happened, line by line

List<Ticket> issued = new ArrayList<>(); declares a variable of the interface type List, holding a value that is actually an ArrayList. The <Ticket> says this particular list holds Ticket objects and nothing else; chapter 1.8 explains exactly what that angle-bracket syntax is doing. The empty <> on the right is the compiler filling in <Ticket> again from context, so you do not have to type it twice.

issued.add(...) appends to the end. Notice the same plate, KA-01-4432, appears in the list twice, at index 0 and index 2. A List does not care. It stores what you tell it to store, in the order you gave it, duplicates included.

for (Ticket t : issued) is the for-each loop. Read it as "for each Ticket in issued, calling it t inside the loop body". It visits every element in order and does not expose an index, which is exactly what you want when you only need to look at each element once, not calculate a position.

Map<String, Integer> spotOf = new HashMap<>(); declares a map from String keys to Integer values. spotOf.put("KA-01-4432", 12) stores the pair; spotOf.get("MH-12-9001") retrieves the value stored under that exact key. The name spotOf is doing real work here: reading it as "the spot of" whatever plate you pass in makes the code closer to a sentence, and that habit is worth keeping.

spotOf.get("DL-3C-0001") asks for a key that was never put in. A Map does not throw an exception for a missing key. It returns null, and the program printed `unknown plate looks up as: null` to prove it. That single fact causes one of the two errors in the next section, so hold on to it.

Set<String> platesOnSite = new HashSet<>(); and three calls to .add, two of them with the same plate. HashSet.add silently does nothing the second time it sees a value already present, and .size() came back 2, not 3. A Set is asking one question about every element you give it: "do I already have this?"; and a List never asks that question at all.

5. Errors you are likely to hit

Asking a List for an index it does not have. Change the loop to System.out.println(issued.get(5)); on a list of three elements:

INLINECODE4

List indices run from 0 to size() - 1. Ask for anything outside that range and Java stops the program rather than guessing.

Calling a method on a value a Map never gave you. This is the trap section 4 set up. Write

INLINECODE5

and Java has to unbox the Integer that get returned into a primitive int. Since get returned null, there is nothing to unbox:

INLINECODE6

Every Map.get call on a key you have not checked for is a null waiting to reach exactly this line. Chapter 1.9 gives you the tool for handling this properly; for now, check spotOf.containsKey(plate) before you trust the result, or compare the result to null before using it.

Removing from a List while a for-each loop is reading it. This one deserves its own section, because it is not a typo, it is a real design decision in the JVM.

INLINECODE7

Running this crashes:

INLINECODE8

A for-each loop over a List is really an object called an iterator, walking the list one step at a time. That iterator keeps a count of how many changes the list has gone through. When you call issued.remove(t) directly, the list's change count moves but the iterator's copy of it does not. The next time the iterator takes a step, it notices the mismatch and refuses to continue, because it can no longer promise it is visiting every element exactly once. This is not a bug you can work around by being careful. It is the collection protecting you from a wrong answer that would otherwise pass silently, such as skipping the element right after the one you removed.

The fix is to let the iterator do the removing. Fetch it explicitly and call its own .remove() method, which updates both counts together:

INLINECODE9

This compiles and runs cleanly, and it is the pattern to reach for any time a loop needs to remove elements as it goes.

6. Your turn

Write a program that keeps a List<Ticket> of three tickets: "KA-01-4432" at minute 555, "MH-12-9001" at minute 600, and "TN-22-7788" at minute 630. Using the iterator pattern from section 5, remove every ticket that arrived before minute 600, then print how many tickets remain and their plates.

Do it before reading on.

The answer:

INLINECODE10

Running it prints:

INLINECODE11

If you got those three lines, you have understood iteration, removal, and why the two do not mix without an iterator's own .remove().

Going deeper

HashMap and HashSet both depend on two methods you already know how to write by hand from chapter 1.3: equals and hashCode. Here is what a HashMap actually does with them, and why skipping hashCode breaks lookups in a way that equals alone cannot fix.

Internally, a HashMap is an array of buckets. When you call put(key, value), Java calls key.hashCode() and uses that number to pick a bucket, then stores the pair there. A get(key) call computes hashCode() on the key you passed in and jumps straight to that same bucket. Only then does it use equals to check the entries in that bucket for an exact match.

If a class overrides equals but not hashCode, two objects that are "equal" by your own definition can still land in different buckets. The default hashCode, inherited from Object, is based on memory identity and has no idea your equals says otherwise. The lookup fails silently: get returns null for a key that is sitting in the map right now, just in the wrong bucket. That is why equals and hashCode are a pair, never one without the other.

More than one key can still land in the same bucket, which is called a collision, and a bucket can hold more than one entry. Up through Java 7 a bucket was a linked list, so heavy collisions degraded to a linear scan. Java 8 changed this. Once a single bucket's chain grows past 8 entries, the JDK converts that bucket from a linked list into a small red-black tree, turning a worst-case linear scan into a logarithmic one. This is a checkable number: TREEIFY_THRESHOLD is defined as 8 in java.util.HashMap's own source, there specifically so a bad hashCode() degrades gracefully instead of turning a HashMap into a bottleneck.

ArrayList has a matching fact worth knowing on the memory side. It is backed by a plain array, and new ArrayList<>() with no argument starts that array at capacity 10. Every time you add past the array's current capacity, ArrayList allocates a new, larger array at 1.5 times the old capacity, and copies every existing element into it. Measured directly against the JDK 21 ArrayList used for this course: capacity starts at 10, grows to 15 at the eleventh element, then to 22 at the sixteenth. Each growth step costs a full copy of everything added so far.

If you already know roughly how many elements a list will hold, new ArrayList<>(expectedSize) allocates the backing array at that size once. Every add afterward is then a plain array write with no copying. On a list holding a few dozen tickets this is invisible. On a list built from a loop over a large corpus, skipping the resizes is a measurable difference, not a superstition.

7. Why this matters in an interview

List, Map, and Set are the vocabulary every design round is conducted in. When an interviewer asks how you would look up a parking spot by plate number, "a Map from plate to spot" is the entire answer to that part of the question. Saying it fast signals you are not translating from some other language in your head.

The thread-safety point from section 1 is not decoration. A machine-coding round in Part 4 of this course will hand you two threads sharing a parking lot. Say the honest sentence first: "ArrayList and HashMap are not thread-safe, so this needs a lock or a concurrent collection." Do not let this be something you discover later by watching data get corrupted.

And ConcurrentModificationException from section 5 is not a curiosity. A candidate who has only ever added to a list, never removed from one mid-loop, hits this crash live in an interview, looks confused, and burns two minutes on it. You now know it on sight, and you know the fix.

Next: chapter 1.8, Generics, as far as you actually need them. The angle brackets you just typed without a second thought, List<Ticket>, get explained properly there, starting from the mess they exist to prevent.

← 1.6 Abstract classes, and when an interface is better · All chapters · 1.8 Generics, as far as you actually need them →