Collections & Complexity

Implementations at a glance

Interface	Implementation	Backing structure	Order	Nulls	Thread-safe
List	ArrayList	resizable Object[] (grows ~1.5x)	insertion	yes	no
List	LinkedList	doubly linked nodes (also Deque)	insertion	yes	no
List	CopyOnWriteArrayList	array copied on each write	insertion	yes	yes
List	Vector / Stack	synchronized array (legacy)	insertion	yes	yes (coarse)
Set	HashSet	HashMap keys	none	one null	no
Set	LinkedHashSet	hash + linked list	insertion	one null	no
Set	TreeSet	red-black tree	sorted	no (natural order)	no
Set	EnumSet	bit vector	enum ordinal	no	no
Map	HashMap	table of buckets (list, tree at 8+)	none	1 null key, null values	no
Map	LinkedHashMap	hash + linked list (access-order option)	insertion/access	yes	no
Map	TreeMap	red-black tree	sorted by key	no null key	no
Map	ConcurrentHashMap	CAS + per-bin synchronized	none	no null key/value	yes
Map	Hashtable	synchronized buckets (legacy)	none	no nulls	yes (coarse)
Queue	ArrayDeque	circular array	FIFO/LIFO	no	no
Queue	PriorityQueue	binary min-heap	by priority (iteration not sorted)	no	no
Queue	ConcurrentLinkedQueue	lock-free linked	FIFO	no	yes
Queue	LinkedBlockingQueue / ArrayBlockingQueue	linked / bounded array	FIFO	no	yes

Big-O table

Structure	get / contains	add	remove	Notes
ArrayList	O(1) by index; O(n) contains	O(1) amortized end; O(n) middle	O(n)	shifts via System.arraycopy
LinkedList	O(n)	O(1) at ends / at iterator	O(1) at iterator; O(n) by index	poor cache locality, rarely wins
HashSet / HashMap	O(1) avg	O(1) avg	O(1) avg	worst O(log n) with treeified bins (Java 8+), O(n) before
LinkedHashMap	O(1)	O(1)	O(1)	extra pointer per entry
TreeSet / TreeMap	O(log n)	O(log n)	O(log n)	also floor/ceiling/subMap
ArrayDeque	O(n) search	O(1) both ends	O(1) both ends	faster than LinkedList as stack/queue
PriorityQueue	O(1) peek	O(log n) offer	O(log n) poll; O(n) remove(Object)	heapify from collection is O(n)
CopyOnWriteArrayList	O(1)	O(n)	O(n)	reads lock-free, snapshot iterators
ConcurrentHashMap	O(1) avg	O(1) avg	O(1) avg	size() is an estimate under concurrency

When to use which

• Default list: ArrayList. Default map: HashMap. Default set: HashSet. Default queue/stack: ArrayDeque.
• Need insertion order for a set/map: LinkedHashSet / LinkedHashMap.
• Need sorted order or range queries (headMap, ceilingKey): TreeMap / TreeSet (or ConcurrentSkipListMap for concurrent).
• LRU cache: LinkedHashMap(cap, 0.75f, true) overriding removeEldestEntry.
• Enum keys: EnumMap / EnumSet (array-backed, fastest).
• Top-K / scheduling by priority: PriorityQueue; wrap comparator for max-heap (Comparator.reverseOrder()).
• Read-mostly listener list, rare writes: CopyOnWriteArrayList.
• Producer/consumer hand-off: BlockingQueue (bounded to get back-pressure).
• Stack and Vector are legacy; use ArrayDeque.

Map<K, V> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) {
        return size() > MAX;
    }
};

HashMap internals

• Index = (n - 1) & (h ^ (h >>> 16)); table length is always a power of two (default 16, load factor 0.75).
• Resize doubles the table when size > threshold; entries split into "low" and "high" buckets (no rehash of hashCode).
• Bucket becomes a red-black tree when chain >= 8 and table >= 64 (else it resizes instead); un-treeifies at <= 6.
• Keys need consistent equals/hashCode; mutating a key after insertion loses the entry.
• Pre-size to avoid resizes: HashMap.newHashMap(n) (Java 19+) or new HashMap<>((int) (n / 0.75f) + 1).
• Java 7 and earlier: head insertion plus concurrent resize could create an infinite loop; fixed by tail insertion in Java 8, but HashMap is still not thread-safe.

