Java Collections Framework

List<E> is an ordered, indexable collection that allows duplicates. Main implementations: ArrayList (array-backed) and LinkedList (doubly linked). Use List.of(...) for a fixed immutable list.

The animation adds the same values to an ArrayList, LinkedHashSet, HashSet, TreeSet and a priority queue so you can compare the resulting order.

1List<Integer> xs = new ArrayList<>();
2xs.add(5); xs.add(1); xs.add(5);   // [5, 1, 5]: order kept, duplicates allowed
3xs.add(1, 9);                      // [5, 9, 1, 5]
4int first = xs.get(0);
5xs.set(0, 7);
6int at = xs.indexOf(1);            // 2

1List<Integer> list = new ArrayList<>();
2Set<Integer> linked = new LinkedHashSet<>();
3Set<Integer> hash = new HashSet<>();
4Set<Integer> tree = new TreeSet<>();
5PriorityQueue<Integer> heap = new PriorityQueue<>();
6for (int x : arr) {
7    list.add(x);        // keeps insertion order, keeps duplicates
8    linked.add(x);      // keeps insertion order, drops duplicates
9    hash.add(x);        // order decided by hash buckets
10    tree.add(x);        // always sorted
11    heap.add(x);        // heap array: only the smallest is guaranteed first
12}
13System.out.println(list + " " + linked + " " + hash + " " + tree + " " + heap);

Set<E> stores unique elements and answers “is it present?”. HashSet is unordered and averages O(1); LinkedHashSet keeps insertion order; TreeSet keeps elements sorted at O(log n) and supports range queries.

Adding an existing element returns false and changes nothing.

1Set<Integer> s = new HashSet<>();
2boolean a = s.add(3);   // true
3boolean b = s.add(3);   // false: already present
4boolean has = s.contains(3);
5s.remove(3);

1List<Integer> list = new ArrayList<>();
2Set<Integer> linked = new LinkedHashSet<>();
3Set<Integer> hash = new HashSet<>();
4Set<Integer> tree = new TreeSet<>();
5PriorityQueue<Integer> heap = new PriorityQueue<>();
6for (int x : arr) {
7    list.add(x);        // keeps insertion order, keeps duplicates
8    linked.add(x);      // keeps insertion order, drops duplicates
9    hash.add(x);        // order decided by hash buckets
10    tree.add(x);        // always sorted
11    heap.add(x);        // heap array: only the smallest is guaranteed first
12}
13System.out.println(list + " " + linked + " " + hash + " " + tree + " " + heap);

Map<K, V> associates keys with values and keys are unique. HashMap is unordered with average O(1) operations, LinkedHashMap keeps insertion (or access) order, and TreeMap keeps keys sorted. Useful methods: getOrDefault, merge, computeIfAbsent, entrySet.

Counting occurrences with merge is the standard idiom.

1Map<String, Integer> count = new HashMap<>();
2for (String w : "a b a c a b".split(" ")) count.merge(w, 1, Integer::sum);
3// {a=3, b=2, c=1} (order unspecified)
4Map<Integer, List<String>> byLen = new TreeMap<>();
5for (String w : List.of("aa", "b", "cc")) byLen.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);
6// {1=[b], 2=[aa, cc]}

Queue<E> models first-in, first-out. Each operation has a throwing and a non-throwing form: add/offer, remove/poll, element/peek. The non-throwing forms return false or null instead of throwing, so prefer offer, poll and peek in algorithms.

Implement a plain queue with ArrayDeque; use PriorityQueue when the next element must be the smallest.

1Queue<Integer> q = new ArrayDeque<>();
2q.offer(1); q.offer(2); q.offer(3);
3int head = q.peek();     // 1, not removed
4int out = q.poll();      // 1, removed
5Queue<Integer> empty = new ArrayDeque<>();
6Integer none = empty.poll();   // null, no exception

Deque<E> allows insertion and removal at both ends: offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast. It serves as a queue, a stack (push, pop, peek at the head) and a sliding-window helper.

Prefer ArrayDeque over the legacy Stack class and over LinkedList for stacks and queues.

