The Collections Framework

The Collections Framework is a family of interfaces (List, Set, Queue, Deque, Map) and the classes that implement them (ArrayList, HashSet, HashMap, ArrayDeque and more). You choose an interface for the behaviour you need and an implementation for the performance you need.

30 min 4 code practice

ArrayList is a growable array: an Object[] plus a size counter. Reading by index is O(1), adding at the end is amortised O(1) because the array grows by 1.5x when full, and inserting or removing in the middle is O(n) because System.arraycopy shifts every later element.

34 min 5 code practice

LinkedList is a doubly linked list: a chain of node objects, each pointing to the one before and after. Adding or removing at either end is O(1), but reaching index i means walking node by node, so get(i) is O(n), and in practice ArrayList or ArrayDeque is almost always the better choice.

29 min 4 code practice

A HashMap is an array of buckets. It turns each key's hashCode into a bucket index (after mixing the high bits into the low ones), keeps colliding entries in a linked list that becomes a red-black tree past 8 nodes (Java 8+), and doubles the array when it's 75% full, giving O(1) expected get and put.

39 min 5 code practice

A Set holds each element at most once. HashSet is a HashMap with only keys (O(1), no order), LinkedHashSet adds insertion order, and TreeSet keeps elements sorted in a red-black tree (O(log n)) with navigation methods like floor and ceiling.

29 min 4 code practice

LinkedHashMap is a HashMap that also remembers order (insertion or, optionally, access order), which makes a five-line LRU cache. TreeMap keeps keys sorted in a red-black tree and answers range and nearest-key questions in O(log n).

31 min 4 code practice

A Queue hands elements out in arrival order (first in, first out); a Deque works at both ends, so it can also be a stack (last in, first out). ArrayDeque, a circular array, is the fastest general implementation of both and replaces Stack and, for queues, LinkedList.

29 min 4 code practice

PriorityQueue always hands out the smallest element first (or the largest, with a reversed comparator). It's a binary heap stored in an array: peek is O(1), offer and poll are O(log n), and its iteration order is not sorted.

32 min 5 code practice

An Iterator walks a collection one element at a time and is what every for-each loop uses behind the scenes. Most java.util iterators are fail-fast: if the collection is structurally changed by anything other than the iterator itself, the next step throws ConcurrentModificationException.

30 min 4 code practice

Comparable gives a class one built-in natural order (compareTo), and a Comparator is a separate object that describes any other order. Sorting, TreeMap, TreeSet, PriorityQueue, min and max all work through one of the two.

27 min 5 code practice

List.of, Set.of and Map.of (Java 9) create collections that can never change, and List.copyOf (Java 10) makes a frozen copy. Collections.unmodifiableList is different: a read-only view that still shows changes made to the original list underneath.

25 min 4 code practice

Java 21 added SequencedCollection, SequencedSet and SequencedMap: one standard way to get the first and last element, add at either end, and walk in reverse with reversed(), for every collection that has a defined order.

17 min 3 code practice

Choosing a collection comes down to four questions: duplicates or not, does order matter (and which order), how will you look things up, and do several threads share it? The answers point to ArrayList, HashMap, HashSet, LinkedHashMap, TreeMap, ArrayDeque or PriorityQueue almost every time.

20 min 4 code practice