Collections: which one to pick

A collection is a container that holds a group of objects, so your code can store, find, sort or process them together. Java's Collections Framework gives you interfaces (what a container can do) and implementations (how it does it).

Do not ask “which collection is best?” Ask “what must this group keep, or do quickly?”

The map

Most collection types sit under these interfaces. Map is part of the same framework, but it is not a Collection, because it stores key-value pairs.

                      Iterable
                          |
                      Collection                          Map
          +---------------+---------------+                |
          |               |               |    +--------+--+------------+-------+
        List             Set            Queue  |        |               |       |
          |               |               |    HashMap  LinkedHashMap   TreeMap ConcurrentHashMap
   ArrayList         HashSet        ArrayDeque
   LinkedList     LinkedHashSet    PriorityQueue
                    TreeSet

A Map holds pairs, not single elements.

Pick one in ten seconds

If you are unsure, pick ArrayList for a list and HashMap for a map. Change only when you have a reason.

Time complexity

Time complexity says how the work grows with the data. O(1) means the cost stays the same. O(n) means it grows with the item count. O(log n) grows slowly.

* O(1) on average. When the internal array is full it doubles, which is O(n) for that one add. ** O(1) for the link itself, but O(n) to walk to that position first.

n/a: a hash or sort order picks the position.

The row that matters most is contains. To search an ArrayList of 10,000 items, Java may check all 10,000. A HashSet checks about one. If you write list.contains(x) inside a loop, you probably want a set or a map.

List

List<String> names = new ArrayList<>();
names.add("Rizon");
names.add("Aisha");
names.get(0);              // Rizon
names.contains("Aisha");   // true, but O(n)
names.remove("Aisha");

ArrayList is a resizable array. Reading by position is fast. Inserting in the middle is slow, because every later item shifts over.

LinkedList is a chain of nodes, where each node points to the next. It only pays off when you add and remove at both ends a lot, and even then ArrayDeque is usually faster. In practice, use ArrayList.

Removing while looping

Removing from a list inside a for each loop throws ConcurrentModificationException, because the loop notices the list changed under it:

for (String name : names) {
    if (name.startsWith("A")) {
        names.remove(name);      // breaks
    }
}

Two correct ways:

names.removeIf(name -> name.startsWith("A"));      // simplest

Iterator<String> it = names.iterator();            // when you need more control
while (it.hasNext()) {
    if (it.next().startsWith("A")) {
        it.remove();
    }
}

Set

A set holds no duplicates. Java decides what counts as a duplicate by calling equals and hashCode. So a set of your own objects only works if you wrote those two methods. See 15-EqualsAndHashCode.md.

Set<String> plates = new HashSet<>();
plates.add("KA01AB1234");
plates.add("KA01AB1234");     // ignored, already there
plates.size();                // 1
plates.contains("KA01AB1234"); // true, O(1)

TreeSet must know how to sort. Either the elements implement Comparable, or you pass a Comparator to the constructor.

Map

Map<String, ParkingSpot> spots = new HashMap<>();
spots.put("KA01AB1234", spotA);
spots.get("KA01AB1234");                // spotA
spots.get("UNKNOWN");                   // null
spots.getOrDefault("UNKNOWN", empty);   // no null to handle
spots.containsKey("KA01AB1234");        // true
spots.remove("KA01AB1234");

