JAVA-201 · Lesson 12 of 12 · 28 min

Capstone: choosing data structures for a real system

▶ Video coming soon A video version of this lesson is on the way.

ShopBook, Hamza's booking system from the Wednesday course, was demonstrated to Odile on Saturday, April 17, 2027. It handles bookings; it does not yet know anything about the parts room, the repair rack or which day each rental bike is free. The plan for the week after the demo is the capstone of this course: from Monday, April 19 to Thursday, April 22, Hamza designs and builds StockRoom, the data layer that ties the parts room, the repair rack and the rental calendar together, and on Friday, April 23 he walks Ingrid and Kofi through his choices. The aim is not a big program. It is to choose, for each need, the right structure, and to be able to say why.

The requirements

Hamza began, as JAVA-102 taught, by writing down what the program must do, in Kofi's, Tamsin's and Odile's words, and numbering each requirement so that every design choice and every check could point back to one.

StockRoom requirements
#RequirementAsked for by
R1Find any part by its code instantly, out of about 600Kofi
R2Print the parts list in order of code for the monthly stocktakeKofi
R3List the parts at or below their reorder level, lowest stock first, then by codeKofi
R4Hand out repair jobs by urgency, and by arrival within the same urgencyTamsin
R5Say whether a rental bike is free between two dates, and when it is next bookedOdile
R6Show the last ten stock changes and undo the most recent oneKofi
R7List the shelves in use, each once, in orderKofi
R8Never let other code change the stock room's data except through its methodsIngrid

Thinking about each requirement

For each requirement Hamza asked the questions from lesson 2's table: is it a lookup by key, a set of unique values, a sequence, a queue or a range? What operations happen most often, and how many elements are there? The answers lead to a structure, and the table of costs from the course says whether it is good enough.

R1 is a lookup by key, done many times a day, so a HashMap<String, Part> keyed by code gives O(1) average lookups. A TreeMap would also work at O(log n), about 10 comparisons for 612 parts, but nothing about R1 needs order, so the simpler and faster map wins. Part is a record with an immutable String key, so the hash contract from lesson 5 holds.

R2 needs the parts in code order, but only once a month. Hamza considered keeping a TreeMap alongside the HashMap and rejected it: two maps must be kept in step on every change, for a printout that happens twelve times a year. Sorting a copy of the 612 values on demand costs O(n log n), a few thousand comparisons, which is nothing at this size. That is a general lesson: the cheapest structure to maintain is often a sort when you need it.

R3 is a filter and a two-level order, again on demand. Counts change all day, and a PriorityQueue or TreeSet of low parts would have to be updated, with remove and add, on every change. Filtering and sorting when Kofi asks is O(n log n) and always correct. Ingrid agreed, with one note: if the shop ever had a hundred thousand parts, or wanted the list refreshed after every sale, a structure that is kept up to date would be worth its complexity.

R4 is a classic priority queue, exactly as in lesson 11: a PriorityQueue<Job> with a comparator on urgency, then arrival number. Jobs are added and taken one at a time, and the urgent one must always be next, so O(log n) offer and poll is the right shape.

R5 is about ranges of dates, which is what TreeMap's navigation methods are for. Each bike keeps a TreeMap<LocalDate, LocalDate> from each booking's start date to its end date. Bookings for one bike never overlap, so to check a range from one date to another, look at the booking that starts on or before the last date, using floorEntry: the range is free if there is none, or if that booking ends before the range begins. That is one O(log n) step.

R6 is a bounded history, newest first, with undo from the newest end: a stack that forgets its oldest entries. An ArrayDeque used as a stack with push and pop, plus removeLast whenever it grows past ten, does exactly that in O(1). R7 is a set of unique values in order, a TreeSet<String>. R8 is met by never returning a field directly, only unmodifiable views or copies.

A design diagram for StockRoom. Centre: the class StockRoom, with a HashMap from code to Part labelled R1 and an ArrayDeque of changes labelled R6, and methods printout (sort a copy, R2), toReorder (filter and sort, R3), shelvesInUse (TreeSet, R7) and read-only views (R8). Left: Part, a record with code, name, shelf, count and reorderAt. Right: RepairRack with a PriorityQueue of Jobs ordered by urgency then arrival (R4), and Rentals for one bike with a TreeMap from start date to end date (R5), using floorEntry and ceilingEntry.
StockRoom: one structure per need

The data structures chosen

