AtticCollections
Cheatsheet
Master quick-reference lookup tables for Arrays, Strings, Lists, Maps, Sets, and Queues with return types, parameters, and time complexities
This master cheatsheet provides an instant-lookup reference for Java's primary data structures: Arrays, Strings, Lists, and Maps (along with Sets and Queues). Each section features a standout toolkit table listing exact method signatures, parameters, return types, asymptotic time complexities, and key notes.
Master Quick Navigation
1. Arrays Toolkit
java.util.Arrays methods, binarySearch, copyOf, 2D deep operations, and System.arraycopy
2. Strings & StringBuilder
String manipulation, regex split/join, immutability, and mutable StringBuilder buffer operations
3. Lists Toolkit
ArrayList and LinkedList indexed access, mutation, search, subList, and sorting
4. Maps Toolkit
HashMap lookups, computeIfAbsent, merge, entrySet, and TreeMap navigable range keys
5. Sets & Queues Toolkit
HashSet uniqueness, TreeSet range queries, ArrayDeque stack/queue, and PriorityQueue heaps
6. Master Complexity Matrix
Direct side-by-side comparison of time complexities, ordering, and null permissibility
1. Arrays Methods Toolkit
Methods provided by java.util.Arrays and native Java array runtime operations:
| Method | Parameters | Return Type | Complexity | Description / Notes |
|---|---|---|---|---|
Arrays.sort(arr) | (int[] | double[] | ...) | void | O(n log n) | Dual-Pivot Quicksort on primitive arrays (unstable) |
Arrays.sort(T[] a, Comparator c) | (T[] a, Comparator c) | void | O(n log n) | TimSort on object arrays (stable, adaptive) |
Arrays.parallelSort(arr) | (arr) | void | O(n log n) | Multi-threaded ForkJoinPool sort for arrays > 8192 items |
Arrays.binarySearch(arr, key) | (arr, key) | int | O(log n) | Array must be sorted. Returns index or -(insertion_point) - 1 |
Arrays.fill(arr, val) | (arr, val) | void | O(n) | Assigns val to every element slot |
Arrays.fill(arr, from, to, val) | (arr, int, int, val) | void | O(k) | Fills half-open subrange [from, to) with val |
Arrays.equals(a, b) | (a, b) | boolean | O(n) | Element-by-element equality check |
Arrays.deepEquals(a, b) | (Object[], Object[]) | boolean | O(R * C) | Recursively checks multidimensional array equality |
Arrays.toString(arr) | (arr) | String | O(n) | Formats 1D array as "[e1, e2, ...]"; avoids [I@hash |
Arrays.deepToString(arr) | (Object[]) | String | O(R * C) | Recursively formats nested 2D/3D matrices |
Arrays.copyOf(arr, newLen) | (arr, int) | T[] | O(n) | Returns zero-padded or truncated copy |
Arrays.copyOfRange(arr, from, to) | (arr, int, int) | T[] | O(k) | Slices subrange [from, to) into a new array |
Arrays.mismatch(a, b) | (a, b) | int | O(n) | Index of first differing element, or -1 if identical (Java 9+) |
Arrays.stream(arr) | (arr) | IntStream / Stream<T> | O(1) | Converts primitive or object array to Stream |
Arrays.asList(T... a) | (T... a) | List<T> | O(1) | Fixed-size list backed by original array; cannot add/remove |
System.arraycopy(src, sp, dest, dp, len) | (src, int, dest, int, int) | void | O(k) | JVM native memory copy (memmove); fastest array slice copy |
arr.clone() | () | T[] | O(n) | Deep copy for 1D primitive array; shallow copy for 2D/object array |
2. Strings & StringBuilder Toolkit
String Core Methods (Immutable)
| Method | Parameters | Return Type | Complexity | Description / Notes |
|---|---|---|---|---|
charAt(index) | (int index) | char | O(1) | Returns char at index (throws StringIndexOutOfBoundsException) |
length() | () | int | O(1) | Number of UTF-16 code units |
substring(beginIndex) | (int begin) | String | O(k) | Slices string from begin to end of string |
substring(begin, end) | (int begin, int end) | String | O(k) | Half-open slice [begin, end) |
indexOf(str) | (String str) | int | O(n * m) | First occurrence index, or -1 if absent |
indexOf(ch, fromIndex) | (int ch, int from) | int | O(n) | Searches forward starting at from index |
lastIndexOf(str) | (String str) | int | O(n * m) | Last occurrence index, or -1 if absent |
contains(charSeq) | (CharSequence s) | boolean | O(n * m) | Evaluates indexOf(s.toString()) >= 0 |
startsWith(prefix) | (String prefix) | boolean | O(k) | Tests if string begins with prefix |
endsWith(suffix) | (String suffix) | boolean | O(k) | Tests if string terminates with suffix |
equals(obj) | (Object anObject) | boolean | O(n) | Value-based character comparison (never use == for strings) |
equalsIgnoreCase(str) | (String anotherString) | boolean | O(n) | Case-insensitive character equality |
compareTo(anotherString) | (String anotherString) | int | O(n) | Lexicographical order: < 0, 0, or > 0 |
toLowerCase() / toUpperCase() | () | String | O(n) | Converts case using default locale |
trim() | () | String | O(n) | Strips ASCII whitespace (<= '\u0020') |
strip() | () | String | O(n) | Strips all Unicode whitespace (Java 11+; preferred over trim()) |
split(regex) | (String regex) | String[] | O(n) | Splits around regex match (e.g. split("\\s+")) |
String.join(delim, elems) | (CharSequence, Iterable) | String | O(n) | Joins elements with delimiter: String.join(", ", list) |
replace(target, replacement) | (CharSequence, CharSequence) | String | O(n) | Replaces every literal matching substring |
replaceAll(regex, replacement) | (String regex, String repl) | String | O(n) | Replaces regex matches across string |
toCharArray() | () | char[] | O(n) | Copies string characters into a fresh mutable char[] |
isEmpty() | () | boolean | O(1) | Checks length() == 0 |
isBlank() | () | boolean | O(n) | Returns true if empty or only Unicode whitespace (Java 11+) |
repeat(count) | (int count) | String | O(n * count) | Repeats string count times (Java 11+) |
String.valueOf(data) | (Object | int | char[]) | String | O(n) | Converts any type/primitive to String |
StringBuilder Methods (Mutable Buffer)
| Method | Parameters | Return Type | Complexity | Description / Notes |
|---|---|---|---|---|
append(val) | (String | int | char | ...) | StringBuilder | O(k) amortized | Appends characters to tail; expands internal buffer if full |
insert(offset, val) | (int offset, Object val) | StringBuilder | O(n) | Inserts at offset; shifts subsequent characters right |
delete(start, end) | (int start, int end) | StringBuilder | O(n) | Removes characters in range [start, end) |
deleteCharAt(index) | (int index) | StringBuilder | O(n) | Removes single character at index |
replace(start, end, str) | (int, int, String) | StringBuilder | O(n) | Replaces slice [start, end) with str |
reverse() | () | StringBuilder | O(n) | Reverses characters in-place |
setCharAt(index, ch) | (int index, char ch) | void | O(1) | Mutates single character at index |
charAt(index) | (int index) | char | O(1) | Reads character at index |
setLength(newLength) | (int newLength) | void | O(1) / O(n) | Truncates or pads with null chars (\0) |
toString() | () | String | O(n) | Converts mutable buffer to immutable String |
3. Lists Toolkit (ArrayList, LinkedList)
| Method | Parameters | Return Type | ArrayList | LinkedList | Description / Notes |
|---|---|---|---|---|---|
get(index) | (int index) | E | O(1) | O(n) | Direct index calculation vs sequential pointer traversal |
set(index, e) | (int index, E e) | E | O(1) | O(n) | Overwrites index slot; returns displaced element |
add(e) | (E e) | boolean | O(1) amortized | O(1) | Appends to tail |
add(index, e) | (int index, E e) | void | O(n) | O(n) / O(1) head | Shifts subsequent elements rightward |
remove(index) | (int index) | E | O(n) | O(n) / O(1) head | Shifts remaining elements leftward; returns removed item |
remove(o) | (Object o) | boolean | O(n) | O(n) | Removes first occurrence matching .equals() |
indexOf(o) | (Object o) | int | O(n) | O(n) | First index of element, or -1 if absent |
lastIndexOf(o) | (Object o) | int | O(n) | O(n) | Last index of element, or -1 if absent |
contains(o) | (Object o) | boolean | O(n) | O(n) | Evaluates indexOf(o) >= 0 |
size() | () | int | O(1) | O(1) | Number of elements in the list |
isEmpty() | () | boolean | O(1) | O(1) | Evaluates size() == 0 |
clear() | () | void | O(n) | O(n) | Resets list; sets internal references to null |
subList(from, to) | (int from, int to) | List<E> | O(1) | O(1) | Live backed view [from, to); structural mutations reflect |
sort(comparator) | (Comparator<? super E> c) | void | O(n log n) | O(n log n) | In-place TimSort (Java 8+) |
toArray(T[] a) | (T[] a) | T[] | O(n) | O(n) | Copies to array: list.toArray(new String[0]) |
removeIf(filter) | (Predicate<? super E> f) | boolean | O(n) | O(n) | Removes matching elements without iterator trap |
replaceAll(op) | (UnaryOperator<E> op) | void | O(n) | O(n) | Mutates each element in-place via lambda |
List.of(e...) | (E... elements) | List<E> | O(n) | — | Unmodifiable, non-null list factory (Java 9+) |
4. Maps Toolkit (HashMap, TreeMap)
Key-Value Lookups & Mutators
| Method | Parameters | Return Type | HashMap | TreeMap | Description / Notes |
|---|---|---|---|---|---|
put(key, val) | (K key, V val) | V | O(1) amortized | O(log n) | Inserts mapping; returns old value or null |
get(key) | (Object key) | V | O(1) amortized | O(log n) | Retrieves value, or null if key absent |
getOrDefault(key, defVal) | (Object key, V defVal) | V | O(1) amortized | O(log n) | Returns defVal if key is absent (Java 8+) |
containsKey(key) | (Object key) | boolean | O(1) amortized | O(log n) | Fast hash check / binary search for key |
containsValue(val) | (Object val) | boolean | O(n) | O(n) | Full scan across all values |
remove(key) | (Object key) | V | O(1) amortized | O(log n) | Removes key entry; returns removed value |
remove(key, val) | (Object k, Object v) | boolean | O(1) amortized | O(log n) | Removes only if mapped to exact val |
putIfAbsent(key, val) | (K key, V val) | V | O(1) amortized | O(log n) | Sets value only if key absent or mapped to null |
replace(key, val) | (K key, V val) | V | O(1) amortized | O(log n) | Replaces value only if key is currently present |
keySet() | () | Set<K> | O(1) | O(1) | Live set view of keys (mutating set mutates map) |
values() | () | Collection<V> | O(1) | O(1) | Live collection view of values |
entrySet() | () | Set<Map.Entry<K,V>> | O(1) | O(1) | Live set view of key-value pair entries |
size() | () | int | O(1) | O(1) | Number of key-value mappings |
isEmpty() | () | boolean | O(1) | O(1) | Evaluates size() == 0 |
clear() | () | void | O(n) | O(n) | Empties all table buckets / tree nodes |
Modern Java 8+ Functional & Compute Methods
| Method | Parameters | Return Type | Code Pattern / Production Use Case |
|---|---|---|---|
computeIfAbsent(k, fn) | (K k, Function<K,V> fn) | V | Multi-map grouping: map.computeIfAbsent(id, k -> new ArrayList<>()).add(item) |
computeIfPresent(k, biFn) | (K k, BiFunction<K,V,V> biFn) | V | Conditional update; removes entry if lambda returns null |
compute(k, biFn) | (K k, BiFunction<K,V,V> biFn) | V | Calculates new value using key and current value |
merge(k, v, biFn) | (K k, V v, BiFunction<V,V,V> biFn) | V | Frequency counter: map.merge(word, 1, Integer::sum) |
forEach(biConsumer) | (BiConsumer<? super K, ? super V> action) | void | Clean iteration: map.forEach((k, v) -> System.out.println(k + "=" + v)) |
TreeMap / NavigableMap Sorted Range Methods
| Method | Parameters | Return Type | Complexity | Search Boundary |
|---|---|---|---|---|
firstKey() / lastKey() | () | K | O(log n) | Smallest / largest sorted key |
firstEntry() / lastEntry() | () | Map.Entry<K,V> | O(log n) | Smallest / largest key-value entry (read-only) |
floorKey(key) | (K key) | K | O(log n) | Greatest key <= key (or null) |
ceilingKey(key) | (K key) | K | O(log n) | Smallest key >= key (or null) |
lowerKey(key) | (K key) | K | O(log n) | Strictly greatest key < key (or null) |
higherKey(key) | (K key) | K | O(log n) | Strictly smallest key > key (or null) |
pollFirstEntry() / pollLastEntry() | () | Map.Entry<K,V> | O(log n) | Retrieves and removes min / max entry |
subMap(fromKey, fInc, toKey, tInc) | (K, boolean, K, boolean) | NavigableMap<K,V> | O(1) | Live range sub-view between key bounds |
5. Sets & Queues Toolkit
Set<E> & NavigableSet<E> (HashSet, TreeSet)
| Method | Parameters | Return Type | HashSet | TreeSet | Description / Notes |
|---|---|---|---|---|---|
add(e) | (E e) | boolean | O(1) amortized | O(log n) | Adds element; returns false if already contained |
contains(o) | (Object o) | boolean | O(1) amortized | O(log n) | Checks presence via hashCode/equals or compareTo |
remove(o) | (Object o) | boolean | O(1) amortized | O(log n) | Removes element from set |
first() / last() | () | E | — | O(log n) | Retrieves min / max element in TreeSet |
floor(e) / ceiling(e) | (E e) | E | — | O(log n) | Greatest <= e / Smallest >= e |
lower(e) / higher(e) | (E e) | E | — | O(log n) | Strictly < e / Strictly > e |
pollFirst() / pollLast() | () | E | — | O(log n) | Retrieves and removes min / max element |
Queue<E> & Deque<E> (ArrayDeque, LinkedList, PriorityQueue)
| Operation | Throws Exception | Returns False / Null | Return Type | ArrayDeque | LinkedList | PriorityQueue | Description |
|---|---|---|---|---|---|---|---|
| Enqueue | add(e) | offer(e) | boolean | O(1) amortized | O(1) | O(log n) | Appends element to queue tail |
| Dequeue | remove() | poll() | E | O(1) | O(1) | O(log n) | Removes head element (or null if empty) |
| Examine | element() | peek() | E | O(1) | O(1) | O(1) | Inspects head without removal |
| Stack Push | push(e) | offerFirst(e) | void / boolean | O(1) amortized | O(1) | — | LIFO push to stack top |
| Stack Pop | pop() | pollFirst() | E | O(1) | O(1) | — | LIFO pop from stack top |
| Stack Peek | peek() | peekFirst() | E | O(1) | O(1) | — | LIFO inspect stack top |
6. Master Complexity Profile
| Data Structure | Direct Access | Insert (Head) | Insert (Tail) | Delete (Element) | Contains | Ordering Guaranteed | Null Elements Permitted |
|---|---|---|---|---|---|---|---|
1D Array (T[]) | O(1) | O(n) | O(n) resize | O(n) shift | O(n) / O(log n) sorted | Index order | Yes (objects) |
String | O(1) char | — | — | — | O(n * m) | Immutable sequence | No |
StringBuilder | O(1) char | O(n) shift | O(1) amortized | O(n) shift | O(n * m) | Mutable sequence | Appends "null" |
ArrayList | O(1) | O(n) shift | O(1) amortized | O(n) shift | O(n) | Insertion order | Yes |
LinkedList | O(n) | O(1) | O(1) | O(1) node | O(n) | Insertion order | Yes |
ArrayDeque | O(1) | O(1) amortized | O(1) amortized | O(n) | O(n) | FIFO / LIFO | No (throws NPE) |
PriorityQueue | O(1) peek | O(log n) | O(log n) | O(n) search | O(n) | Min/Max Heap | No (throws NPE) |
HashSet | — | O(1) amortized | O(1) amortized | O(1) amortized | O(1) amortized | Unordered | 1 null allowed |
TreeSet | — | O(log n) | O(log n) | O(log n) | O(log n) | Sorted / Natural | No (throws NPE) |
HashMap | O(1) key | O(1) amortized | O(1) amortized | O(1) amortized | O(1) key | Unordered | 1 null key, any null values |
TreeMap | O(log n) key | O(log n) | O(log n) | O(log n) | O(log n) key | Sorted keys | No null keys |