for (Map.Entry<String, ParkingSpot> entry : spots.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

Methods that remove boilerplate

// old
List<Screening> list = byMovie.get(movie);
if (list == null) {
    list = new ArrayList<>();
    byMovie.put(movie, list);
}
list.add(screening);

// new
byMovie.computeIfAbsent(movie, k -> new ArrayList<>()).add(screening);

counts.merge(word, 1, Integer::sum);      // count occurrences in one line
map.putIfAbsent(key, value);              // only if not already there
map.getOrDefault(key, fallback);          // avoid the null check

computeIfAbsent is the one to remember. It means: if the key has no value yet, create one, store it and return it. Use it any time you have a map of lists.

TreeMap for ranges

TreeMap keeps its keys sorted, so it can answer "give me everything from this key upward".

TreeMap<Integer, Set<Table>> tablesByCapacity = new TreeMap<>();

// every table that seats at least partySize
for (Set<Table> tables : tablesByCapacity.tailMap(partySize).values()) {
    // ...
}

Layout.java in the restaurant system does exactly this. A HashMap would have to check every key.

Other useful ones: headMap, subMap, firstKey, lastKey, floorKey, ceilingKey.

Queue and Deque

Deque means double ended queue: you can add and remove at both the front and the back. One class, ArrayDeque, works as both a queue (first in, first out) and a stack (last in, first out).

// Queue, first in first out
Deque<Request> queue = new ArrayDeque<>();
queue.addLast(request);        // enqueue
Request next = queue.pollFirst();   // dequeue, null if empty

// Stack, last in first out
Deque<Move> history = new ArrayDeque<>();
history.push(move);            // same as addFirst
Move last = history.pop();     // same as removeFirst

Do not use the old Stack class. It extends Vector, and every method is synchronized (slower, with no benefit here). It also iterates from bottom to top, which surprises people. ArrayDeque is the modern replacement.

Each operation has two flavours. They differ when the queue is empty or full:

Prefer the poll and peek methods and check for null. That is cleaner than catching NoSuchElementException.

PriorityQueue

A PriorityQueue is not sorted overall, but poll() always gives you the smallest item (by the comparator you gave it).

PriorityQueue<Request> pq = new PriorityQueue<>(Comparator.comparing(Request::getFloor));
pq.add(new Request(5));
pq.add(new Request(2));
pq.poll();     // the floor 2 request

Use it for an elevator scheduler or any "serve the most urgent next" problem.

Immutable and unmodifiable collections

List<String> fixed = List.of("a", "b", "c");        // cannot be changed at all
Map<String, Integer> m = Map.of("a", 1, "b", 2);
Set<String> s = Set.of("x", "y");

List<String> copy = List.copyOf(existingList);      // snapshot, safe to hand out
List<String> view = Collections.unmodifiableList(names);  // read only view of a live list

Calling add or remove on these throws UnsupportedOperationException. List.of(...) also rejects nulls.

This matters when one class owns a list. Do not hand out the real list. Hand out a copy. See the "leaking the parts" mistake in ../OOP/ClassRelationships.md.

// Bad: hands out the real map
public Map<MenuItem, List<OrderItem>> getOrderedItems() { return orderedItems; }
// A caller can now clear the table's orders. Returning Map.copyOf(orderedItems) prevents that.

Table.getOrderedItems() returns an unmodifiable copy instead.

Careful: Arrays.asList(...) is a third kind. Its size is fixed, but you can replace elements, and it is backed by the array you passed in.

Choosing by question

Do I need key to value lookup?
    YES -> Map.  Need sorted keys or ranges? TreeMap.  Enum key? EnumMap.
           Multiple threads? ConcurrentHashMap.  Otherwise HashMap.
    NO  |
        v
Do duplicates matter?
    NO (must be unique) -> Set.  Need order? LinkedHashSet or TreeSet.  Otherwise HashSet.
    YES (allowed)       |
                        v
    Do I add and remove mostly at the ends?
        YES -> ArrayDeque
        NO  -> ArrayList

Common mistakes

• list.contains() inside a loop. That is O(n squared): n items, each searching a list of n. Build a HashSet first.
• Custom objects in a HashSet or as HashMap keys without equals and hashCode. It fails silently: duplicates get in and lookups miss. In the repo, Locker in a Set still lacks both.
• Removing during a for each loop. Use removeIf or an Iterator.
• Using Stack or Vector. Old and slower. Use ArrayDeque and ArrayList.
• Returning the internal collection from a getter. The caller can then modify your object's state.
• Assuming HashMap keeps order. It does not, and the order can change between runs.
• HashMap shared across threads. Its inner structure can get damaged. See 18-Concurrency.md.

Where you see it in this repo

• Map<VehicleSize, List<ParkingSpot>> in ParkingManager, a map of lists (lists are created up front, not with computeIfAbsent)
• TreeMap with tailMap in the restaurant Layout, finding tables big enough for a party
• ConcurrentHashMap in SeatLockManager for seat locks
• Set<Locker>, Set<Reservation> in the locker and restaurant systems
• Stack<EditorMemento> in the Memento pattern, a good candidate to switch to ArrayDeque
• Map<String, EmailTemplate> in the Prototype registry

Related: 08-Generics.md, 15-EqualsAndHashCode.md, 16-LambdasAndStreams.md.