Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › Java

Java Collections Framework

The Collections Framework (java.util) gives ready-made data structures. Interfaces describe what a structure does; classes implement how.

Iterable
 └ Collection
     ├ List   → ArrayList, LinkedList, Vector
     ├ Set    → HashSet, LinkedHashSet, TreeSet
     └ Queue  → PriorityQueue, ArrayDeque (Deque)
Map (separate) → HashMap, LinkedHashMap, TreeMap, Hashtable

Always declare with the interface: List<String> names = new ArrayList<>(); — easy to switch implementations later.

List — ordered, allows duplicates, index access

ArrayList LinkedList
Inside dynamic array doubly linked list
get(i) O(1) O(n)
add at end O(1) amortised O(1)
add/remove in the middle O(n) (shifting) O(1) once you're there, but finding the spot is O(n)
Memory compact extra pointers per node

Use ArrayList almost always.

List<Integer> a = new ArrayList<>(List.of(5, 3, 8));
a.add(1); a.get(0); a.set(0, 9); a.remove(Integer.valueOf(3)); // remove by value, not index!
Collections.sort(a);  a.contains(8);  a.size();

Set — no duplicates

HashSet LinkedHashSet TreeSet
Order none insertion order sorted
add/contains/remove O(1) avg O(1) avg O(log n)
Inside HashMap HashMap + linked list red-black tree

TreeSet extras: first(), last(), floor(x), ceiling(x), headSet, tailSet.

Map — key → value

HashMap LinkedHashMap TreeMap
Order none insertion (or access → LRU cache) sorted by key
get/put O(1) avg O(1) avg O(log n)
null key one allowed one allowed not allowed
Map<String, Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum);     // count words
freq.getOrDefault("java", 0);
freq.putIfAbsent("go", 0);
freq.computeIfAbsent("x", k -> new ArrayList<>());        // map of lists pattern
for (Map.Entry<String, Integer> e : freq.entrySet()) System.out.println(e.getKey() + "=" + e.getValue());

How HashMap works (asked in almost every Java interview)

  1. hashCode() of the key → spread → index = hash & (capacity − 1) into an array of buckets.
  2. Collisions are stored in the same bucket as a linked list; since Java 8, a bucket with more than 8 entries (and capacity ≥ 64) becomes a red-black tree → worst case O(log n) instead of O(n).
  3. Default capacity 16, load factor 0.75: when size > 12 it resizes to double and rehashes.
  4. get finds the bucket, then compares keys with equals.

That's why keys must override both equals and hashCode consistently, and why mutable keys are dangerous (change a field → the key is in the "wrong" bucket).

HashMap vs Hashtable vs ConcurrentHashMap: Hashtable is old and fully synchronized (slow); HashMap isn't thread-safe; ConcurrentHashMap is thread-safe with fine-grained locking — use it for shared maps.

Queue, Deque and PriorityQueue

Deque<Integer> stack = new ArrayDeque<>();   // use instead of Stack
stack.push(1); stack.pop(); stack.peek();

Queue<Integer> q = new ArrayDeque<>();       // FIFO
q.offer(1); q.poll(); q.peek();

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue: offer/poll O(log n), peek O(1). Iterating it does not give sorted order.

Comparable vs Comparator

Comparable Comparator
Method compareTo(T o) inside the class compare(a, b) outside
Orders one natural order as many as you like
record Student(String name, int marks) {}
students.sort(Comparator.comparingInt(Student::marks).reversed().thenComparing(Student::name));

Avoid a - b in comparators — it can overflow; use Integer.compare(a, b).

Iterating and removing safely

Removing inside a for-each loop throws ConcurrentModificationException (fail-fast iterators). Use:

list.removeIf(x -> x % 2 == 0);
// or an explicit Iterator: it.next(); it.remove();

Useful utilities

Collections.sort / reverse / shuffle / max / min / frequency / unmodifiableList, Arrays.asList (fixed size!), List.of (immutable), Arrays.sort (dual-pivot quicksort for primitives, TimSort for objects).

What to use when

Need Use
list with fast index access ArrayList
unique items, fast lookup HashSet
keep insertion order LinkedHashSet / LinkedHashMap
sorted keys, floor/ceiling TreeSet / TreeMap
counting / grouping HashMap
stack or queue ArrayDeque
always get min or max PriorityQueue
shared between threads ConcurrentHashMap, CopyOnWriteArrayList

Interview one-liners

More Java notes