The choices, their costs and what they replaced
Req.StructureKey operationsCostRejected alternative
R1HashMap<String, Part>get, putO(1) averagelist search, O(n)
R2sort a copy when askedvalues, sortO(n log n), monthlya second TreeMap kept in step
R3filter and sort when askedloop, sortO(n log n), on demanda PriorityQueue updated on every change
R4PriorityQueue<Job>offer, pollO(log n)ArrayDeque, which ignores urgency
R5TreeMap<LocalDate, LocalDate> per bikefloorEntry, ceilingEntryO(log n)a list of bookings, O(n) per check
R6ArrayDeque as a bounded stackpush, pop, removeLastO(1)java.util.Stack, ArrayList with remove(0)
R7TreeSet<String>add, iterateO(n log n) to buildHashSet, which has no order
R8unmodifiable viewsCollections.unmodifiable*O(1) to wrapreturning the fields directly

The program

Hamza's StockRoom prototype keeps the three parts of the problem in three small classes, each owning its structures privately. Part is an immutable record: a change of count makes a new Part with withCount, so there is never a stale copy in the map. The main method acts as a set of checks, one line per requirement, so the output can be read against the table above.

Java Example · Main.java
import java.time.LocalDate;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        StockRoom room = new StockRoom();
        room.addPart(new Part("TUBE-700x25", "700x25c inner tube", "B-07", 14, 10));
        room.addPart(new Part("PAD-ROAD", "brake pads, road", "B-14", 6, 8));
        room.addPart(new Part("CHAIN-11", "chain, 11-speed", "C-03", 4, 4));
        room.addPart(new Part("BELL", "bell, brass", "A-02", 9, 4));
        room.addPart(new Part("CABLE-BRAKE", "brake cable", "C-03", 2, 6));

        System.out.println("R1 lookup: " + room.find("PAD-ROAD"));
        room.use("TUBE-700x25", 5);
        room.use("BELL", 1);
        room.receive("CABLE-BRAKE", 10);
        System.out.println("R2 printout: " + room.printout());
        System.out.println("R3 reorder: " + room.toReorder());
        System.out.println("R6 recent: " + room.recentChanges());
        System.out.println("R6 undo: " + room.undo() + " -> " + room.find("CABLE-BRAKE"));
        System.out.println("R7 shelves: " + room.shelvesInUse());

        RepairRack rack = new RepairRack();
        rack.add("Mei Lin, tune-up", Urgency.ROUTINE);
        rack.add("Ana Ruiz, flat tire", Urgency.NEEDED_TOMORROW);
        rack.add("rental Cargo 1, snapped spoke", Urgency.RENTAL_DAMAGE);
        rack.add("Theo Park, brake cable", Urgency.NEEDED_TOMORROW);
        System.out.println("R4 next jobs: " + rack.next() + "; " + rack.next() + "; " + rack.next());

        Rentals cargo = new Rentals("Cargo 1");
        cargo.book(LocalDate.of(2027, 5, 1), 2, "Ana Ruiz");
        cargo.book(LocalDate.of(2027, 5, 8), 3, "Theo Park");
        System.out.println("R5 free May 3 to 7? " + cargo.isFree(LocalDate.of(2027, 5, 3), LocalDate.of(2027, 5, 7)));
        System.out.println("R5 free May 6 to 9? " + cargo.isFree(LocalDate.of(2027, 5, 6), LocalDate.of(2027, 5, 9)));
        System.out.println("R5 next after May 4: " + cargo.nextBookingAfter(LocalDate.of(2027, 5, 4)));
        try {
            room.printoutView().add(null);
        } catch (UnsupportedOperationException e) {
            System.out.println("R8 views are read-only");
        }
    }
}

record Part(String code, String name, String shelf, int count, int reorderAt) {
    Part withCount(int c) { return new Part(code, name, shelf, c, reorderAt); }
    @Override public String toString() { return code + ":" + count; }
}

class StockRoom {
    private final Map<String, Part> byCode = new HashMap<>();
    private final Deque<String[]> history = new ArrayDeque<>();
    private static final int HISTORY = 10;

    void addPart(Part p) { byCode.put(p.code(), p); }

    Part find(String code) {
        Part p = byCode.get(code);
        if (p == null) throw new NoSuchElementException("no part " + code);
        return p;
    }

    void use(String code, int n) { change(code, -n); }
    void receive(String code, int n) { change(code, n); }

