Java Collections

1. When You read by position, or mostly append at the end

   , choose

   ArrayList

2. When Each element may appear only once

   , choose

   HashSet

3. When You look values up by a key

   , choose

   HashMap

4. When The keys must stay in sorted order

   , choose

   TreeMap

5. When You take work in arrival order, or need a stack

   , choose

   ArrayDeque

6. When The smallest element must always come out next

   , choose

   PriorityQueue

Keep order and duplicates, and reach any element by its position.

• ArrayList

  Elements side by side in one array: fast to read by position, slow to insert at the front.

  Use when

  You read by position, or mostly append at the end. It is the default List.

  Facts

  Read by position

  Constant

  any index

  Append at the end

  Constant

  averaged

  Insert at the front

  Shifts everything

  every element moves up

  Watch for

  Removing elements through the list inside a for-each loop over it.

  ConcurrentModificationException: Removing Inside a for-each Loop

• LinkedList

  Separate nodes, each pointing at the next: cheap to insert, slow to reach by position.

  Use when

  You insert or remove in the middle while walking the list with its iterator.

  Facts

  Read by position

  Walks to it

  link by link

  Insert at the front

  Constant

  two pointers change

  Memory

  Two extra pointers

  per element

  Watch for

  A get(i) loop over it, which walks the links again on every call.

• List.of(...)

  An unmodifiable list: add, remove and set compile, then throw when called.

  Use when

  The contents are known up front and nothing should change them.

  Facts

  add, remove, set

  Throws

  UnsupportedOperationException

  null element

  Refused

  throws on construction

  To change it

  Copy it

  into new ArrayList<>(…)

  Watch for

  Treating Arrays.asList(…) as the same thing: it allows set, but never add.

  Unmodifiable Lists: Why List.of(...) Refuses add()

Keep each element once; they differ in the order they give elements back.

• HashSet

  Keeps each element once, deciding sameness by hashCode and then equals, in no promised order.

  Use when

  You need fast membership checks and the order does not matter.

  Facts

  add, contains

  Constant

  on average

  Iterates in

  No promised order

  can change between versions

  Elements need

  hashCode, equals

  both overridden

  Watch for

  A class that overrides neither equals nor hashCode: every object counts as new.

• LinkedHashSet

  A HashSet that also remembers the order elements were first added.

  Use when

  You need duplicates removed but the original order kept, or reproducible output.

  Facts

  add, contains

  Constant

  plus two pointers each

  Iterates in

  Insertion order

  the order you added them

  Watch for

  Using a HashSet where output must be reproducible: its order only looks stable.

• TreeSet

  Keeps its elements sorted, and answers first, last and ceiling.

  Use when

  You need the elements in sorted order, or the nearest one to a value.

  Facts

  add, contains

  Logarithmic

  grows with the log of the size

  Iterates in

  Sorted order

  natural, or the Comparator's

  Elements need

  Comparable

  or a Comparator given to it

  Watch for

  Adding elements that are not Comparable without giving the set a Comparator.

Find a value by its key; they differ in the order the keys come back in.

• HashMap

  Finds a value by turning its key's hashCode into a bucket, in no promised order.

  Use when

  You look values up by a key and the order of keys does not matter.

  Facts

  get, put

  Constant

  on average

  Crowded bucket

  Becomes a tree

  at 8 entries, with 64 buckets

  Rebuilds at

  0.75 full

  the default load factor

  Watch for

  Reading a null from get as a missing key: the key may hold a null value.

  Null Keys: Allowed in HashMap, Refused by TreeMap

• LinkedHashMap

  A HashMap that iterates in insertion order, or in access order when asked.

  Use when

  Output must match the input order, or you want a small least-recently-used cache.

  Facts

  get, put

  Constant

  plus two pointers each

  Iterates in

  Insertion order

  or access order, if built so

  Watch for

  Expecting reads to reorder it: only the access-order constructor does that.

• TreeMap

  Keeps its keys sorted, so it answers nearest-key questions such as ceilingKey.

  Use when

  You need keys in sorted order, or the key just below or above a value.

  Facts

  get, put

  Logarithmic

  grows with the log of the size

  Nearest key

  ceilingKey, headMap

  sorted maps only

  null key

  Refused

  NullPointerException

  Watch for

  Swapping it in for a HashMap that holds a null key: the first put throws.

  Null Keys: Allowed in HashMap, Refused by TreeMap

Decide what comes out next: the oldest, the newest, or the smallest.

• ArrayDeque

  A double-ended queue: one class serves as a queue, a stack, or both at once.

  Use when

  You take work in arrival order, or need a stack.

  Facts

  poll()

  First or last in

  as you choose

  Both ends

  addFirst, addLast

  and pollFirst, pollLast

  Watch for

  Reaching for the legacy Stack class instead.

  Stack vs ArrayDeque: Why the Stack Class Should Not Be Used

• PriorityQueue

  A heap: poll() always takes the smallest element, by the order you supply.

  Use when

  You process work by priority, not by the order it arrived.

  Facts

  poll()

  The smallest

  natural, or the Comparator's

  Elements need

  Comparable

  or a Comparator given to it

  Watch for

  Printing or iterating it and expecting the order poll() will give.

  PriorityQueue Iteration Order: Printing Does Not Show Poll Order

How every sorted collection and every sort call decides which of two comes first.

• Comparable

  The one natural order a type gives itself, through compareTo.

  Use when

  Your type has one obvious order, such as dates or amounts.

  Facts

  Lives

  On the class

  as compareTo

  Orders per type

  One

  the natural order

  Used by

  sort, TreeSet, TreeMap

  when no Comparator is given

  Watch for

  Comparing two ints by subtracting one from the other, which can overflow.

  Integer Overflow in Comparators: Why Subtraction Is a Bug

• Comparator

  An order kept outside the type, so one type can be sorted many ways.

  Use when

  You need a second order, or to sort a type you cannot change.

  Facts

  Lives

  A separate object

  passed at the call site

  Orders per type

  As many as you like

  one per Comparator

  Class source

  Not needed

  works on types you do not own

  Watch for

  Breaking its contract, so a sort that always worked throws on one list.

  Comparator Contract Violations: "Comparison Method Violates Its General Contract"

• Comparator on Two Fields

  Builds a comparator from one field; thenComparing adds the tie-breakers.

  Use when

  You sort on several fields, or need one of them reversed.

  Facts

  comparing

  First key

  one field

  thenComparing

  Tie-breaker

  only when the keys before tie

  reversed()

  Flips the chain

  everything before it

  Watch for

  Calling reversed() last to reverse one field: it reverses the whole chain.

1. 01

   Removing from a list inside a for-each loop over it.

   ConcurrentModificationException: Removing Inside a for-each Loop

2. 02

   Calling add on a list made by List.of(…).

   Unmodifiable Lists: Why List.of(...) Refuses add()

3. 03

   Printing a PriorityQueue to check the order it will give elements back.

   PriorityQueue Iteration Order: Printing Does Not Show Poll Order

4. 04

   Using Stack when ArrayDeque does the same job without the synchronisation.

   Stack vs ArrayDeque: Why the Stack Class Should Not Be Used

5. 05

   Comparing two ints by subtracting one from the other.

   Integer Overflow in Comparators: Why Subtraction Is a Bug

• The Collections Framework5 questions

  Practise

• Lists6 questions

  Practise

• Sets and Queues5 questions

  Practise

• Maps and HashMap Internals5 questions

  Practise

• Sorting Your Own Types5 questions

  Practise