Fail-fast vs fail-safe

Kind	Examples	Behaviour on structural modification during iteration
Fail-fast	ArrayList, HashMap, HashSet, TreeMap, LinkedList	ConcurrentModificationException via modCount check (best effort, not guaranteed)
Weakly consistent	ConcurrentHashMap, ConcurrentLinkedQueue, ConcurrentSkipListMap	never throws CME; may or may not reflect concurrent changes
Snapshot	CopyOnWriteArrayList, CopyOnWriteArraySet	iterates the array as of iterator creation; iterator remove() unsupported

list.removeIf(x -> x < 0);            // safe, single pass
for (Iterator<Integer> it = list.iterator(); it.hasNext();)
    if (it.next() < 0) it.remove();    // safe
// for (Integer x : list) list.remove(x);  -> CME (except removing the second-to-last element)

• Changing a value of an existing key (put on an existing key) is not structural; no CME.

ConcurrentHashMap

• Java 8+: no segments; CAS on empty bin head, synchronized on the bin head node otherwise. Java 7 used Segment locks.
• Null keys and values are rejected (ambiguity of get() == null).
• Individual operations are atomic; compound check-then-act sequences are not. Use atomic methods.

map.merge(word, 1, Integer::sum);                 // atomic counter
map.computeIfAbsent(k, key -> new ArrayList<>()).add(v);
map.putIfAbsent(k, v);
map.compute(k, (key, old) -> old == null ? 1 : old + 1);
long n = map.mappingCount();                       // prefer over size()

• computeIfAbsent mapping function must be short and must not modify the same map (can deadlock or throw IllegalStateException).
• LongAdder values (map.computeIfAbsent(k, x -> new LongAdder()).increment()) beat Integer merge under heavy contention.
• Bulk ops with parallelism threshold: forEach(1, ...), reduce, search.

Immutable collections

Factory	Java	Nulls	Mutation	Notes
List.of(...), Set.of(...), Map.of(...)	9	NPE	UnsupportedOperationException	truly immutable; Set.of/Map.of reject duplicates (IllegalArgumentException); iteration order of Set/Map is randomized per JVM run
Map.ofEntries(entry(k,v), ...)	9	NPE	UOE	for more than 10 pairs
List.copyOf(c) / Set.copyOf / Map.copyOf	10	NPE	UOE	returns same instance if already immutable
stream.toList()	16	allowed	UOE	unmodifiable list, allows nulls
Collectors.toUnmodifiableList()	10	NPE	UOE
Collections.unmodifiableList(l)	1.2	allowed	UOE	a view: changes to backing list show through
Arrays.asList(arr)	1.2	allowed	set ok, add/remove UOE	fixed-size, write-through to array

• List.of(...).contains(null) throws NPE.
• Java 21: SequencedCollection / SequencedMap add getFirst, getLast, reversed(), addFirst to List, Deque, LinkedHashSet, LinkedHashMap, SortedSet.

Sorting and comparators

list.sort(Comparator.comparing(Person::lastName)
                    .thenComparing(Person::age, Comparator.reverseOrder())
                    .thenComparing(Person::name, Comparator.nullsLast(Comparator.naturalOrder())));
Collections.sort(list);        // stable merge sort/TimSort, O(n log n)
Arrays.sort(int[])             // dual-pivot quicksort, not stable; Object[] uses TimSort (stable)

• Comparator must be consistent with equals for TreeSet/TreeMap; they treat compare == 0 as the same key.
• Never compute a - b in a comparator (overflow); use Integer.compare.

Pitfalls

• ArrayList.remove(int) vs remove(Object): list.remove(1) removes index 1; use remove(Integer.valueOf(1)) for the value.
• subList is a view; structural change to the parent invalidates it (CME).
• HashSet<MutableKey>: mutating fields used in hashCode makes the element unfindable.
• TreeMap with a non-comparable key throws ClassCastException on first put.
• Collections.synchronizedList still needs manual locking for iteration.
• PriorityQueue iterator/toString order is heap order, not sorted; poll repeatedly for sorted output.
• Equal hashCode is required for equal objects; the reverse is not.