    private void change(String code, int delta) {
        Part p = find(code);
        if (p.count() + delta < 0) throw new IllegalArgumentException("only " + p.count() + " of " + code);
        byCode.put(code, p.withCount(p.count() + delta));
        history.push(new String[] {code, String.valueOf(delta)});
        if (history.size() > HISTORY) history.removeLast();
    }

    String undo() {
        String[] last = history.pop();
        Part p = find(last[0]);
        byCode.put(last[0], p.withCount(p.count() - Integer.parseInt(last[1])));
        return "undid " + last[0] + " " + last[1];
    }

    List<String> recentChanges() {
        List<String> out = new ArrayList<>();
        for (String[] h : history) out.add(h[0] + " " + h[1]);
        return out;
    }

    List<Part> printout() {
        List<Part> list = new ArrayList<>(byCode.values());
        list.sort(Comparator.comparing(Part::code));
        return list;
    }

    List<Part> printoutView() { return Collections.unmodifiableList(printout()); }

    List<Part> toReorder() {
        List<Part> low = new ArrayList<>();
        for (Part p : byCode.values()) if (p.count() <= p.reorderAt()) low.add(p);
        low.sort(Comparator.comparingInt(Part::count).thenComparing(Part::code));
        return low;
    }

    SortedSet<String> shelvesInUse() {
        TreeSet<String> s = new TreeSet<>();
        for (Part p : byCode.values()) s.add(p.shelf());
        return Collections.unmodifiableSortedSet(s);
    }
}

enum Urgency { RENTAL_DAMAGE, NEEDED_TOMORROW, ROUTINE }

class RepairRack {
    private record Job(int arrival, String what, Urgency urgency) {}
    private final PriorityQueue<Job> queue = new PriorityQueue<>(
            Comparator.comparing(Job::urgency).thenComparingInt(Job::arrival));
    private int arrivals;

    void add(String what, Urgency u) { queue.offer(new Job(++arrivals, what, u)); }
    String next() { return queue.poll().what(); }
}

class Rentals {
    private final String bike;
    private final TreeMap<LocalDate, LocalDate> startToEnd = new TreeMap<>();
    private final Map<LocalDate, String> who = new HashMap<>();

    Rentals(String bike) { this.bike = bike; }

    void book(LocalDate start, int days, String customer) {
        LocalDate end = start.plusDays(days - 1);
        if (!isFree(start, end)) throw new IllegalStateException(bike + " is booked then");
        startToEnd.put(start, end);
        who.put(start, customer);
    }

    boolean isFree(LocalDate from, LocalDate to) {
        Map.Entry<LocalDate, LocalDate> before = startToEnd.floorEntry(to);
        return before == null || before.getValue().isBefore(from);
    }

    String nextBookingAfter(LocalDate d) {
        Map.Entry<LocalDate, LocalDate> e = startToEnd.ceilingEntry(d);
        return e == null ? "none" : e.getKey() + " to " + e.getValue() + ", " + who.get(e.getKey());
    }
}
Output
R1 lookup: PAD-ROAD:6
R2 printout: [BELL:8, CABLE-BRAKE:12, CHAIN-11:4, PAD-ROAD:6, TUBE-700x25:9]
R3 reorder: [CHAIN-11:4, PAD-ROAD:6, TUBE-700x25:9]
R6 recent: [CABLE-BRAKE 10, BELL -1, TUBE-700x25 -5]
R6 undo: undid CABLE-BRAKE 10 -> CABLE-BRAKE:2
R7 shelves: [A-02, B-07, B-14, C-03]
R4 next jobs: rental Cargo 1, snapped spoke; Ana Ruiz, flat tire; Theo Park, brake cable
R5 free May 3 to 7? true
R5 free May 6 to 9? false
R5 next after May 4: 2027-05-08 to 2027-05-10, Theo Park
R8 views are read-only

What this code does

The program builds the stock room, the repair rack and one bike's rental calendar, then exercises each requirement and prints one line labelled R1 to R8. Lookups go through the HashMap, the printout and reorder list are sorted copies, the rack is a PriorityQueue and the calendar answers range questions with floorEntry and ceilingEntry. The last line shows that a view handed out by the stock room refuses changes.