1Deque<Integer> dq = new ArrayDeque<>();
2dq.offerLast(1); dq.offerLast(2); dq.offerFirst(0);   // [0, 1, 2]
3int a = dq.pollFirst();    // 0
4int b = dq.pollLast();     // 2
5Deque<Integer> stack = new ArrayDeque<>();
6stack.push(10); stack.push(20);
7int top = stack.pop();     // 20 (last in, first out)

Collection<E> is the root of lists, sets and queues (maps are separate). It provides size, isEmpty, contains, add, remove, addAll, removeIf, stream and iterator. Accepting a Collection parameter makes a method work with any of them.

Copy constructors such as new ArrayList<>(other) and new HashSet<>(other) convert between collection types.

1static int countPositive(Collection<Integer> c) {
2    int n = 0;
3    for (int x : c) if (x > 0) n++;
4    return n;
5}
6int a = countPositive(List.of(1, -1, 2));
7int b = countPositive(new HashSet<>(List.of(5, 6)));
8Set<Integer> unique = new HashSet<>(List.of(1, 1, 2));   // {1, 2}

java.util.Collections (plural) is a utility class: sort, reverse, shuffle, swap, max, min, frequency, binarySearch, unmodifiableList, emptyList, nCopies. Do not confuse it with the Collection interface.

Collections.sort is stable and uses an adaptive merge-based algorithm (TimSort).

1List<Integer> xs = new ArrayList<>(List.of(4, 1, 3, 1));
2Collections.sort(xs);                       // [1, 1, 3, 4]
3Collections.reverse(xs);                    // [4, 3, 1, 1]
4int f = Collections.frequency(xs, 1);       // 2
5int mx = Collections.max(xs);               // 4
6List<Integer> ro = Collections.unmodifiableList(xs);   // read-only view

ArrayList stores elements in a resizable array. get and set are O(1), add at the end is amortised O(1), and add/remove at an index shift elements in O(n). contains and indexOf are O(n).

It is the default list. Presize with new ArrayList<>(capacity) when you know the size.

LinkedList is a doubly linked list that implements both List and Deque. Add and remove at either end are O(1), but get(i) walks from the nearer end in O(n), and every element costs an extra object with two references.

Insertion in the middle is O(1) only through an iterator that is already there; finding the position is still O(n). In practice ArrayList or ArrayDeque is almost always faster.

1LinkedList<Integer> ll = new LinkedList<>(List.of(1, 2, 3));
2ll.addFirst(0);          // O(1)
3ll.removeLast();         // O(1)
4int x = ll.get(2);       // O(n): walks the links
5ListIterator<Integer> it = ll.listIterator();
6it.next(); it.add(99);   // insert after first element in O(1) once positioned

HashMap hashes each key to a bucket. get, put and remove average O(1). Keys need consistent equals and hashCode. Since Java 8 a bucket with many collisions becomes a balanced tree, so the worst case is O(log n) rather than O(n). It grows (doubles) when the load factor 0.75 is exceeded, rehashing all entries.

Iteration order is unspecified and can change after a resize.

1Map<String, Integer> m = new HashMap<>();
2m.put("x", 1);
3int v = m.getOrDefault("y", 0);     // 0
4m.computeIfAbsent("z", k -> 5);
5for (Map.Entry<String, Integer> e : m.entrySet()) System.out.println(e.getKey() + "=" + e.getValue());

HashSet is a HashMap whose values are ignored: it gives average O(1) add, contains and remove, with no ordering guarantee. The animation inserts the same numbers into a hash set with its buckets visible, so you can see why the iteration order is not insertion order.

Use LinkedHashSet when you need insertion order, and TreeSet when you need sorting.

1Set<Integer> seen = new HashSet<>();
2for (int x : new int[]{3, 1, 3, 2}) if (!seen.add(x)) System.out.println("duplicate " + x);   // duplicate 3
3boolean hasTwo = seen.contains(2);

1List<Integer> list = new ArrayList<>();
2Set<Integer> linked = new LinkedHashSet<>();
3Set<Integer> hash = new HashSet<>();
4Set<Integer> tree = new TreeSet<>();
5PriorityQueue<Integer> heap = new PriorityQueue<>();
6for (int x : arr) {
7    list.add(x);        // keeps insertion order, keeps duplicates
8    linked.add(x);      // keeps insertion order, drops duplicates
9    hash.add(x);        // order decided by hash buckets
10    tree.add(x);        // always sorted
11    heap.add(x);        // heap array: only the smallest is guaranteed first
12}
13System.out.println(list + " " + linked + " " + hash + " " + tree + " " + heap);

