--- title: Java Collections description: Cheat sheet for the Java collections framework plus strings and arrays, with the Big-O of every structure and a table for picking the right one. tags: [java, collections, data-structures, interview] --- Fast lookup for the Java APIs that show up in coding rounds. The code carries most of it, and there is a line of explanation only where an API is easy to get wrong. ## Pick the right one | Need | Use | | ------------------------------------------- | ---------------------------------- | | Index lookup, mostly reads | `ArrayList` | | FIFO queue | `ArrayDeque` | | LIFO stack | `ArrayDeque`, not `Stack` | | Add and remove at both ends | `ArrayDeque` | | Key to value, order does not matter | `HashMap` | | Key to value, sorted keys | `TreeMap` | | Key to value, insertion order kept | `LinkedHashMap` | | Unique items, order does not matter | `HashSet` | | Unique items, sorted | `TreeSet` | | Always pull the smallest or largest | `PriorityQueue` | | Count frequency of lowercase letters | `int[26]` | | Count frequency of anything else | `HashMap` with `merge` | | A fixed set of known values, never modified | `List.of`, `Set.of`, `Map.of` | ## Complexity at a glance | Structure | Access | Contains | Insert | Remove | Notes | | --------------- | ------------- | -------- | ------------------------------------- | -------------------------------------- | ------------------------------------------- | | `ArrayList` | O(1) | O(n) | O(1) amortized at end, O(n) in middle | O(n) | Array backed, capacity doubles on growth | | `LinkedList` | O(n) | O(n) | O(1) at either end | O(1) at either end, O(n) by index | Doubly linked | | `ArrayDeque` | Not indexable | O(n) | O(1) both ends | O(1) both ends | Fastest stack and queue | | `HashMap` | O(1) avg | O(1) avg | O(1) avg | O(1) avg | O(log n) worst case per bucket since Java 8 | | `LinkedHashMap` | O(1) avg | O(1) avg | O(1) avg | O(1) avg | Keeps insertion order | | `TreeMap` | O(log n) | O(log n) | O(log n) | O(log n) | Red black tree, keys sorted | | `HashSet` | n/a | O(1) avg | O(1) avg | O(1) avg | `HashMap` underneath | | `TreeSet` | n/a | O(log n) | O(log n) | O(log n) | Sorted | | `PriorityQueue` | `peek` O(1) | O(n) | O(log n) | `poll` O(log n), `remove(Object)` O(n) | Binary heap, iteration order is not sorted | ## Strings `String` is immutable. Every concat builds a new object, so loop with `StringBuilder`. ```java String s = "hello"; s.length(); s.charAt(i); s.isEmpty(); s.trim(); s.substring(start, end); // end is exclusive s.indexOf("lo"); // index or -1 s.contains("ell"); s.equals(other); // never use == on strings s.equalsIgnoreCase(other); s.compareTo(other); // <0, 0, >0 s.toLowerCase(); s.split(","); // takes a regex, not a plain string s.repeat(3); String.join(",", list); ``` ### StringBuilder ```java StringBuilder sb = new StringBuilder(); StringBuilder sb = new StringBuilder("Hello world"); sb.append('c'); // char, String, int, double all work sb.insert(0, "x"); sb.deleteCharAt(i); sb.setCharAt(i, 'a'); sb.charAt(i); sb.indexOf("lo"); sb.length(); sb.reverse(); sb.toString(); // Two builders are only equal as strings sb.toString().equals(other.toString()); ``` ### String vs StringBuffer vs StringBuilder | Feature | `String` | `StringBuffer` | `StringBuilder` | | --------------- | -------------------------------------- | ------------------------------------------------------ | ------------------------------------------ | | Storage | String pool if a literal, else heap | Heap | Heap | | Object creation | New object on every change (immutable) | Changes the same object (mutable) | Changes the same object (mutable) | | Memory usage | High, one object per change | Moderate, no new objects but synchronization overhead | Low, no new objects and no synchronization | | Thread safety | Thread safe because immutable | Thread safe, methods are synchronized | Not thread safe | | Performance | Slow for heavy modification | Slower than `StringBuilder` because of synchronization | Fastest for modification on one thread | | Use case | Constant strings and light work | String edits shared across threads | Hot string edits on one thread | Default to `StringBuilder`. Reach for `StringBuffer` only when several threads edit the same buffer. ### Conversions Everything in one place, since these are the lines you forget under pressure. ```java // String and char[] char[] chars = s.toCharArray(); String back = String.valueOf(chars); String back = new String(chars); // String and int int n = Integer.parseInt("200"); String s = String.valueOf(200); String s = Integer.toString(200); // char and String String s = Character.toString('a'); String s = String.valueOf('a'); // char and int digit int d = c - '0'; // '7' becomes 7 int idx = c - 'a'; // 'c' becomes 2, for int[26] buckets // List and array List list = new ArrayList<>(Arrays.asList(arr)); // arr is Integer[] Integer[] arr = list.toArray(new Integer[0]); int[][] grid = list.toArray(new int[0][]); // List ``` ### char ```java Character.isLetter(c); Character.isDigit(c); Character.isLetterOrDigit(c); Character.isUpperCase(c); Character.isWhitespace(c); Character.toUpperCase(c); Character.toLowerCase(c); ``` ### Integer ```java Integer.MIN_VALUE; Integer.MAX_VALUE; Integer.parseInt(s); Integer.parseInt(s, 2); // binary string to int Integer.toBinaryString(n); Integer.bitCount(n); // number of set bits Integer.compare(a, b); // overflow safe, unlike a - b Integer.valueOf(s); // boxed Integer, parseInt gives a primitive int ``` `Integer` caches boxed values from -128 to 127, so `==` on `Integer` gives the right answer for small numbers and the wrong one for large ones. Use `.equals()` or unbox to `int`. ### Number limits Every primitive has a fixed range, and the constants are the readable way to say it. Reach for them when you need a sentinel for a min or max search, or when you are checking whether a value fits. | Type | Bits | Min | Max | | -------- | ---- | -------------------------- | ------------------------------------------------ | | `byte` | 8 | -128 | 127 | | `short` | 16 | -32,768 | 32,767 | | `char` | 16 | 0 | 65,535 | | `int` | 32 | -2,147,483,648 | 2,147,483,647, about 2.1 billion | | `long` | 64 | -9,223,372,036,854,775,808 | 9,223,372,036,854,775,807, about 9.2 quintillion | | `float` | 32 | about -3.4e38 | about 3.4e38, 7 digits of precision | | `double` | 64 | about -1.8e308 | about 1.8e308, 15 digits of precision | ```java Integer.MIN_VALUE; // -2147483648 Integer.MAX_VALUE; // 2147483647 Long.MIN_VALUE; // -9223372036854775808 Long.MAX_VALUE; // 9223372036854775807 Byte.MIN_VALUE; Byte.MAX_VALUE; Short.MIN_VALUE; Short.MAX_VALUE; Character.MIN_VALUE; Character.MAX_VALUE; Integer.SIZE; // 32 bits Integer.BYTES; // 4 bytes Double.MAX_VALUE; // largest positive double Double.MIN_VALUE; // smallest positive double, 4.9e-324, not the most negative Double.POSITIVE_INFINITY; Double.NEGATIVE_INFINITY; Double.NaN; ``` `Double.MIN_VALUE` is the trap. It is the smallest positive value, not the lowest one. For the lowest possible double write `-Double.MAX_VALUE`. `NaN` is not equal to itself, so `d == Double.NaN` is always false. Use `Double.isNaN(d)`, and `Double.isInfinite(d)` for the other two. ### Long `long` is the escape hatch when `int` is too small: sums of a large array, products of two ints, timestamps in milliseconds, anything counting past 2.1 billion. ```java long x = 10; // widening from int is automatic long big = 10000000000L; // literal past int range needs the L int back = (int) big; // narrowing needs a cast and can silently truncate int safe = Math.toIntExact(big); // throws ArithmeticException instead Long.MIN_VALUE; Long.MAX_VALUE; Long.SIZE; // 64 bits Long.BYTES; // 8 bytes Long.parseLong(s); Long.compare(a, b); Long.toBinaryString(n); Long.bitCount(n); ``` The suffix is the part that bites. A numeric literal is an `int` until you write `L`, so the arithmetic happens in `int` and overflows before the value is ever widened to `long`. ```java long ms = 24 * 60 * 60 * 1000; // fine, fits in int long us = 24 * 60 * 60 * 1000 * 1000; // overflows, all int math long us = 24L * 60 * 60 * 1000 * 1000; // one L on the left fixes the whole expression long sum = 0; for (int n : nums) sum += n; // sum is long, each n widens, safe ``` `Long.MIN_VALUE` is one further from zero than `Long.MAX_VALUE`, so it has no positive twin. Negating or taking the absolute value of it gives you the same number back. ```java Math.abs(Long.MIN_VALUE); // still Long.MIN_VALUE, negative -Long.MIN_VALUE; // same, wraps to itself Long.MIN_VALUE / -1; // Long.MIN_VALUE, no exception thrown Math.negateExact(Long.MIN_VALUE); // throws ArithmeticException ``` Java will not let you write the constant as a plain literal either. `-9223372036854775808L` compiles only because the minus is part of the expression; `9223372036854775808L` on its own is a compile error. Use `Long.MIN_VALUE`. Boxing rules match `Integer`. `Long` caches -128 to 127, so `==` on two `Long` objects is right for small values and wrong for big ones. Compare with `.equals()` or unbox. ### Overflow `int` arithmetic wraps around in silence. Nothing throws, you get a negative number and a wrong answer far from the line that caused it. ```java Integer.MAX_VALUE + 1; // -2147483648 Math.abs(Integer.MIN_VALUE); // still -2147483648, abs has no positive answer here int big = 100000 * 100000; // overflows before the assignment long ok = 100000L * 100000; // one L makes the whole product long int mid = (low + high) / 2; // overflows on large indexes int mid = low + (high - low) / 2; // safe binary search midpoint ``` Three ways out. Compute in `long` and cast back once you know it fits. Use `Math.addExact`, `Math.subtractExact` or `Math.multiplyExact`, which throw `ArithmeticException` instead of wrapping. Or use `Math.toIntExact(longValue)` when narrowing. Sentinels overflow too. `Integer.MAX_VALUE` is the usual "infinity" for a shortest path or a min search, but the moment you add a weight to it the value wraps negative and the algorithm picks the broken path. ```java int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) { } // guard first // or give yourself headroom final int INF = Integer.MAX_VALUE / 2; // or hold distances in long ``` ### Math ```java Math.abs(n); Math.max(a, b); Math.min(a, b); Math.pow(2, 10); // returns double, cast for int Math.sqrt(n); // double Math.cbrt(n); Math.floor(x); Math.ceil(x); // double in, double out Math.round(x); // long for double, int for float Math.hypot(a, b); Math.floorDiv(-7, 2); // -4, rounds down Math.floorMod(-7, 3); // 2, never negative -7 % 3; // -1, the sign follows the left operand Math.addExact(a, b); // throws on overflow Math.multiplyExact(a, b); Math.toIntExact(longValue); ``` Integer division truncates toward zero, so `7 / 2` is 3 and `-7 / 2` is -3. For a ceiling divide of positive numbers use `(a + b - 1) / b`. `%` keeps the sign of the left side, which breaks index wrapping on a negative step. `Math.floorMod(i, n)` gives the answer you wanted. ### Frequency count ```java int[] freq = new int[26]; for (char c : s.toCharArray()) { freq[c - 'a']++; } Map freq = new HashMap<>(); for (char c : s.toCharArray()) { freq.merge(c, 1, Integer::sum); } ``` ## Arrays ```java int[] a = new int[20]; // filled with 0 int[] a = {1, 2, 3, 4, 5}; int[][] grid = new int[10][10]; a.length; // field, no parentheses Arrays.fill(a, 10); Arrays.fill(grid[0], -1); Arrays.sort(a); // dual pivot quicksort, O(n log n) Arrays.sort(a, from, to); Arrays.binarySearch(a, key); // array must be sorted first Arrays.copyOf(a, newLength); Arrays.copyOfRange(a, from, to); Arrays.equals(a, b); Arrays.toString(a); Arrays.deepToString(grid); // for 2D Arrays.stream(a).sum(); Arrays.stream(a).max().getAsInt(); ``` Descending sort needs boxed types. `Arrays.sort(int[], Comparator)` does not compile. ```java Integer[] a = {3, 1, 2}; Arrays.sort(a, Collections.reverseOrder()); // For int[], sort ascending then reverse by hand int[] b = {3, 1, 2}; Arrays.sort(b); for (int i = 0, j = b.length - 1; i < j; i++, j--) { int tmp = b[i]; b[i] = b[j]; b[j] = tmp; } // Sort 2D by a column int[][] intervals = {{1, 3}, {0, 2}}; Arrays.sort(intervals, (x, y) -> x[0] - y[0]); Arrays.sort(intervals, Comparator.comparingInt(x -> x[0])); ``` ## List ### ArrayList ```java List list = new ArrayList<>(); List list = new ArrayList<>(Arrays.asList(60, 25, 12)); List list = new ArrayList<>(other); // copy list.size(); list.isEmpty(); list.get(i); list.set(i, value); list.add(10); // append list.add(i, 10); // insert at i, shifts right list.addAll(other); list.remove(2); // by index for List list.remove(Integer.valueOf(2)); // by value list.contains(120); list.indexOf(o); // first match or -1 list.clear(); list.subList(from, to); // view, not a copy list.toArray(new Integer[0]); ``` `Arrays.asList(...)` returns a fixed size view of the array. `add` and `remove` on it throw `UnsupportedOperationException`, though `set` works and writes straight through to the backing array. Wrap it in `new ArrayList<>(...)` when you need to mutate. For a list that cannot be changed at all, see the immutable factories below. Nested lists: ```java List> grid = new ArrayList<>(); for (int i = 0; i < 100; i++) { grid.add(new ArrayList<>()); } ``` ### Filtering and transforming `removeIf` edits in place. Everything else here reads the list and builds a new one, leaving the original alone. ```java list.removeIf(n -> n % 2 == 0); // in place, no iterator needed // Filter and map List evens = list.stream().filter(n -> n % 2 == 0).toList(); List names = people.stream().map(Person::getName).toList(); List flat = nested.stream().flatMap(List::stream).toList(); // Group, partition, join Map> byCity = people.stream().collect(Collectors.groupingBy(Person::getCity)); Map> split = list.stream().collect(Collectors.partitioningBy(n -> n > 10)); String csv = String.join(", ", names); // Reduce to one value int sum = list.stream().mapToInt(Integer::intValue).sum(); double avg = list.stream().mapToInt(Integer::intValue).average().orElse(0); int max = list.stream().mapToInt(Integer::intValue).max().orElseThrow(); // Ask a question boolean any = list.stream().anyMatch(n -> n > 100); boolean all = list.stream().allMatch(n -> n > 0); long count = list.stream().filter(n -> n > 10).count(); // Dedupe and slice List unique = list.stream().distinct().toList(); List firstFive = list.stream().limit(5).toList(); // Back to an array Integer[] arr = list.stream().toArray(Integer[]::new); int[] prim = list.stream().mapToInt(Integer::intValue).toArray(); ``` Two `toList` calls exist and they are not the same. `stream().toList()` (Java 16 and up) returns an unmodifiable list, while `collect(Collectors.toList())` returns a mutable one. Choosing the first and then calling `add` on it throws `UnsupportedOperationException` somewhere far from the cause. `subList` returns a view, not a copy. Writes go through to the backing list, and structurally changing the backing list invalidates the view. ```java List slice = list.subList(2, 5); // indexes 2, 3, 4 slice.clear(); // deletes them from list List copy = new ArrayList<>(list.subList(2, 5)); // real copy ``` `list.sort(...)` reorders in place. `list.stream().sorted()` leaves the original alone and gives you a new sequence, which is the one to use when the caller owns the list. `new ArrayList<>(100)` sets capacity, not size. The list is still empty, and the argument only saves the array copies that growth would otherwise cost. ### LinkedList Use it when you need `Deque` behaviour on a `List`. For a plain stack or queue, `ArrayDeque` is faster. ```java LinkedList ll = new LinkedList<>(); ll.add(e); ll.add(i, e); ll.addFirst(e); ll.addLast(e); ll.getFirst(); ll.getLast(); ll.peekFirst(); ll.peekLast(); // null if empty ll.removeFirst(); ll.removeLast(); // throw if empty ll.pollFirst(); ll.pollLast(); // null if empty ll.size(); ``` ## Stack `Stack` extends `Vector` and every method is synchronized, so it is slow. Interviewers expect `ArrayDeque`. ```java Deque stack = new ArrayDeque<>(); stack.push(10); // addFirst stack.pop(); // removeFirst, throws if empty stack.peek(); // null if empty stack.isEmpty(); stack.size(); ``` Legacy form, still fine to read: ```java Stack stack = new Stack<>(); stack.push(10); stack.pop(); stack.peek(); stack.isEmpty(); ``` ## Queue ```java Queue queue = new ArrayDeque<>(); // LinkedList also works, slower queue.offer(10); // add at tail, returns false when full queue.add(10); // add at tail, throws when full queue.poll(); // remove head, null if empty queue.remove(); // remove head, throws if empty queue.peek(); // head without removing, null if empty queue.isEmpty(); queue.size(); ``` The pattern is the same everywhere: `offer` / `poll` / `peek` return a special value, `add` / `remove` / `element` throw. Prefer the first set. `ArrayDeque` rejects `null` elements. `LinkedList` allows them, which is why `poll` returning `null` is ambiguous there. ### BFS template ```java Queue q = new ArrayDeque<>(); q.offer(new int[]{0, 0}); boolean[][] seen = new boolean[rows][cols]; seen[0][0] = true; while (!q.isEmpty()) { int size = q.size(); // one level at a time for (int i = 0; i < size; i++) { int[] cur = q.poll(); // visit neighbours, mark seen, offer } } ``` ## PriorityQueue A binary heap. `peek` and `poll` give the smallest by default. Iterating it does not give sorted order, only `poll` does. ```java PriorityQueue minHeap = new PriorityQueue<>(); PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder()); PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> b - a); // By a field PriorityQueue pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); pq.offer(10); pq.poll(); // smallest, null if empty pq.peek(); pq.size(); pq.isEmpty(); ``` Top K pattern: keep a min heap of size k, evict the head once it overflows. ```java PriorityQueue pq = new PriorityQueue<>(); for (int n : nums) { pq.offer(n); if (pq.size() > k) pq.poll(); } // pq.peek() is the kth largest ``` ## Map ### HashMap ```java Map map = new HashMap<>(); Map> map = new HashMap<>(); map.size(); map.isEmpty(); map.containsKey(key); map.containsValue(value); // O(n) map.get(key); // null if absent map.getOrDefault(key, 0); map.put(key, value); // returns the old value or null map.putIfAbsent(key, value); map.remove(key); map.clear(); map.keySet(); map.values(); map.entrySet(); // Counting and grouping without null checks map.merge(key, 1, Integer::sum); map.computeIfAbsent(key, k -> new ArrayList<>()).add(item); ``` `getOrDefault`, `merge`, and `computeIfAbsent` replace the `if (map.get(k) == null)` dance. Use them. A key's `hashCode` and `equals` must agree. Mutating an object after using it as a key makes the entry unreachable. ### TreeMap Sorted keys, plus navigation methods that `HashMap` does not have. ```java TreeMap tm = new TreeMap<>(); // ascending TreeMap tm = new TreeMap<>(Collections.reverseOrder()); tm.put(key, value); tm.get(key); tm.getOrDefault(key, 0); tm.remove(key); tm.firstKey(); tm.lastKey(); tm.firstEntry(); tm.lastEntry(); tm.pollFirstEntry(); tm.pollLastEntry(); tm.floorKey(k); // greatest key <= k tm.ceilingKey(k); // smallest key >= k tm.lowerKey(k); // greatest key < k tm.higherKey(k); // smallest key > k tm.headMap(k); tm.tailMap(k); tm.subMap(from, to); ``` ### Iterating a map ```java for (Map.Entry e : map.entrySet()) { String key = e.getKey(); int value = e.getValue(); } for (String key : map.keySet()) { } for (int value : map.values()) { } map.forEach((k, v) -> System.out.println(k + " " + v)); List keys = new ArrayList<>(map.keySet()); List values = new ArrayList<>(map.values()); ``` Removing while looping throws `ConcurrentModificationException`. Remove through the iterator instead. ```java Iterator> it = map.entrySet().iterator(); while (it.hasNext()) { if (it.next().getValue() == 0) it.remove(); } ``` ## Set ### HashSet ```java Set set = new HashSet<>(); Set set = new HashSet<>(list); // dedupes the list set.add(10); // false if already present set.contains(10); set.remove(10); set.size(); set.isEmpty(); set.clear(); set.addAll(other); // union set.retainAll(other); // intersection set.removeAll(other); // difference ``` `LinkedHashSet` is the same with insertion order preserved. ### TreeSet Sorted, with the same navigation methods as `TreeMap`. ```java TreeSet ts = new TreeSet<>(); // ascending TreeSet ts = new TreeSet<>((a, b) -> b - a); // descending ts.add(10); ts.contains(10); ts.remove(10); ts.first(); ts.last(); ts.pollFirst(); ts.pollLast(); ts.floor(k); ts.ceiling(k); ts.lower(k); ts.higher(k); ts.headSet(k); ts.tailSet(k); ts.subSet(from, to); ``` ## Immutable factories Java 9 added `of` factories to `List`, `Set` and `Map`. They build a small collection in one expression, and the result cannot be changed afterwards. ```java List list = List.of("a", "b", "c"); Set set = Set.of(1, 2, 3); Map map = Map.of("a", 1, "b", 2); // Map.of tops out at 10 pairs, so past that use entries Map bigger = Map.ofEntries( Map.entry("a", 1), Map.entry("b", 2) ); // unmodifiable snapshot of a collection you were handed List snapshot = List.copyOf(other); ``` Four things bite here. Every mutator throws `UnsupportedOperationException`, not only `add` and `remove`. That includes `set`, `sort`, `clear` and `removeIf`. `null` is rejected everywhere: as an element, as a key, as a value, and even as the argument to `contains`. `List.of("a", null)` throws `NullPointerException` at construction rather than later. Duplicates are an error, not a silent merge. `Set.of(1, 1)` and a `Map.of` with a repeated key both throw `IllegalArgumentException`. `List.of` keeps insertion order, but the iteration order of `Set.of` and `Map.of` is unspecified and deliberately varies between JVM runs. Never write code, or a test, that depends on it. When you want a literal to start from and then edit, wrap it: ```java List editable = new ArrayList<>(List.of("a", "b")); ``` The three one-line ways to build a list differ more than they look: | | `List.of(...)` | `Arrays.asList(...)` | `new ArrayList<>(...)` | | --------------- | --------------- | ------------------------------------ | ---------------------- | | Size | Fixed | Fixed | Grows | | `set(i, v)` | Throws | Allowed, writes through to the array | Allowed | | `add`, `remove` | Throws | Throws | Allowed | | `null` elements | Rejected | Allowed | Allowed | | Backed by | Its own storage | The array you passed | A copy | ## Sorting and comparators ```java Collections.sort(list); // natural order Collections.sort(list, Collections.reverseOrder()); list.sort(Comparator.naturalOrder()); list.sort(Comparator.reverseOrder()); // By a field people.sort(Comparator.comparing(Person::getName)); people.sort(Comparator.comparingInt(Person::getAge)); // Descending, then a tie breaker people.sort(Comparator.comparingInt(Person::getAge).reversed() .thenComparing(Person::getName)); Collections.reverse(list); Collections.shuffle(list); Collections.max(list); Collections.min(list); Collections.frequency(list, item); Collections.swap(list, i, j); ``` `Comparable` lives on the class through `compareTo`, so it defines one natural order. `Comparator` is passed in at the call site, so you can have as many orders as you need. Subtraction comparators like `(a, b) -> a - b` overflow when the values can be near `Integer.MIN_VALUE` or `Integer.MAX_VALUE`. `Integer.compare(a, b)` is always safe.