Reading the output against the requirements, every line is what was asked for. R1 finds PAD-ROAD with 6 in stock. R2 lists the parts by code, with the changed counts. R3 lists the three parts at or below their reorder level, lowest first: CHAIN-11 with 4, PAD-ROAD with 6 and the tubes, which have dropped to 9 against a reorder level of 10; the bells, down to 8, are still above their level of 4. R6 shows the three changes newest first, and the undo takes the brake cables back from 12 to 2. R4 hands out the damaged rental first, then Ana before Theo. R5 reports May 3 to 7 free, because Ana's rental ends on May 2, and May 6 to 9 not free, because Theo's starts on May 8.

Checking the choices with numbers

Ingrid asked Hamza to show, not just claim, that the HashMap matters at Second Gear's size. Counting comparisons for 1,000 lookups among 612 parts makes the point without timing anything.

Java Example · Main.java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 612, lookups = 1000;
        List<String> codes = new ArrayList<>();
        for (int i = 0; i < n; i++) codes.add(String.format("P-%04d", i));

        long listSteps = 0;
        long treeSteps = 0;
        int seed = 12345;
        for (int k = 0; k < lookups; k++) {
            seed = (seed * 1103515245 + 12345) & 0x7fffffff;
            int target = seed % n;
            listSteps += target + 1;
            int lo = 0, hi = n - 1;
            while (lo <= hi) {
                treeSteps++;
                int mid = (lo + hi) / 2;
                if (mid == target) break;
                if (mid < target) lo = mid + 1; else hi = mid - 1;
            }
        }
        System.out.println("comparisons for " + lookups + " lookups among " + n + " parts");
        System.out.println("  scan a list:          " + listSteps);
        System.out.println("  balanced tree search: " + treeSteps);
        System.out.println("  hash map (about 1 each): " + lookups);
    }
}
Output
comparisons for 1000 lookups among 612 parts
  scan a list:          304224
  balanced tree search: 8313
  hash map (about 1 each): 1000

What this code does

A simple fixed-seed generator picks the same 1,000 part codes to look up on every run, so the counts are repeatable. Scanning a list costs hundreds of thousands of comparisons, a balanced search tree about eight per lookup, and a hash map about one. At 612 parts the list is already hundreds of times more work than the map.

The same habit of counting answered Kofi's question about R2. Sorting 612 parts takes at most about 612 × log₂ 612, roughly 5,700 comparisons, once a month. Keeping a second sorted map in step would cost a little on every one of the thousands of stock changes in that month, and add a whole class of bugs where the two maps disagree. Doing less work all month to do slightly more work once is the better trade.

A bug found at the review

At the Friday review Kofi tried to break the rental calendar by booking Cargo 1 from May 2 for two days, overlapping Ana's rental, which ends on May 2. The booking was refused, as it should be. He then asked what happens if two bookings start on the same date. Because the TreeMap's key is the start date, a second put with the same date would replace the first booking silently. book is safe because it checks isFree first, but Ingrid pointed out that any future method that calls put directly would reintroduce the bug. Hamza added a comment and a check, and noted it for the ShopBook integration.

Java Example · Main.java
import java.time.LocalDate;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<LocalDate, String> byStart = new TreeMap<>();
        LocalDate may1 = LocalDate.of(2027, 5, 1);
        byStart.put(may1, "Ana Ruiz");
        String lost = byStart.put(may1, "Kofi, testing");
        System.out.println("put replaced: " + lost + ", map now " + byStart);

        byStart.put(may1, "Ana Ruiz");
        String existing = byStart.putIfAbsent(may1, "Kofi, testing");
        System.out.println("putIfAbsent kept: " + existing + ", map now " + byStart);
    }
}
Output
put replaced: Ana Ruiz, map now {2027-05-01=Kofi, testing}
putIfAbsent kept: Ana Ruiz, map now {2027-05-01=Ana Ruiz}

What this code does

put returns the value it replaced, so the first call shows that Ana's booking was silently overwritten by Kofi's test. putIfAbsent leaves an existing entry alone and returns it, so the second attempt keeps Ana's booking. A key that two entries could share needs this kind of check, or a different key.

