Java Collections Documentation
Every Java collection for DSA and interviews — which one to pick, the methods you use, complexity, comparators and the traps.
Every Java collection you need for DSA and interviews on one page — which class to pick, the methods you'll actually use, their complexity, and the traps. For the concepts with diagrams read Java Collections Framework; for the language itself see the Java docs.
1. The Hierarchy
Iterable
└── Collection
├── List → ArrayList, LinkedList, Vector (legacy), Stack (legacy)
├── Set → HashSet, LinkedHashSet, TreeSet
└── Queue → PriorityQueue, ArrayDeque, LinkedList
└── Deque → ArrayDeque, LinkedList
Map (separate) → HashMap, LinkedHashMap, TreeMap, Hashtable (legacy), ConcurrentHashMap
Program to the interface: List<Integer> a = new ArrayList<>(); — then you can swap the implementation later.
2. Which One to Pick
| Need | Use |
|---|---|
| Resizable array, index access | ArrayList |
| Stack | ArrayDeque (push/pop) — not Stack |
| Queue (FIFO) | ArrayDeque (offer/poll) |
| Min-heap / max-heap | PriorityQueue |
| Unique items, fast lookup | HashSet |
| Unique items in insertion order | LinkedHashSet |
| Sorted unique items, floor/ceiling | TreeSet |
| Key → value, fast | HashMap |
| Key → value in insertion order / LRU cache | LinkedHashMap |
| Sorted keys, range queries | TreeMap |
| Shared between threads | ConcurrentHashMap, CopyOnWriteArrayList |
3. List — ArrayList and LinkedList
List<Integer> a = new ArrayList<>();
a.add(5); a.add(0, 1); // append, insert at index
a.get(0); a.set(0, 9); // read, replace
a.remove(Integer.valueOf(5)); // remove by VALUE
a.remove(0); // remove by INDEX (careful with List<Integer>!)
a.size(); a.isEmpty(); a.contains(9); a.indexOf(9);
Collections.sort(a); a.sort(Comparator.reverseOrder());
List<Integer> fixed = List.of(1, 2, 3); // immutable
List<Integer> copy = new ArrayList<>(fixed); // mutable copy
| Operation | ArrayList | LinkedList |
|---|---|---|
| get(i) | O(1) | O(n) |
| add at end | O(1) amortised | O(1) |
| add/remove in middle | O(n) | O(1) at an iterator, O(n) to reach it |
| Memory | compact | extra node pointers |
ArrayList is the right default almost always.
4. Set — HashSet, LinkedHashSet, TreeSet
Set<String> s = new HashSet<>();
s.add("a"); s.contains("a"); s.remove("a");
TreeSet<Integer> t = new TreeSet<>(List.of(5, 1, 9));
t.first(); t.last(); // 1, 9
t.floor(6); t.ceiling(6); // 5, 9 (<= and >=)
t.lower(5); t.higher(5); // 1, 9 (< and >)
t.headSet(5); t.tailSet(5); // views below / from 5
t.pollFirst(); // remove + return smallest
HashSet operations are O(1) average; TreeSet are O(log n). floor/ceiling return null when nothing qualifies.
5. Map — HashMap, LinkedHashMap, TreeMap
Map<String, Integer> m = new HashMap<>();
m.put("a", 1);
m.get("x"); // null if missing
m.getOrDefault("x", 0);
m.merge("a", 1, Integer::sum); // counting: m[a] += 1
m.computeIfAbsent("g", k -> new ArrayList<>()).add(3); // map of lists
m.putIfAbsent("b", 0);
m.containsKey("a"); m.remove("a");
for (Map.Entry<String, Integer> e : m.entrySet()) System.out.println(e.getKey() + "=" + e.getValue());
TreeMap<Integer, String> tm = new TreeMap<>();
tm.firstKey(); tm.lastKey(); tm.floorKey(10); tm.ceilingKey(10);
tm.headMap(10); tm.tailMap(10, true); tm.subMap(5, 15);
How HashMap works: hashCode() picks a bucket; collisions chain in a list that becomes a red-black tree beyond 8 entries; the table doubles when size > capacity × 0.75. Average O(1), worst O(log n) with tree bins.
LRU cache in a few lines:
class LRU<K, V> extends LinkedHashMap<K, V> {
private final int cap;
LRU(int cap) { super(16, 0.75f, true); this.cap = cap; } // true = access order
@Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > cap; }
}
6. Queue, Deque and Stack
Deque<Integer> st = new ArrayDeque<>(); // as a stack
st.push(1); st.peek(); st.pop();
Queue<Integer> q = new ArrayDeque<>(); // as a queue
q.offer(1); q.peek(); q.poll(); // poll/peek return null when empty
Deque<Integer> dq = new ArrayDeque<>(); // both ends (sliding window)
dq.offerFirst(1); dq.offerLast(2); dq.pollFirst(); dq.peekLast();
add/remove/element throw exceptions when they fail; offer/poll/peek return false/null. ArrayDeque doesn't allow null elements.
7. PriorityQueue (Heap)
PriorityQueue<Integer> minH = new PriorityQueue<>();
PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[0] - y[0]); // Dijkstra: {dist, node}
minH.offer(5); minH.peek(); minH.poll(); minH.size();
offer/poll O(log n), peek O(1). Iterating a PriorityQueue does not give sorted order — poll repeatedly instead. x[0] - y[0] can overflow for huge values; use Integer.compare(x[0], y[0]).
8. Sorting and Comparators
int[] arr = {3, 1, 2};
Arrays.sort(arr); // primitives: dual-pivot quicksort
Integer[] boxed = {3, 1, 2};
Arrays.sort(boxed, Collections.reverseOrder()); // descending needs objects
record Student(String name, int marks) implements Comparable<Student> {
public int compareTo(Student o) { return Integer.compare(marks, o.marks); } // natural order
}
students.sort(Comparator.comparing(Student::marks).reversed() // highest marks first
.thenComparing(Student::name)); // then by name
Comparable = the class's natural order (compareTo). Comparator = any extra order, defined outside.
9. The Collections and Arrays Utilities
Collections.reverse(list); Collections.shuffle(list);
Collections.max(list); Collections.min(list);
Collections.frequency(list, x);
Collections.swap(list, i, j);
Collections.unmodifiableList(list);
Collections.nCopies(5, 0);
Arrays.fill(arr, -1);
Arrays.asList(1, 2, 3); // fixed-size view of an array
Arrays.toString(arr); Arrays.deepToString(grid);
Arrays.binarySearch(arr, key); // sorted array; negative if absent
Arrays.copyOfRange(arr, 1, 3);
int[][] dp = new int[n][m]; for (int[] row : dp) Arrays.fill(row, -1);
10. Iterating Safely
for (int x : list) { } // read only
Iterator<Integer> it = list.iterator();
while (it.hasNext()) if (it.next() % 2 == 0) it.remove(); // safe removal
list.removeIf(x -> x % 2 == 0); // simplest
m.entrySet().removeIf(e -> e.getValue() == 0);
Removing with list.remove() inside a for-each loop throws ConcurrentModificationException (fail-fast iterators).
11. Streams with Collections
List<Integer> evens = nums.stream().filter(x -> x % 2 == 0).toList();
int sum = nums.stream().mapToInt(Integer::intValue).sum();
Map<Character, Long> freq = s.chars().mapToObj(c -> (char) c)
.collect(Collectors.groupingBy(c -> c, Collectors.counting()));
Map<Integer, List<String>> byLength = words.stream().collect(Collectors.groupingBy(String::length));
String joined = names.stream().collect(Collectors.joining(", "));
See Java 8 Features.
12. Thread-Safe Collections
| Class | Use |
|---|---|
ConcurrentHashMap |
Shared map; fine-grained locking, no nulls |
CopyOnWriteArrayList |
Many reads, few writes (listeners) |
BlockingQueue (ArrayBlockingQueue, LinkedBlockingQueue) |
Producer–consumer |
Collections.synchronizedList(...) |
Simple wrapper; lock it yourself while iterating |
13. Common Mistakes
list.remove(1)on aList<Integer>removes index 1, not the value 1 — useremove(Integer.valueOf(1)).- Comparing
Integerobjects with==works only for −128…127 (cache); use.equals(). - Mutable objects as HashMap keys — changing a key's fields after insertion "loses" it.
- Overriding
equals()withouthashCode()breaks HashSet/HashMap. Arrays.asList(...)can't grow;List.of(...)can't change at all.- Using
Stack/Vector/Hashtable— legacy and synchronized; preferArrayDeque/ArrayList/HashMap.
14. Cheat Sheet & References
Pick a collection
index access ............ ArrayList
stack / queue / deque ... ArrayDeque
heap .................... PriorityQueue (reverseOrder() = max-heap)
unique, fast ............ HashSet sorted ... TreeSet
key→value, fast ......... HashMap sorted ... TreeMap
insertion order / LRU ... LinkedHashSet / LinkedHashMap
threads ................. ConcurrentHashMap, CopyOnWriteArrayList
Complexity
ArrayList get O(1) add O(1)* insert/remove middle O(n) contains O(n)
HashMap/Set get/put/contains O(1) avg
TreeMap/Set get/put/floor/ceiling O(log n)
PriorityQueue offer/poll O(log n), peek O(1)
ArrayDeque push/pop/offer/poll O(1)
Must-know methods
map.getOrDefault(k, 0); map.merge(k, 1, Integer::sum);
map.computeIfAbsent(k, x -> new ArrayList<>()).add(v);
treeSet.floor(x); treeSet.ceiling(x); treeMap.floorKey(x);
deque.offerFirst/offerLast/pollFirst/pollLast/peekFirst/peekLast
list.removeIf(...); list.sort(Comparator.comparing(...));