Choosing a collection

You are going on a trip. For a weekend away you take a rucksack. For a month abroad you take a suitcase. For the train to college you take a small bag for your laptop and lunch. Nobody wonders which one is "the best bag". The question is always "the best bag for this trip".

Collections work the same way. After ten lessons you have met a whole set of them, and none is the best. ArrayList is perfect for a shopping list and wrong for a phone book. HashMap is perfect for a phone book and wrong for an undo button. Choosing well is mostly a matter of asking what the trip is.

Good news: you only need three questions. This lesson turns them into a guide you can keep open next to your editor. It is the lesson most students come back to.

Remember: don't ask "which collection is best?" Ask "what do I need to do with these items?"

Read the picture from the top.

1. Do you look things up by a key? A key is a name or ID that points to a value, like a name in a phone book. If yes, you need a Map. Then ask about order: no order needed means HashMap, the order you added means LinkedHashMap, and sorted keys means TreeMap.
2. If not: should each item appear only once? If yes, you need a Set, and the same order question picks HashSet, LinkedHashSet or TreeSet.
3. If not: how is the list used? To read by position, such as "the third item", use ArrayList. To work at the ends, as a stack (newest first) or a queue (oldest first), use ArrayDeque. To always take the most urgent item next, use PriorityQueue.

And one more rule that holds throughout: declare the variable as the interface (List, Set, Map, Deque, Queue) and only write the class name after new. Then changing your mind later means changing one word.

Every block below can be pasted into jshell. Each one names the need first and then the pick.

Trip 1: a shopping list. Order matters, repeats are fine, and you read by position.

// Order matters, repeats are fine, and you read by position: an ArrayList.
List<String> bag = new ArrayList<>();
bag.add("milk");
bag.add("eggs");
bag.add("milk"); // two packets of milk
System.out.println(bag);
System.out.println(bag.get(1));

[milk, eggs, milk]
eggs

Trip 2: who has visited? You only want to know "have I seen this one?", and each person counts once.

// "Have I seen this before?" and "no repeats": a HashSet.
Set<String> visitors = new HashSet<>();
String[] arrivals = {"asha", "ravi", "asha", "meera", "ravi", "asha"};
for (String id : arrivals) {
    visitors.add(id);
}
System.out.println(visitors.size());
System.out.println(visitors.contains("meera"));

3
true

Six arrivals, three different people. A set absorbs the repeats on its own.

Trip 3: no repeats, but keep the order they first came in.

// No repeats, and the first-seen order kept: a LinkedHashSet.
List<String> raw = List.of("b", "a", "b", "c", "a");
Set<String> unique = new LinkedHashSet<>(raw);
System.out.println(unique);

[b, a, c]

A LinkedHashSet is a HashSet that remembers insertion order. Copying a list into one is a neat way to remove repeats without scrambling the list.

Trip 4: a phone book. You look up by name, and now and then list everyone A to Z.

// Look up by name: a HashMap. List them A to Z: copy into a TreeMap.
Map<String, String> contacts = new HashMap<>();
contacts.put("Ravi", "98450 22222");
contacts.put("Asha", "98450 11111");
contacts.put("Meera", "98450 33333");
System.out.println(contacts.get("Meera"));
System.out.println(new TreeMap<>(contacts));

98450 33333
{Asha=98450 11111, Meera=98450 33333, Ravi=98450 22222}

A HashMap for the quick lookups. When you need the sorted list, copy it into a TreeMap just for that moment.

Trip 5: undo. The newest change is the first to be undone.

// The newest edit is undone first: a stack, so an ArrayDeque.
Deque<String> edits = new ArrayDeque<>();
edits.push("typed 'Hel'");
edits.push("typed 'lo'");
edits.push("deleted 'o'");
System.out.println(edits.pop());
System.out.println(edits.pop());

deleted 'o'
typed 'lo'

Trip 6: a print line. The oldest job goes first.

// The oldest job is served first: a queue, so an ArrayDeque again.
Queue<String> jobs = new ArrayDeque<>();
jobs.offer("report.pdf");
jobs.offer("photo.png");
System.out.println(jobs.poll());
System.out.println(jobs.size());

report.pdf
1

Both of those are ArrayDeque: one used as a stack, one as a queue.

Trip 7: the next train. Whatever order the times are added in, you always want the earliest.

// Always the earliest departure first, whatever order they arrive in:
// a PriorityQueue.
PriorityQueue<Integer> departures = new PriorityQueue<>();
departures.offer(1545);
departures.offer(915);
departures.offer(1210);
System.out.println(departures.poll());
System.out.println(departures.poll());

915
1210

Changing your mind later

Because the variable is declared as Map, the code that uses it does not care which map it got.

// Written against Map, so any map will do.
static int total(Map<String, Integer> marks) {
    int sum = 0;
    for (int value : marks.values()) {
        sum += value;
    }
    return sum;
}

Map<String, Integer> marks = new HashMap<>(); // change this one word to TreeMap...
marks.put("Asha", 91);
marks.put("Ravi", 72);
marks.put("Meera", 65);
System.out.println(total(marks)); // ...and nothing below needs to change

228

Change HashMap to TreeMap on the first line and the total is the same. This is the habit from lesson 1 paying off. Pick the class you need today, and keep the door open.

The guide as code

If it helps to see the guide as a program, here it is. Each branch is one arrow in the picture.

enum Need { LOOK_UP_BY_KEY, UNIQUE_ITEMS, BY_POSITION, STACK_OR_QUEUE, MOST_URGENT_FIRST }

enum Order { ANY, AS_ADDED, SORTED }