Java Example · Main.java
import java.time.LocalDate;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        StockRoom room = new StockRoom();
        room.addPart(new Part("TUBE-700x25", "700x25c inner tube", "B-07", 14, 10));
        room.addPart(new Part("PAD-ROAD", "brake pads, road", "B-14", 6, 8));
        room.addPart(new Part("CHAIN-11", "chain, 11-speed", "C-03", 4, 4));
        room.addPart(new Part("BELL", "bell, brass", "A-02", 9, 4));
        room.addPart(new Part("CABLE-BRAKE", "brake cable", "C-03", 2, 6));

        System.out.println("R1 lookup: " + room.find("PAD-ROAD"));
        room.use("TUBE-700x25", 5);
        room.use("BELL", 1);
        room.receive("CABLE-BRAKE", 10);
        System.out.println("R2 printout: " + room.printout());
        System.out.println("R3 reorder: " + room.toReorder());
        System.out.println("R6 recent: " + room.recentChanges());
        System.out.println("R6 undo: " + room.undo() + " -> " + room.find("CABLE-BRAKE"));
        System.out.println("R7 shelves: " + room.shelvesInUse());

        RepairRack rack = new RepairRack();
        rack.add("Mei Lin, tune-up", Urgency.ROUTINE);
        rack.add("Ana Ruiz, flat tire", Urgency.NEEDED_TOMORROW);
        rack.add("rental Cargo 1, snapped spoke", Urgency.RENTAL_DAMAGE);
        rack.add("Theo Park, brake cable", Urgency.NEEDED_TOMORROW);
        System.out.println("R4 next jobs: " + rack.next() + "; " + rack.next() + "; " + rack.next());

        Rentals cargo = new Rentals("Cargo 1");
        cargo.book(LocalDate.of(2027, 5, 1), 2, "Ana Ruiz");
        cargo.book(LocalDate.of(2027, 5, 8), 3, "Theo Park");
        System.out.println("R5 free May 3 to 7? " + cargo.isFree(LocalDate.of(2027, 5, 3), LocalDate.of(2027, 5, 7)));
        System.out.println("R5 free May 6 to 9? " + cargo.isFree(LocalDate.of(2027, 5, 6), LocalDate.of(2027, 5, 9)));
        System.out.println("R5 next after May 4: " + cargo.nextBookingAfter(LocalDate.of(2027, 5, 4)));
        cargo.book(LocalDate.of(2027, 5, 2), 2, "Kofi, testing");
        try {
            room.printoutView().add(null);
        } catch (UnsupportedOperationException e) {
            System.out.println("R8 views are read-only");
        }
    }
}

record Part(String code, String name, String shelf, int count, int reorderAt) {
    Part withCount(int c) { return new Part(code, name, shelf, c, reorderAt); }
    @Override public String toString() { return code + ":" + count; }
}

class StockRoom {
    private final Map<String, Part> byCode = new HashMap<>();
    private final Deque<String[]> history = new ArrayDeque<>();
    private static final int HISTORY = 10;

    void addPart(Part p) { byCode.put(p.code(), p); }

    Part find(String code) {
        Part p = byCode.get(code);
        if (p == null) throw new NoSuchElementException("no part " + code);
        return p;
    }

    void use(String code, int n) { change(code, -n); }
    void receive(String code, int n) { change(code, n); }

    private void change(String code, int delta) {
        Part p = find(code);
        if (p.count() + delta < 0) throw new IllegalArgumentException("only " + p.count() + " of " + code);
        byCode.put(code, p.withCount(p.count() + delta));
        history.push(new String[] {code, String.valueOf(delta)});
        if (history.size() > HISTORY) history.removeLast();
    }

    String undo() {
        String[] last = history.pop();
        Part p = find(last[0]);
        byCode.put(last[0], p.withCount(p.count() - Integer.parseInt(last[1])));
        return "undid " + last[0] + " " + last[1];
    }

    List<String> recentChanges() {
        List<String> out = new ArrayList<>();
        for (String[] h : history) out.add(h[0] + " " + h[1]);
        return out;
    }

    List<Part> printout() {
        List<Part> list = new ArrayList<>(byCode.values());
        list.sort(Comparator.comparing(Part::code));
        return list;
    }

    List<Part> printoutView() { return Collections.unmodifiableList(printout()); }

    List<Part> toReorder() {
        List<Part> low = new ArrayList<>();
        for (Part p : byCode.values()) if (p.count() <= p.reorderAt()) low.add(p);
        low.sort(Comparator.comparingInt(Part::count).thenComparing(Part::code));
        return low;
    }

    SortedSet<String> shelvesInUse() {
        TreeSet<String> s = new TreeSet<>();
        for (Part p : byCode.values()) s.add(p.shelf());
        return Collections.unmodifiableSortedSet(s);
    }
}