TreeMap is a red-black tree keyed by natural order or a comparator. get, put and remove are O(log n). Unique to sorted maps: firstKey, lastKey, floorKey, ceilingKey, lowerKey, higherKey, headMap, tailMap, subMap.

Use it for “nearest key”, range and ordered iteration queries; use HashMap otherwise.

1TreeMap<Integer, String> t = new TreeMap<>();
2t.put(10, "a"); t.put(20, "b"); t.put(30, "c");
3int fl = t.floorKey(25);      // 20: greatest key <= 25
4int ce = t.ceilingKey(25);    // 30: smallest key >= 25
5NavigableMap<Integer, String> mid = t.subMap(10, true, 20, true);   // {10=a, 20=b}

TreeSet keeps unique elements sorted, backed by a TreeMap. Operations are O(log n). It provides first, last, floor, ceiling, lower, higher, pollFirst, headSet, tailSet and descendingSet.

Elements need a consistent order. Two elements the comparator treats as equal count as duplicates even if equals says otherwise.

1TreeSet<Integer> ts = new TreeSet<>(List.of(8, 2, 5));   // [2, 5, 8]
2int lo = ts.first();          // 2
3Integer fl = ts.floor(6);     // 5
4Integer hi = ts.higher(8);    // null: nothing greater
5ts.pollFirst();               // removes 2

1List<Integer> list = new ArrayList<>();
2Set<Integer> linked = new LinkedHashSet<>();
3Set<Integer> hash = new HashSet<>();
4Set<Integer> tree = new TreeSet<>();
5PriorityQueue<Integer> heap = new PriorityQueue<>();
6for (int x : arr) {
7    list.add(x);        // keeps insertion order, keeps duplicates
8    linked.add(x);      // keeps insertion order, drops duplicates
9    hash.add(x);        // order decided by hash buckets
10    tree.add(x);        // always sorted
11    heap.add(x);        // heap array: only the smallest is guaranteed first
12}
13System.out.println(list + " " + linked + " " + hash + " " + tree + " " + heap);

PriorityQueue is a binary min-heap: poll returns the smallest element. offer and poll are O(log n), peek is O(1), remove(Object) is O(n), and building from a collection is O(n). For a max-heap pass Comparator.reverseOrder().

Iterating a PriorityQueue or printing it shows the heap array, not sorted order. Only repeated poll yields sorted order. The animation shows the array after each insertion.

1PriorityQueue<Integer> pq = new PriorityQueue<>();
2for (int x : new int[]{5, 1, 4, 2}) pq.offer(x);
3int min = pq.poll();     // 1
4PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
5maxHeap.addAll(List.of(5, 1, 4));
6int max = maxHeap.poll();   // 5

1List<Integer> list = new ArrayList<>();
2Set<Integer> linked = new LinkedHashSet<>();
3Set<Integer> hash = new HashSet<>();
4Set<Integer> tree = new TreeSet<>();
5PriorityQueue<Integer> heap = new PriorityQueue<>();
6for (int x : arr) {
7    list.add(x);        // keeps insertion order, keeps duplicates
8    linked.add(x);      // keeps insertion order, drops duplicates
9    hash.add(x);        // order decided by hash buckets
10    tree.add(x);        // always sorted
11    heap.add(x);        // heap array: only the smallest is guaranteed first
12}
13System.out.println(list + " " + linked + " " + hash + " " + tree + " " + heap);

ArrayDeque is a resizable circular array: O(1) amortised at both ends, compact and cache friendly. It rejects null elements. Use it for stacks, queues, BFS frontiers and monotonic-deque sliding windows.

It has no index access; for that use ArrayList.

1Deque<int[]> frontier = new ArrayDeque<>();
2frontier.offerLast(new int[]{0, 0});
3while (!frontier.isEmpty()) {
4    int[] cell = frontier.pollFirst();
5    // visit cell, offerLast its neighbours...
6}