/** The decision guide, written as code. */
static String suggest(Need need, Order order) {
    return switch (need) {
        case LOOK_UP_BY_KEY -> switch (order) {
            case ANY -> "HashMap";
            case AS_ADDED -> "LinkedHashMap";
            case SORTED -> "TreeMap";
        };
        case UNIQUE_ITEMS -> switch (order) {
            case ANY -> "HashSet";
            case AS_ADDED -> "LinkedHashSet";
            case SORTED -> "TreeSet";
        };
        case BY_POSITION -> "ArrayList"; // LinkedList is almost never the better answer
        case STACK_OR_QUEUE -> "ArrayDeque";
        case MOST_URGENT_FIRST -> "PriorityQueue";
    };
}

System.out.println(suggest(Need.LOOK_UP_BY_KEY, Order.ANY));
System.out.println(suggest(Need.LOOK_UP_BY_KEY, Order.SORTED));
System.out.println(suggest(Need.UNIQUE_ITEMS, Order.AS_ADDED));
System.out.println(suggest(Need.STACK_OR_QUEUE, Order.ANY));
System.out.println(suggest(Need.MOST_URGENT_FIRST, Order.ANY));

HashMap
TreeMap
LinkedHashSet
ArrayDeque
PriorityQueue

The table below says the same thing in words. This is the one to screenshot.

Notice who is missing: LinkedList. It is not in the table because there is almost always a better row. Lesson 4 explains why.

Remember: three questions. A key to look things up by? Each item only once? Otherwise, how is the list used?

You do not need to memorise costs. If you remember what each class is built from, the costs follow.

Three questions in the guide match three structures: an array when position matters, buckets when a key matters, and a tree or heap when order or urgency matters. Almost every collection in Java is one of those with a different coat on.

First, what each one keeps. The word null here means "no object", and some collections refuse it.

Now what the main operations cost, for n items.

Two habits fall out of the table. If you call contains in a loop on a list, you have n times n work, and a HashSet fixes it. If you keep sorting a list again and again, a TreeSet or a PriorityQueue may be the tool you wanted.

static int firstUnique(String text) {
    throw new UnsupportedOperationException("index of the first letter that appears only once, or -1");
}

static int firstUnique(String text) {
    // Counting needs a lookup by letter: a HashMap.
    Map<Character, Integer> counts = new HashMap<>();
    for (char c : text.toCharArray()) {
        counts.merge(c, 1, Integer::sum);
    }
    // The text itself keeps the order, so scan it again.
    for (int i = 0; i < text.length(); i++) {
        if (counts.get(text.charAt(i)) == 1) {
            return i;
        }
    }
    return -1;
}

static class Editor {
    void type(String more) {
        throw new UnsupportedOperationException("add more to the end of the text");
    }

    boolean undo() {
        throw new UnsupportedOperationException("go back one step; false if there is nothing to undo");
    }

    String text() {
        throw new UnsupportedOperationException("the text so far");
    }
}

static class Editor {
    // Undo takes back the newest change first: a stack.
    private final Deque<String> history = new ArrayDeque<>();
    private String text = "";

    void type(String more) {
        history.push(text); // remember the text as it was before this change
        text = text + more;
    }

    boolean undo() {
        if (history.isEmpty()) {
            return false;
        }
        text = history.pop();
        return true;
    }

    String text() {
        return text;
    }
}

static List<String> topWords(String[] words, int k) {
    throw new UnsupportedOperationException("the k most common words; ties go A to Z");
}

static List<String> topWords(String[] words, int k) {
    Map<String, Integer> counts = new HashMap<>();
    for (String word : words) {
        counts.merge(word, 1, Integer::sum);
    }
    // A map has no order, so move the entries into a list that we can sort.
    List<Map.Entry<String, Integer>> entries = new ArrayList<>(counts.entrySet());
    entries.sort((a, b) -> {
        int byCount = Integer.compare(b.getValue(), a.getValue()); // bigger count first
        return byCount != 0 ? byCount : a.getKey().compareTo(b.getKey()); // then A to Z
    });
    List<String> top = new ArrayList<>();
    for (int i = 0; i < Math.min(k, entries.size()); i++) {
        top.add(entries.get(i).getKey());
    }
    return top;
}

"Which collection would you use?" is asked in nearly every Java interview, sometimes in disguise. The answer is never just a name. It is a name plus a reason.

• Say the need first. "I need to look up by ID, and order doesn't matter, so a HashMap." One sentence with the need and the pick beats a list of facts.
• "ArrayList or LinkedList?" ArrayList, nearly always. Say why: reading by index is O(1), the items sit together in memory, and LinkedList needs a node per item.
• "How do you remove duplicates from a list?" Copy it into a HashSet, or a LinkedHashSet if the order must stay. Say the cost: O(n).
• "Stack or queue in Java?" ArrayDeque for both, not Stack and not LinkedList.
• "HashMap, LinkedHashMap or TreeMap?" Unordered and fastest, insertion order, sorted. One sentence for each.
• "How would you keep the 10 largest of a million numbers?" A PriorityQueue of size 10, as in lesson 9.
• "Why List<String> x = new ArrayList<>()?" Programming to the interface. The rest of the code depends only on List, so you can change the class in one place.
• "What if the choice is wrong?" It rarely matters until the data is large. If a profile shows a hot contains on a list, switch to a set. Start simple, and measure before you tune.
• Say the cost. "Index or key lookup: O(1) for arrays and hashes, O(log n) for trees. The word that matters is what I need to do most."

Made by VeraStack Labs