enum Urgency { RENTAL_DAMAGE, NEEDED_TOMORROW, ROUTINE }

class RepairRack {
    private record Job(int arrival, String what, Urgency urgency) {}
    private final PriorityQueue<Job> queue = new PriorityQueue<>(
            Comparator.comparing(Job::urgency).thenComparingInt(Job::arrival));
    private int arrivals;

    void add(String what, Urgency u) { queue.offer(new Job(++arrivals, what, u)); }
    String next() { return queue.poll().what(); }
}

class Rentals {
    private final String bike;
    private final TreeMap<LocalDate, LocalDate> startToEnd = new TreeMap<>();
    private final Map<LocalDate, String> who = new HashMap<>();

    Rentals(String bike) { this.bike = bike; }

    void book(LocalDate start, int days, String customer) {
        LocalDate end = start.plusDays(days - 1);
        if (!isFree(start, end)) throw new IllegalStateException(bike + " is booked then");
        startToEnd.put(start, end);
        who.put(start, customer);
    }

    boolean isFree(LocalDate from, LocalDate to) {
        Map.Entry<LocalDate, LocalDate> before = startToEnd.floorEntry(to);
        return before == null || before.getValue().isBefore(from);
    }

    String nextBookingAfter(LocalDate d) {
        Map.Entry<LocalDate, LocalDate> e = startToEnd.ceilingEntry(d);
        return e == null ? "none" : e.getKey() + " to " + e.getValue() + ", " + who.get(e.getKey());
    }
}

What this code does

Kofi's test booking for May 2 overlaps the end of Ana's rental, so isFree finds her booking with floorEntry and book refuses it with IllegalStateException. The run prints every requirement line up to R5 and then stops at the refused booking. That is the right behaviour, and the test belongs in the program's checks.

Running it
$ javac Main.java
$ java Main
R1 lookup: PAD-ROAD:6
R2 printout: [BELL:8, CABLE-BRAKE:12, CHAIN-11:4, PAD-ROAD:6, TUBE-700x25:9]
R3 reorder: [CHAIN-11:4, PAD-ROAD:6, TUBE-700x25:9]
R6 recent: [CABLE-BRAKE 10, BELL -1, TUBE-700x25 -5]
R6 undo: undid CABLE-BRAKE 10 -> CABLE-BRAKE:2
R7 shelves: [A-02, B-07, B-14, C-03]
R4 next jobs: rental Cargo 1, snapped spoke; Ana Ruiz, flat tire; Theo Park, brake cable
R5 free May 3 to 7? true
R5 free May 6 to 9? false
R5 next after May 4: 2027-05-08 to 2027-05-10, Theo Park
Exception in thread "main" java.lang.IllegalStateException: Cargo 1 is booked then
	at Rentals.book(Main.java:130)
	at Main.main(Main.java:36)

What the course added up to

Every structure in StockRoom came from a lesson in this course: generics from lesson 1 make the containers type-safe; the framework's interfaces from lesson 2 let fields be declared as Map and Deque; ArrayList, ArrayDeque, HashMap and TreeMap each won because of the costs measured in lessons 3 to 6; the comparators from lesson 7 order the reorder list and the repair rack; iterators from lesson 8 walk the history safely; and lessons 9 to 11 explain what is happening inside each of them. The skill that ties them together is the one this capstone practised: state the need, count the operations, choose the simplest structure whose costs fit, and check the result against the requirements.

A checklist for choosing a data structure
Question to askIf the answer is yesStructure
Do I look things up by a key?and order does not matterHashMap
and I need sorted keys or rangesTreeMap
Must each value appear once?and order does not matterHashSet
and I need them sortedTreeSet
Do I always want the smallest or most urgent next?PriorityQueue
Do I add and remove only at the ends?ArrayDeque, as a queue or stack
Otherwise, a sequence?ArrayList
Is the need rare, such as a monthly report?compute it on demand, for example by sorting a copy

Try it yourself

A bounded change history

Complete record so the history keeps only the newest three entries: push the new entry onto the ArrayDeque, and if it then holds more than max entries, remove the oldest with removeLast.

The program should print [chain -1, pads -2, tube +10].

import java.util.*;

public class Main {
    public static void main(String[] args) {
        History h = new History(3);
        for (String change : new String[] {"bell -1", "cable +6", "tube +10", "pads -2", "chain -1"}) h.record(change);
        System.out.println(h.newestFirst());
    }
}

