Choosing a collection
Start with ArrayList, HashMap and HashSet, and switch only when you need something they lack. Code written
against the interfaces does not change when you switch.
Decision guide
Section titled “Decision guide”| You need | Use |
|---|---|
| Maps: fast lookup by key, any order | HashMap |
| insertion order, access order or an LRU cache | LinkedHashMap |
sorted keys, floorKey/ceilingKey, range views |
TreeMap |
keys compared by identity (===) instead of equals() |
IdentityHashMap |
| contents fixed after creation | Map.of / Map.copyOf |
| Sets: fast membership tests, any order | HashSet |
| insertion order | LinkedHashSet |
sorted order, floor/ceiling, range views |
TreeSet |
| contents fixed after creation | Set.of / Set.copyOf |
| Sequences: access by index, appending, sorting | ArrayList |
inserts or removals at a position reached with a ListIterator |
LinkedList |
a FIFO queue (offer/poll) or a LIFO stack (push/pop) |
ArrayDeque |
| the smallest (or largest) element first | PriorityQueue |
| contents fixed after creation | List.of / List.copyOf |
Vector and Stack are legacy classes; prefer ArrayList and ArrayDeque. LinkedList is rarely faster than
ArrayList, and its get(i) is O(n).
Comparison tables
Section titled “Comparison tables”n is the collection size. “Amortized” means occasionally O(n) when the backing array grows. Hash costs assume
well-distributed hashCode() values.
| Class | null |
get(i) |
add(e) at end |
add(i, e) / removeAt(i) |
contains |
|---|---|---|---|---|---|
ArrayList |
yes | O(1) | O(1) amortized | O(n) | O(n) |
LinkedList |
yes | O(n) | O(1) | O(1) at an iterator, O(n) to get there | O(n) |
Vector, Stack |
yes | O(1) | O(1) amortized | O(n) | O(n) |
List.of / copyOf |
no | O(1) | immutable | immutable | O(n) |
Queues and deques
Section titled “Queues and deques”| Class | Order | null |
offer |
poll |
peek |
contains / remove(o) |
|---|---|---|---|---|---|---|
ArrayDeque |
FIFO / LIFO | no | O(1) amortized | O(1) | O(1) | O(n) |
LinkedList |
FIFO / LIFO | yes | O(1) | O(1) | O(1) | O(n) |
PriorityQueue |
head = smallest | no | O(log n) | O(log n) | O(1) | O(n) |
| Class | Iteration order | null |
add / remove / contains |
|---|---|---|---|
HashSet |
unspecified | yes | O(1) |
LinkedHashSet |
insertion | yes | O(1) |
TreeSet |
sorted | no (unless the comparator handles it) | O(log n) |
Set.of / copyOf |
unspecified | no | contains O(1); immutable |
| Class | Iteration order | null keys / values |
get / put / remove / containsKey |
|---|---|---|---|
HashMap |
unspecified | yes / yes | O(1) |
LinkedHashMap |
insertion (or access) | yes / yes | O(1) |
TreeMap |
sorted by key | no / yes | O(log n) |
IdentityHashMap |
unspecified | yes / yes | O(1) |
Map.of / copyOf |
unspecified | no / no | get / containsKey O(1); immutable |
containsValue is O(n) on every map. Iterating any collection is O(n).
JS runs application code on one thread, so there is no thread-safe variant to choose. The
Collections.synchronized* wrappers exist for API compatibility and only delegate; parallelStream() runs
sequentially (see Compatibility). Measured numbers are in
Benchmarks.
Common picks in code
Section titled “Common picks in code”import { ArrayDeque, PriorityQueue, LinkedHashMap, TreeMap, LinkedHashSet, Comparator } from '@ylcnfrht/collections';
// FIFO queue and LIFO stackconst jobs = new ArrayDeque<string>();jobs.offer('a');jobs.offer('b');console.log(jobs.poll()); // → aconst undo = new ArrayDeque<string>();undo.push('type');undo.push('delete');console.log(undo.pop()); // → delete
// priority: largest firstconst urgent = new PriorityQueue<number>(Comparator.reverseOrder<number>());[3, 10, 7].forEach((n) => urgent.offer(n));console.log(urgent.poll()); // → 10
// LRU cache that keeps the 2 most recently used entriesconst cache = LinkedHashMap.lru<string, number>(2);cache.put('a', 1);cache.put('b', 2);cache.get('a'); // touch acache.put('c', 3); // evicts bconsole.log(cache.toString()); // → {a=1, c=3}
// which bracket does a value fall in?const tax = new TreeMap<number, string>();tax.put(0, 'low');tax.put(10_000, 'mid');tax.put(50_000, 'high');console.log(tax.floorEntry(23_500)?.getValue()); // → mid
// de-duplicate, keeping first-seen orderconst unique = new LinkedHashSet<string>();['b', 'a', 'b', 'c', 'a'].forEach((s) => unique.add(s));console.log(unique.toString()); // → [b, a, c]Full APIs: Lists, Queues and deques, Sets, Maps, Immutable collections and wrappers.