Cheat Sheets
Data Structures in Java · Study material
Java Data Structures Cheat Sheet
| Structure / code | Use and cost |
|---|---|
List<T> a = new ArrayList<>(); | dynamic array – get O(1), add amortized O(1) |
Deque<T> st = new ArrayDeque<>(); st.push(x); st.pop(); st.peek(); | stack – O(1) |
Queue<T> q = new ArrayDeque<>(); q.offer(x); q.poll(); q.peek(); | queue – O(1) |
dq.offerFirst(x); dq.offerLast(x); dq.pollFirst(); dq.pollLast(); | deque – O(1) at both ends |
new PriorityQueue<>() / (Comparator.reverseOrder()) | min-heap / max-heap – offer, poll O(log n) |
Map<K, V> m = new HashMap<>(); | hash table – O(1) average |
TreeMap / TreeSet | red-black tree – sorted, O(log n) |
LinkedList | doubly linked list – ends O(1), get(i) O(n) |
static class Node { int val; Node next; } | linked-list node |
static class TreeNode { int key; TreeNode left, right; } | binary-tree node |
Map<V, List<V>> g + g.computeIfAbsent(u, k -> new ArrayList<>()).add(v) | adjacency list |
left = 2*i + 1, right = 2*i + 2, parent = (i - 1) / 2 | heap index arithmetic |
tail = (tail + 1) % capacity | circular-queue wrap-around |