class History {
    private final Deque<String> entries = new ArrayDeque<>();
    private final int max;

    History(int max) { this.max = max; }

    void record(String change) {
        entries.push(change);
    }

    List<String> newestFirst() { return new ArrayList<>(entries); }
}

Try it yourself

Is the bike free?

Complete isFree for a bike whose bookings never overlap. Find the booking that starts on or before to with floorEntry(to); the range is free if there is none, or if that booking's end date is before from.

The program should print May 3-7 free: true, May 6-9 free: false and April 28-30 free: true.

import java.time.LocalDate;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        TreeMap<LocalDate, LocalDate> bookings = new TreeMap<>();
        bookings.put(LocalDate.of(2027, 5, 1), LocalDate.of(2027, 5, 2));
        bookings.put(LocalDate.of(2027, 5, 8), LocalDate.of(2027, 5, 10));
        System.out.println("May 3-7 free: " + isFree(bookings, LocalDate.of(2027, 5, 3), LocalDate.of(2027, 5, 7)));
        System.out.println("May 6-9 free: " + isFree(bookings, LocalDate.of(2027, 5, 6), LocalDate.of(2027, 5, 9)));
        System.out.println("April 28-30 free: " + isFree(bookings, LocalDate.of(2027, 4, 28), LocalDate.of(2027, 4, 30)));
    }

    static boolean isFree(TreeMap<LocalDate, LocalDate> bookings, LocalDate from, LocalDate to) {
        return !bookings.containsKey(from);
    }
}

Common mistakes

  • MistakeChoosing a structure before writing down what the program must do.

    InsteadList the requirements first, then choose a structure for each one.

  • MistakeKeeping two structures in step for a report that is rarely needed.

    InsteadCompute rare results on demand, for example by sorting a copy.

  • MistakeUsing a key that two entries can share, such as a start date, and calling put directly.

    InsteadCheck for an existing key first, or choose a key that is unique.

  • MistakeReturning a private collection from a getter.

    InsteadReturn an unmodifiable view or a copy.

  • MistakeClaiming a structure is faster without evidence.

    InsteadCount the operations for realistic sizes, as the lookup comparison did.

Summary and key terms

  • A good data layer starts from numbered requirements and chooses one structure per need by asking whether it is a lookup by key, a set, a sequence, a queue or a range, how often each operation happens and how many elements there are.
  • StockRoom uses a HashMap for lookup by code, an on-demand sort for the monthly printout and the reorder list, a PriorityQueue for the repair rack, a TreeMap from start to end date for each rental bike, an ArrayDeque as a bounded undo stack, a TreeSet for shelves and unmodifiable views to protect its data.
  • Rare needs are often best met by computing them when asked, rather than by keeping an extra structure in step.
  • Counting comparisons shows the difference between a list scan, a tree search and a hash lookup at real sizes.
  • Reviews and deliberate attempts to break the design, such as overlapping bookings, find the bugs the requirements did not mention.
Requirement
A numbered statement of something the program must do.
Data layer
The part of a program that holds and organizes its data.
On-demand computation
Producing a result when it is asked for instead of keeping it up to date all the time.
Bounded history
A record that keeps only the newest entries, up to a fixed number.
Design review
A meeting in which others question a design to find weaknesses.
Trade-off
Accepting a cost in one place for a benefit in another.
Invariant check
Code that confirms a rule still holds, such as bookings not overlapping.
Unmodifiable view
A read-only wrapper that lets callers see a collection without changing it.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. Why did Hamza use a HashMap rather than a TreeMap for R1?

    Show answer

    Lookups by code need no order, and a HashMap gives O(1) average lookups.

  2. Why is the monthly printout sorted on demand instead of kept in a second sorted map?

    Show answer

    Sorting once a month is cheap, while keeping two maps in step costs work on every change and risks bugs.

  3. How does Rentals.isFree check a date range in O(log n)?

    Show answer

    It finds the booking that starts on or before the end date with floorEntry and checks whether it ends before the start date.

  4. What structure suits a history that keeps only the last ten changes, newest first?

    Show answer

    An ArrayDeque used as a stack, with removeLast when it grows past ten.

  5. What bug did the review find in the rental calendar?

    Show answer

    Two bookings with the same start date would replace each other in the TreeMap if put were called without checking.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz