Reference

Java Collections Framework

The complete reference for Java's Collections Framework — every interface, every implementation, complexity guarantees, and the decision framework for choosing the right collection for any situation.

Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.

Section One · Overview

What Is the Java Collections Framework?

The Java Collections Framework (JCF) is a unified architecture for representing and manipulating groups of objects — arrays, lists, sets, queues, and maps — through a consistent set of interfaces, implementations, and algorithms introduced in Java 2 (1998) and refined through every subsequent release. Before the JCF, Java developers used arrays, Vector, Hashtable, and ad-hoc data structures with no common interface — code written for one collection could not be reused with another. The JCF solved this by defining a hierarchy of interfaces (Collection, List, Set, Queue, Deque, Map) that describe behaviour independently of implementation, so code written against List<T> works with ArrayList, LinkedList, or any custom implementation without modification. Understanding the JCF means understanding two things: the interfaces (what each collection promises) and the implementations (how each promise is kept, and at what cost).

Every collection in the JCF is parameterised by a type — List<String>, Map<Integer, User>, Set<Long> — enforcing type safety at compile time and eliminating the ClassCastException errors that plagued pre-generics Java. The collections do not store primitive types directly: int becomes Integer, double becomes Double, boolean becomes Boolean — autoboxing handles the conversion automatically but carries a real performance cost for numeric-heavy code. For primitive collections with no boxing overhead, consider Eclipse Collections, Trove, or the primitive streams API.

Interfaces

What it promises

The contract a collection honours. Code against the interface, not the implementation — List<T> not ArrayList<T>. This lets you swap implementations without changing calling code.

Collection, List, Set, Queue, Deque, Map
Each defines the operations and their expected behaviour
Documented complexity is part of the contract

Implementations

How the promise is kept

The concrete class that stores your data. Different implementations honour the same interface with different performance trade-offs — ArrayList and LinkedList both implement List but differ by O(1) vs O(n) for index access.

ArrayList, LinkedList, ArrayDeque, HashSet, TreeSet
HashMap, LinkedHashMap, TreeMap, PriorityQueue
Each trades one operation's cost for another's

Algorithms

What the framework provides

Static utility methods in Collections and Arrays that operate on any collection — sorting, searching, shuffling, frequency counting, unmodifiable wrappers, and synchronized wrappers.

Collections.sort(), binarySearch(), shuffle(), reverse()
Collections.unmodifiableList(), synchronizedMap()
Arrays.asList(), Arrays.copyOf(), Arrays.fill()

Always declare the interface, never the implementation: List<String> list = new ArrayList<>() — not ArrayList<String> list = new ArrayList<>(). Declaring the interface means you can swap to LinkedList, CopyOnWriteArrayList, or Collections.unmodifiableList() by changing one line. The implementation is a detail; the interface is the contract.

Section Two · Architecture

The Interface Hierarchy

The JCF interfaces form two separate trees rooted at Collection and Map — Map is deliberately excluded from Collection because a map stores pairs, not individual elements, and forcing it into the same hierarchy would have required awkward compromises. Every concrete class in the JCF implements one or more of these interfaces, and understanding the hierarchy tells you immediately which operations any class supports — if it implements Queue, it has offer() and poll(); if it implements SortedMap, it has floorKey() and ceilingKey(). The hierarchy also determines interoperability: a method that accepts Collection<T> works with any List, Set, or Queue — the interface is the compatibility surface.

JCF Interface and Implementation Hierarchy

Interface	Extends	Key Contract	Notable Implementations
`Iterable<E>`	—	Provides `iterator()`	All collections
`Collection<E>`	Iterable	add, remove, contains, size	—
`List<E>`	Collection	Ordered, indexed, duplicates allowed	ArrayList, LinkedList
`Set<E>`	Collection	No duplicates	HashSet, TreeSet
`SortedSet<E>`	Set	Sorted order, first/last	TreeSet
`NavigableSet<E>`	SortedSet	floor, ceiling, higher, lower	TreeSet
`Queue<E>`	Collection	FIFO, offer/poll/peek	ArrayDeque, PriorityQueue
`Deque<E>`	Queue	Both-ends access	ArrayDeque, LinkedList
`Map<K,V>`	—	Key→value, unique keys	HashMap, TreeMap
`SortedMap<K,V>`	Map	Sorted keys, firstKey/lastKey	TreeMap
`NavigableMap<K,V>`	SortedMap	floorKey, ceilingKey	TreeMap

NavigableSet and NavigableMap are where TreeSet/TreeMap's power lives: Most developers know TreeSet and TreeMap are “sorted versions” but miss the NavigableSet/NavigableMap methods that make them powerful: floor(e) finds the greatest element ≤ e, ceiling(e) finds the smallest ≥ e, subSet(from, to) returns a range view, and descendingSet() reverses the order. These operations are O(log n) and have no equivalent in HashMap or HashSet.

Section Three · Interfaces

Core Interfaces — What Each Promises

Each JCF interface defines a behavioural contract — a set of operations with specified semantics — that every implementation must honour, regardless of how those operations are performed internally. The key to using the JCF effectively is knowing that List has get(index) and that the contract specifies O(1) for ArrayList and O(n) for LinkedList — implementation-dependent complexity is documented in the Javadoc and is part of the design.

Collection<E> — The Root of All Collections

The most general collection interface — defines the minimum operations every collection must support regardless of ordering, uniqueness, or access pattern.

Java — Collection<E> core methods

// Core Collection<E> methods — available on every List, Set, Queue
Collection<String> c = new ArrayList<>();

c.add("hello");           // O(?) — depends on implementation
c.remove("hello");        // O(?) — depends on implementation
c.contains("hello");      // O(?) — depends on implementation
c.size();                  // O(1) — all implementations
c.isEmpty();               // O(1) — all implementations
c.clear();                  // O(n) — all implementations
c.toArray();               // O(n) — copies to Object[]
c.addAll(otherCollection); // O(k) where k = other.size()
c.iterator();              // O(1) — returns Iterator<E>
      

Collection has no get() — that is List's contribution: The root Collection interface intentionally has no random access method. get(index) belongs to List because Sets and Queues have no concept of positional access. This is why code that accepts Collection<T> cannot call get() — if you need positional access, require List<T> in your method signature instead.

List<E> — Ordered, Indexed, Duplicates Allowed

An ordered sequence where elements are accessible by integer index, duplicates are permitted, and insertion order is preserved.

Java — List<E> operations

List<String> list = new ArrayList<>();

list.add("a");                  // append — O(1) amort
list.add(0, "b");              // insert at index — O(n)
list.get(1);                    // index access — O(1) ArrayList
list.set(1, "c");              // replace at index — O(1) ArrayList
list.remove(0);               // remove by index — O(n) shift
list.indexOf("c");            // first occurrence — O(n)
list.subList(0, 2);           // range view — O(1) ArrayList
list.listIterator();           // bidirectional iterator
Collections.sort(list);        // sort in place — O(n log n)
      

subList() is a view — mutations propagate both ways: list.subList(1, 3) returns a view backed by the original list — modifications to the subList modify the original, and structural modifications to the original (add/remove outside the subList range) invalidate the subList with a ConcurrentModificationException. If you need an independent copy, wrap with new ArrayList<>(list.subList(1,3)).

Set<E> — No Duplicates, Membership Testing

A collection that contains no duplicate elements — add() returns false and does not insert if the element already exists.

Java — Set<E> operations and set algebra

Set<String> set = new HashSet<>();

set.add("apple");             // O(1) avg — returns true (added)
set.add("apple");             // O(1) avg — returns false (duplicate)
set.contains("apple");        // O(1) avg — the core operation
set.remove("apple");          // O(1) avg
set.size();                    // O(1)

// Set algebra
Set<String> a = new HashSet<>(Arrays.asList("x","y","z"));
Set<String> b = new HashSet<>(Arrays.asList("y","z","w"));
a.retainAll(b);               // intersection: {y, z}
a.addAll(b);                  // union: {x, y, z, w}
a.removeAll(b);               // difference: {x}
      

HashSet uses HashMap internally: HashSet<E> is literally a HashMap<E, PRESENT> where PRESENT is a static dummy Object value. Every Set operation delegates to the backing HashMap — add() calls map.put(), contains() calls map.containsKey(). This means HashSet has identical performance characteristics to HashMap and requires the same correct hashCode() and equals() implementation.

Queue<E> — FIFO Processing Order

A collection designed for holding elements prior to processing, with operations for inserting at the tail and removing from the head.

Java — Queue<E> operations

Queue<Integer> q = new ArrayDeque<>();

// Two versions of each operation: throws vs returns special value
// THROWS on failure:    add()     remove()   element()
// RETURNS null/false:   offer()   poll()     peek()

q.offer(10);                  // enqueue — O(1), returns true/false
q.poll();                     // dequeue — O(1), null if empty
q.peek();                     // front element — O(1), null if empty
q.add(20);                    // enqueue — O(1), throws if full
q.remove();                   // dequeue — O(1), throws if empty
q.element();                  // front — O(1), throws if empty
      

Prefer offer/poll/peek over add/remove/element: The throwing variants (add, remove, element) are designed for queues with a fixed capacity where failure is exceptional. For ArrayDeque — which has no fixed capacity — both variants behave identically except on empty. The non-throwing variants (offer, poll, peek) signal failure through return values and are safer in general use.

Deque<E> — Both Ends, All Roles

A double-ended queue that supports O(1) insertion and removal at both the head and tail — generalising both Stack and Queue.

Java — Deque<E> as Stack, Queue, and both-ends

Deque<String> deque = new ArrayDeque<>();

// As a Stack (LIFO):
deque.push("first");           // addFirst() — O(1)
deque.pop();                    // removeFirst() — O(1)
deque.peek();                   // peekFirst() — O(1)

// As a Queue (FIFO):
deque.offer("first");          // addLast() — O(1)
deque.poll();                   // removeFirst() — O(1)

// Both ends explicitly:
deque.addFirst("head");        // O(1)
deque.addLast("tail");         // O(1)
deque.removeFirst();           // O(1)
deque.removeLast();            // O(1)
deque.peekFirst();             // O(1)
deque.peekLast();              // O(1)
      

ArrayDeque replaces both Stack and LinkedList-as-queue: The legacy Stack class is synchronized on every operation — overhead you never want in single-threaded code. LinkedList-as-queue allocates a node object per element — pointer overhead and GC pressure. ArrayDeque has no synchronization, no per-element allocation, and better cache performance — the correct choice for all LIFO and FIFO use cases.

SortedSet & NavigableSet — Ordered Set with Range Power

A Set that maintains elements in a defined sorted order and provides efficient range, floor, and ceiling operations not available in plain Set.

Java — NavigableSet operations

NavigableSet<Integer> ns = new TreeSet<>();
ns.addAll(Arrays.asList(1, 3, 5, 7, 9));

ns.first();                    // 1  — minimum O(log n)
ns.last();                     // 9  — maximum O(log n)
ns.floor(6);                  // 5  — greatest ≤ 6
ns.ceiling(6);                // 7  — smallest ≥ 6
ns.lower(5);                  // 3  — strictly less than 5
ns.higher(5);                 // 7  — strictly greater than 5
ns.subSet(3, true, 7, false);// [3, 7) → {3, 5}
ns.headSet(5, true);          // ≤ 5 → {1, 3, 5}
ns.tailSet(5, false);         // > 5 → {7, 9}
ns.descendingSet();            // reverse view: {9,7,5,3,1}
ns.pollFirst();                // removes + returns 1 — O(log n)
ns.pollLast();                 // removes + returns 9 — O(log n)
      

subSet/headSet/tailSet return live views: Unlike List.subList(), NavigableSet range views are backed by the original TreeSet — mutations propagate in both directions and elements outside the range cannot be added to the view. Adding an element outside the view's range throws IllegalArgumentException. Use these views to efficiently work with a subset without copying.

Map<K,V> — Key-Value Pairs, Unique Keys

Associates keys with values where each key maps to exactly one value — the fundamental lookup structure.

Java — Map<K,V> operations

Map<String, Integer> map = new HashMap<>();

// Core operations
map.put("a", 1);              // O(1) avg — returns old value or null
map.get("a");                 // O(1) avg — null if absent
map.remove("a");              // O(1) avg — returns removed value
map.containsKey("a");         // O(1) avg
map.containsValue(1);         // O(n) — no hash on values

// Java 8+ convenience methods
map.getOrDefault("b", 0);    // O(1) avg — avoids null check
map.putIfAbsent("b", 2);     // O(1) avg — insert only if missing
map.merge("a", 1, Integer::sum); // atomic get+combine+put
map.computeIfAbsent("c", k -> new ArrayList<>());

// Iteration (entrySet is most efficient)
for (Map.Entry<String,Integer> e : map.entrySet()) {
  System.out.println(e.getKey() + "=" + e.getValue());
}
map.forEach((k, v) -> System.out.println(k + "=" + v));
      

Iterate entrySet() — not keySet() then get(): Calling map.get(key) inside a keySet() loop performs a hash lookup on every iteration — O(n) lookups total. Iterating entrySet() gives you the key and value together with no extra lookup. This doubles the performance of map iteration in hot code paths.

Common Mistake: Calling remove() on a collection while iterating it with a for-each loop — this throws ConcurrentModificationException. The correct pattern is to use an explicit Iterator and call iterator.remove(), use collection.removeIf(predicate) (Java 8+), or collect elements to remove in a separate list and call removeAll() after iteration.

Section Four · List

List Implementations

Java provides three general-purpose List implementations and several specialized ones — each with a distinct internal structure that gives different performance profiles for the same List operations. Choosing correctly between ArrayList and LinkedList is the most common JCF decision a developer makes, and getting it wrong silently causes O(n²) performance in code that appears to work correctly.

ArrayList<E> — Resizable Array, the Default List

ArrayList stores elements in a contiguous array that grows by 50% when full (in Java 8+, from capacity n to n + n/2), giving amortized O(1) append and O(1) random access via index formula. Its weakness is the middle — insert or remove at index i requires shifting every element from i to the end, which is O(n) in the worst case and involves a System.arraycopy() call in the JDK implementation. ArrayList is cache-friendly: iterating the backing array hits the CPU cache sequentially, making iteration 3–5× faster than LinkedList in practice even though both are technically O(n).

Java — ArrayList operations

List<Integer> list = new ArrayList<>();           // capacity 10
List<Integer> sized = new ArrayList<>(1000);       // pre-allocate

list.add(42);               // O(1) amortized — append
list.add(0, 99);            // O(n) — shift everything right
list.get(5);                // O(1) — direct array index
list.set(5, 77);             // O(1) — overwrite at index
list.remove(5);             // O(n) — shift everything left
list.contains(42);          // O(n) — linear scan
list.sort(Comparator.naturalOrder()); // O(n log n) TimSort
((ArrayList<Integer>) list).trimToSize();   // releases unused capacity
((ArrayList<Integer>) list).ensureCapacity(500); // pre-allocate
      

Pre-size ArrayList when count is known: new ArrayList<>(expectedSize) pre-allocates the backing array, eliminating all resize copies during population. If you are building a list of n elements from a loop or stream, pre-sizing saves O(log n) resize operations. For very large lists this is a measurable improvement.

LinkedList<E> — Doubly Linked, Implements List and Deque

LinkedList stores elements as a chain of node objects, each holding a value and references to the previous and next nodes — making it a doubly linked list that simultaneously implements both List and Deque. Its advantage is O(1) insertion and deletion at the head and tail (maintained by head and tail references), but it carries two pointer fields per node and one heap allocation per element — significant overhead compared to ArrayList's single array. The most important fact about LinkedList: get(index) is O(n) because it must traverse from the head or tail to the requested index — calling it in a loop is the single most common O(n²) mistake in Java code.

Java — LinkedList operations

LinkedList<String> ll = new LinkedList<>();

ll.addFirst("head");        // O(1) — head pointer update
ll.addLast("tail");         // O(1) — tail pointer update
ll.removeFirst();           // O(1) — head pointer advance
ll.removeLast();            // O(1) — tail pointer retreat
ll.get(5);                  // O(n) — traversal from head or tail
ll.add(3, "middle");        // O(n) — traverse to index 3, then O(1) insert
ll.peekFirst();             // O(1) — read head without removing
ll.peekLast();              // O(1) — read tail without removing

// Using as a Deque (preferred over LinkedList-as-List)
Deque<String> deque = new LinkedList<>();
      

LinkedList is rarely the right choice: In benchmarks, ArrayList outperforms LinkedList for almost every operation because of CPU cache effects — ArrayList's contiguous memory lets the processor prefetch elements, while LinkedList's scattered nodes cause cache misses on every step. Use LinkedList only when you need both List and Deque semantics from one object. For pure stack/queue, ArrayDeque is always faster.

CopyOnWriteArrayList<E> — Thread-Safe, Snapshot Reads

CopyOnWriteArrayList is a thread-safe List where every write operation (add, set, remove) creates a new copy of the entire backing array — writes are O(n) but reads require no locking and are genuinely O(1). Iterators are snapshot-based: they iterate the array as it existed when the iterator was created and never throw ConcurrentModificationException, even if the list is modified during iteration. Use CopyOnWriteArrayList when reads vastly outnumber writes and the list is relatively small — it is the standard choice for listener lists, event handler registries, and shared configuration that changes rarely but is read constantly.

Java — CopyOnWriteArrayList

List<String> cow = new CopyOnWriteArrayList<>();

cow.add("listener1");       // O(n) — copies entire array
cow.get(0);                  // O(1) — no lock needed
cow.contains("listener1");  // O(n) — reads snapshot

// Safe iteration while another thread modifies
for (String s : cow) {        // iterates snapshot — never throws CME
  notifyListener(s);       // if cow.add() happens here — no problem
}
      

Never use CopyOnWriteArrayList for frequently written lists: Each add() on a CopyOnWriteArrayList copies the entire backing array — for a list of 10,000 elements, every add costs 10,000 element copies. At high write frequency this is catastrophically slow. For high-write concurrent lists, use ConcurrentLinkedDeque or a synchronized wrapper with explicit locking strategy.

Operation	ArrayList	LinkedList	CopyOnWriteArrayList
`get(index)`	O(1)	O(n)	O(1)
`add()` at end	O(1)*	O(1)	O(n)
`add(i, val)`	O(n)	O(n)	O(n)
`remove(index)`	O(n)	O(n)	O(n)
`contains()`	O(n)	O(n)	O(n)
`iterator()`	O(1)	O(1)	O(1) snapshot
Thread safe?	No	No	Yes (reads)
Best for	Random access	Head/tail ops	Read-heavy concurrent

* amortized

Section Five · Queue & Deque

Queue and Deque Implementations

Java provides three primary Queue/Deque implementations — ArrayDeque for general-purpose O(1) stack and queue operations, PriorityQueue for priority-ordered processing, and LinkedList which implements Deque but is outperformed by ArrayDeque in every pure queue benchmark. The choice between them is almost always determined by a single question: do you need elements processed in arrival order (ArrayDeque), priority order (PriorityQueue), or do you need to operate on both ends with O(1) access to the minimum or maximum (PriorityQueue does not support arbitrary removal efficiently)?

ArrayDeque<E> — The Workhorse Stack and Queue

ArrayDeque implements Deque using a circular resizable array — the head and tail indices advance modulo capacity, giving O(1) amortized operations at both ends with no per-element allocation. It is the replacement for both the legacy Stack class (which is synchronized) and for using LinkedList as a queue (which wastes memory on node objects). ArrayDeque does not permit null elements — attempting to add null throws NullPointerException, which distinguishes it from LinkedList that does permit nulls.

Java — ArrayDeque as Stack, Queue, and Deque

// As a Stack (LIFO)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.push(3);
stack.pop();                   // 3 — LIFO
stack.peek();                  // 2 — top without removing

// As a Queue (FIFO)
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2); queue.offer(3);
queue.poll();                  // 1 — FIFO
queue.peek();                  // 2 — front without removing

// As a true Deque
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("a");  deque.addLast("b");
deque.peekFirst();            // "a"
deque.peekLast();             // "b"
deque.pollFirst();            // "a" — null if empty
deque.pollLast();             // "b" — null if empty
      

Declare as Queue<T> or Deque<T> — not ArrayDeque<T>: Declaring Queue<T> queue = new ArrayDeque<>() prevents callers from using addFirst() or other deque-specific methods that would violate FIFO semantics. The interface declaration is your enforcement mechanism — use it. Declare Deque<T> only when you genuinely need both-ends access.

PriorityQueue<E> — Min-Heap, Priority-Ordered Processing

PriorityQueue implements Queue using a binary min-heap — elements are stored such that poll() always removes the element with the lowest priority (natural ordering or Comparator-defined), giving O(log n) offer() and poll() and O(1) peek(). It is not a sorted collection — iteration order is undefined and does not correspond to priority order; only poll() and peek() respect the heap property. For a max-heap, pass Comparator.reverseOrder() to the constructor — Java provides no built-in MaxPriorityQueue.

Java — PriorityQueue min-heap, max-heap, and top-K

// Min-heap (default — smallest element at head)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5); minHeap.offer(1); minHeap.offer(3);
minHeap.peek();                // 1 — minimum, O(1)
minHeap.poll();                // 1 — removes minimum, O(log n)

// Max-heap (largest element at head)
PriorityQueue<Integer> maxHeap =
  new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(3);
maxHeap.peek();                // 5 — maximum, O(1)

// Top-K pattern — keep K smallest
PriorityQueue<Integer> topK =
  new PriorityQueue<>(3, Comparator.reverseOrder());
for (int n : new int[]{7,2,9,1,5}) {
  topK.offer(n);
  if (topK.size() > 3) topK.poll(); // evict largest
}
// topK contains: {1, 2, 5} — 3 smallest values
      

PriorityQueue does not support O(1) arbitrary remove: remove(element) on PriorityQueue is O(n) — it must scan the heap to find the element before removing it. If you need to update or remove arbitrary elements efficiently, use a TreeSet or maintain a separate boolean[] visited array to mark removed elements as invalid when they reach the head.

Operation	ArrayDeque	PriorityQueue	LinkedList (as Deque)
offer(e) / add(e)	O(1) amort	O(log n)	O(1)
poll() / remove()	O(1)	O(log n)	O(1)
peek() / element()	O(1)	O(1)	O(1)
addFirst(e)	O(1)	—	O(1)
addLast(e)	O(1)	—	O(1)
remove(element)	O(n)	O(n)	O(n)
Ordering	FIFO/LIFO	Priority	FIFO/LIFO
Null elements	No	No	Yes
Thread safe	No	No	No

Section Six · Set

Set Implementations

Java's Set implementations differ along two axes: whether they use hashing (O(1) operations but no order) or a tree structure (O(log n) operations with sorted order), and whether they maintain insertion order (LinkedHashSet) or access order. The correct Set is determined by a single question: do you need sorted order or range operations? If yes, TreeSet. If no, HashSet. If you need insertion-order iteration, LinkedHashSet.

HashSet<E> — O(1) Membership, Backed by HashMap

HashSet is a HashMap where keys are the set elements and values are a shared dummy PRESENT object — every Set operation delegates to the backing HashMap with identical performance characteristics. It offers the best raw performance for membership testing but provides no guarantees about iteration order.

Java — HashSet basics

Set<String> set = new HashSet<>();
set.add("apple");             // O(1) avg
set.contains("apple");        // O(1) avg — the primary operation
set.remove("apple");          // O(1) avg

// Deduplication — fastest way to remove duplicates from a list
List<String> deduped = new ArrayList<>(new HashSet<>(list));
      

HashSet iteration order is not insertion order: Iteration over a HashSet visits elements in an order determined by their hash codes, which changes after resize and is unrelated to insertion order. If your code relies on HashSet iteration producing a consistent order across JVM runs or Java versions, it is subtly broken — use LinkedHashSet instead.

LinkedHashSet<E> — Insertion-Order Set

LinkedHashSet extends HashSet with a doubly linked list running through all elements in insertion order — it combines O(1) average membership operations with predictable, insertion-ordered iteration. The memory overhead is one prev/next pointer pair per element compared to HashSet.

Java — LinkedHashSet ordering

Set<String> linked = new LinkedHashSet<>();
linked.add("c"); linked.add("a"); linked.add("b");
// Iteration: c, a, b — insertion order preserved
linked.contains("a");          // O(1) avg — still hash-backed

// Deduplication preserving order:
List<String> ordered = new ArrayList<>(new LinkedHashSet<>(list));
      

LinkedHashSet is the correct deduplication tool when order matters: new ArrayList<>(new HashSet<>(list)) deduplicates but destroys order. new ArrayList<>(new LinkedHashSet<>(list)) deduplicates and preserves the first-occurrence order of each element. In most deduplication scenarios, order matters — use LinkedHashSet.

TreeSet<E> — Sorted Set, O(log n) Everything

TreeSet stores elements in a red-black tree that maintains natural ordering (or Comparator order), giving O(log n) add, remove, and contains — slower than HashSet but enabling operations impossible in a hash-based set. The NavigableSet methods (floor, ceiling, subSet, headSet, tailSet) are the reason to choose TreeSet — they solve problems that would require sorting a HashSet first.

Java — TreeSet and NavigableSet operations

NavigableSet<Integer> ts = new TreeSet<>();
ts.addAll(Arrays.asList(3,1,4,1,5,9,2,6));
// Iteration: 1,2,3,4,5,6,9 — sorted, deduped

ts.first();                    // 1 — minimum O(log n)
ts.last();                     // 9 — maximum O(log n)
ts.floor(4);                  // 4 — largest ≤ 4
ts.ceiling(4);                // 4 — smallest ≥ 4
ts.lower(4);                  // 3 — strictly less
ts.higher(4);                 // 5 — strictly greater
ts.subSet(2, true, 6, true); // {2,3,4,5,6}
ts.pollFirst();               // removes + returns 1
      

TreeSet elements must be Comparable or provide a Comparator: Adding an object that does not implement Comparable to a TreeSet with no Comparator throws ClassCastException at runtime — not at compile time. Always either implement Comparable<T> on your element type or pass new TreeSet<>(myComparator). For custom objects, the Comparator approach is safer because it does not force a single natural ordering into the class.

EnumSet<E> — Bit-Vector Set for Enum Types

EnumSet is a highly optimized Set implementation for enum types that stores elements as a bit vector — for enums with ≤ 64 constants, the entire set is represented as a single long, making all operations O(1) with no boxing, no hashing, and no heap allocation per element. It is faster than any other Set for enum types by a significant margin and should always be used instead of HashSet<MyEnum>.

Java — EnumSet operations

enum Day { MON, TUE, WED, THU, FRI, SAT, SUN }

EnumSet<Day> weekdays = EnumSet.range(Day.MON, Day.FRI);
EnumSet<Day> weekend  = EnumSet.of(Day.SAT, Day.SUN);
EnumSet<Day> all      = EnumSet.allOf(Day.class);
EnumSet<Day> none     = EnumSet.noneOf(Day.class);

weekdays.contains(Day.MON);         // O(1) — single bit check
EnumSet.complementOf(weekdays);      // {SAT, SUN} — O(1) bit NOT
      

Always use EnumSet instead of HashSet<MyEnum>: EnumSet operations are implemented as bitwise operations on a long — contains() is a single bit check, add() flips one bit, complementOf() is a bitwise NOT. There is no hashing, no equals(), no heap allocation. For any Set of enum constants, EnumSet is the correct answer — it is never slower and is often 10× faster.

Operation	HashSet	LinkedHashSet	TreeSet	EnumSet
add(e)	O(1) avg	O(1) avg	O(log n)	O(1)
contains(e)	O(1) avg	O(1) avg	O(log n)	O(1)
remove(e)	O(1) avg	O(1) avg	O(log n)	O(1)
Ordered?	No	Insertion	Sorted	Enum order
floor/ceiling	No	No	Yes	No
Null element	Yes (1)	Yes (1)	No	No
Memory	Low	Medium	High	Minimal

Section Seven · Map

Map Implementations

Java's Map implementations form the most important collection family for interview problems and production code — HashMap powers frequency counting and memoization, LinkedHashMap powers LRU caches, TreeMap powers range queries, and ConcurrentHashMap powers shared state in concurrent systems. The decision between them requires knowing two things: whether you need ordering and whether the map is shared between threads.

HashMap<K,V> — O(1) Average, the Default Map

HashMap stores key-value pairs in a bucket array where the bucket index is computed from the key's hash code — O(1) average for get, put, and remove with no ordering of keys or iteration guarantees. Internal capacity starts at 16 and doubles when the number of entries exceeds capacity × loadFactor (default 0.75), with all entries rehashed to new positions in the larger array. In Java 8+, bucket chains longer than 8 entries are treeified to a red-black tree, capping worst-case single-bucket lookup at O(log n) instead of O(n).

Java — HashMap patterns

Map<String, Integer> map = new HashMap<>();

// Frequency counting — the most common HashMap pattern
for (String word : words) {
  map.merge(word, 1, Integer::sum);  // O(1) avg
}

// Grouping — second most common pattern
Map<String, List<String>> groups = new HashMap<>();
for (String s : words) {
  groups.computeIfAbsent(key(s), k -> new ArrayList<>()).add(s);
}

// Safe get patterns
map.getOrDefault("missing", 0);     // avoids null check
map.putIfAbsent("key", 42);           // insert only if absent
      

merge() and computeIfAbsent() replace 90% of verbose map patterns: The old pattern — if (map.containsKey(k)) map.put(k, map.get(k)+1) else map.put(k, 1) — is three lookups. map.merge(k, 1, Integer::sum) is one atomic operation. computeIfAbsent(k, x -> new ArrayList<>()).add(v) replaces the null-check-then-create-then-put pattern. Learn these two methods and your map code becomes both shorter and correct.

LinkedHashMap<K,V> — Ordered Map, LRU Cache

LinkedHashMap extends HashMap with a doubly linked list threading all entries in insertion order (default) or access order — iteration always visits entries in a predictable, defined order while all hash operations remain O(1) average. Access-order mode (accessOrder=true constructor parameter) moves every accessed entry to the tail of the list, making the head always the least-recently-used entry — this is the structural foundation of an LRU cache. Override removeEldestEntry(Map.Entry) to automatically evict the oldest entry when the map exceeds a size threshold, creating a bounded LRU cache in fewer than 10 lines.

Java — LinkedHashMap insertion order and LRU

// Insertion-order iteration
Map<String, Integer> ordered = new LinkedHashMap<>();
ordered.put("c", 3); ordered.put("a", 1); ordered.put("b", 2);
// forEach visits: c=3, a=1, b=2 — insertion order

// LRU Cache — bounded access-order LinkedHashMap
int CAPACITY = 100;
Map<Integer, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
  @Override
  protected boolean removeEldestEntry(Map.Entry<Integer,String> e) {
      return size() > CAPACITY;     // evict when over limit
  }
};
lru.put(1, "one"); lru.get(1);       // moves key 1 to tail (MRU)
// head is always LRU — evicted first
      

LinkedHashMap is the fastest LRU cache in Java without libraries: The LinkedHashMap LRU pattern above is not thread-safe — wrap with Collections.synchronizedMap() for concurrent access, or use Caffeine for a production-grade cache with expiry, refresh, and statistics. For interview problems, the LinkedHashMap approach is the accepted O(1) solution.

TreeMap<K,V> — Sorted Keys, O(log n) Range Queries

TreeMap stores entries in a red-black tree ordered by key — all operations are O(log n) but the payoff is sorted iteration and a set of range query methods unavailable in any hash-based map. The NavigableMap methods (floorKey, ceilingKey, subMap, headMap, tailMap, firstKey, lastKey, pollFirstEntry, pollLastEntry) make TreeMap the structure for problems involving sorted data, predecessor/successor queries, and range lookups. TreeMap does not permit null keys (because null cannot be compared) but does permit null values.

Java — TreeMap range operations

TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(3,"c"); tm.put(1,"a"); tm.put(5,"e"); tm.put(7,"g");

tm.firstKey();                 // 1 — minimum key O(log n)
tm.lastKey();                  // 7 — maximum key O(log n)
tm.floorKey(4);               // 3 — largest key ≤ 4
tm.ceilingKey(4);             // 5 — smallest key ≥ 4
tm.lowerKey(5);               // 3 — strictly less than 5
tm.higherKey(5);              // 7 — strictly greater than 5
tm.subMap(2, true, 6, false);// {3=c, 5=e} — range [2,6)
tm.pollFirstEntry();           // removes + returns {1=a} O(log n)
tm.descendingMap();            // reverse-order view: 7,5,3
      

TreeMap solves the "nearest value" class of problems: Any problem asking for “the largest value that does not exceed X”, “the next scheduled event after time T”, or “all items with keys in range [a,b]” maps directly to floorKey, ceilingKey, or subMap on a TreeMap. These are O(log n) operations — building the TreeMap is O(n log n) but each subsequent query is O(log n).

ConcurrentHashMap<K,V> — Thread-Safe Map, High Concurrency

ConcurrentHashMap divides the bucket array into segments (Java 7) or uses per-bucket CAS operations (Java 8+) so that multiple threads can read and write simultaneously with no full-map locking — reads are always lock-free, writes lock only the affected bucket. It does not permit null keys or null values — attempting to put(null,v) or put(k,null) throws NullPointerException, intentionally: in a concurrent context, null return from get() would be ambiguous (key absent vs key mapped to null). The compute* and merge methods are atomic on ConcurrentHashMap — computeIfAbsent, merge, and compute are single atomic operations with no race condition between the check and the update.

Java — ConcurrentHashMap atomic patterns

ConcurrentHashMap<String, Integer> chm = new ConcurrentHashMap<>();

// Thread-safe frequency counting — atomic merge
chm.merge(word, 1, Integer::sum);     // atomic get+add+put

// Thread-safe grouping — atomic computeIfAbsent
chm.computeIfAbsent(key, k ->
  new ConcurrentLinkedQueue<>()).add(value);

// Atomic conditional update
chm.compute(key, (k, v) -> v == null ? 1 : v + 1); // atomic

// Bulk operations (Java 8+)
chm.forEach(1L, (k, v) -> process(k, v)); // parallelism threshold
chm.reduce(1L, (k, v) -> v, Integer::sum); // parallel reduction
      

ConcurrentHashMap.size() is not guaranteed atomic: size() returns an approximation in ConcurrentHashMap — it sums counts from internal bins and can be stale by the time it returns. For an accurate concurrent count, maintain a separate LongAdder. The mappingCount() method (Java 8+) returns a long and is preferred over size() for large maps.

EnumMap<K extends Enum<K>, V> — Array-Backed, Zero Overhead

EnumMap stores entries in an array indexed by enum ordinal — all operations are O(1) with no hashing, no equals() comparison, and no boxing; it is the fastest possible Map when keys are enum constants. Always use EnumMap instead of HashMap when keys are an enum type.

Java — EnumMap by enum key

enum Status { PENDING, ACTIVE, COMPLETED, CANCELLED }

Map<Status, List<Order>> byStatus =
  new EnumMap<>(Status.class);
for (Status s : Status.values())
  byStatus.put(s, new ArrayList<>());
// All operations: O(1) via array[ordinal] — no hashing
      

EnumMap is faster than HashMap for enum keys by design: EnumMap.get(Status.ACTIVE) is a single array index operation — array[Status.ACTIVE.ordinal()]. There is no hashCode() call, no bucket search, no chain traversal. For any Map whose keys are all values of one enum type, EnumMap is always the correct choice.

Implementation	get/put	Ordered	Null key	Thread-safe	Best for
HashMap	O(1) avg	No	Yes	No	General purpose
LinkedHashMap	O(1) avg	Insertion	Yes	No	LRU cache, ordered output
TreeMap	O(log n)	Sorted	No	No	Range queries, sorted keys
ConcurrentHashMap	O(1) avg	No	No	Yes	Concurrent access
EnumMap	O(1)	Enum order	No	No	Enum-keyed maps
WeakHashMap	O(1) avg	No	Yes	No	Caches without memory leaks
Hashtable	O(1) avg	No	No	Yes	Legacy — never use

⚠ Hashtable is synchronized on every method — use ConcurrentHashMap

Section Eight · Utilities

The Collections Utility Class

java.util.Collections is a class of static utility methods that operate on any Collection or List — sorting, searching, shuffling, reversing, filling, copying, frequency counting, and creating unmodifiable and synchronized wrappers. Every method in Collections accepts a Collection or List interface, so they work with any implementation — sorting an ArrayList uses the same call as sorting a LinkedList.

Sorting and Ordering

Sorts a List in place using TimSort, or provides Comparator utilities for custom ordering.

Java — sorting and ordering helpers

List<Integer> nums = new ArrayList<>(Arrays.asList(3,1,4,1,5));

Collections.sort(nums);                         // O(n log n) ascending
Collections.sort(nums, Comparator.reverseOrder()); // descending
Collections.reverse(nums);                      // O(n) reverse in place
Collections.shuffle(nums);                      // O(n) random permutation
Collections.shuffle(nums, new Random(42L));    // seeded — reproducible
Collections.rotate(nums, 2);                   // O(n) rotate right by 2
Collections.swap(nums, 0, 4);                  // O(1) swap two indices

// Comparator chaining (Java 8+)
List<Person> people = getPeople();
people.sort(Comparator.comparing(Person::getLastName)
                   .thenComparing(Person::getFirstName)
                   .reversed());
      

list.sort() is faster than Collections.sort(): In Java 8+, list.sort(comparator) calls the sort method on the list directly — ArrayList can pass the backing array to Arrays.sort() with no copy. Collections.sort() calls list.sort() internally anyway, so both are equivalent in effect, but list.sort() is clearer.

Binary Search and Extremes

Performs O(log n) binary search on a sorted List, and finds the minimum or maximum element in O(n).

Java — searching helpers

List<Integer> sorted = Arrays.asList(1,3,5,7,9);

int idx = Collections.binarySearch(sorted, 5);  // 2 — O(log n)
int missing = Collections.binarySearch(sorted, 4); // negative: -(insertion point)-1
// insertion point = -missing - 1 = 2 (between index 1 and 2)

Collections.min(sorted);             // 1 — O(n) linear scan
Collections.max(sorted);             // 9 — O(n) linear scan
Collections.frequency(sorted, 5);  // count occurrences — O(n)
Collections.disjoint(a, b);         // true if no elements in common
      

binarySearch requires a sorted list: Collections.binarySearch() returns an undefined negative value if the list is not sorted — it does not throw. Sort first, or use TreeSet/TreeMap if you need sorted storage and O(log n) search without a separate sort step.

Filling, Copying, and Replacing

Fills a list with a single value, copies between lists, or replaces all occurrences of a value.

Java — fill/copy/replace helpers

List<String> list = new ArrayList<>(Arrays.asList("a","b","c"));

Collections.fill(list, "x");                 // ["x","x","x"] — O(n)
Collections.nCopies(5, "hi");               // immutable List of 5 "hi" values
Collections.replaceAll(list, "x", "y"); // O(n)

List<String> dest = new ArrayList<>(Collections.nCopies(3, null));
Collections.copy(dest, list);                 // dest must be at least as large as src
      

nCopies is O(1) creation: Collections.nCopies(n, element) returns an immutable list that stores one shared element reference and returns it for every index. This is useful for pre-sizing destinations for Collections.copy() or initializing tables with a default value.

Unmodifiable Wrappers

Returns a view of a collection that throws UnsupportedOperationException on mutating operations.

Java — wrappers and immutable factory methods

// Unmodifiable wrappers — read-only views
List<String> immutable = Collections.unmodifiableList(mutableList);
Set<String> iSet = Collections.unmodifiableSet(mutableSet);
Map<String,Integer> iMap = Collections.unmodifiableMap(mutableMap);
// immutable.add("x") → UnsupportedOperationException
// Mutating mutableList still changes immutable view — it is a VIEW

// Java 9+ — truly immutable collections (not views)
List.of("a", "b", "c");
Set.of("x", "y");
Map.of("k1", 1, "k2", 2);
Map.copyOf(existingMap);

// Singleton and empty collections
Collections.singleton("only");
Collections.singletonList("x");
Collections.emptyList();
Collections.emptySet();
Collections.emptyMap();
      

List.of() is better than unmodifiableList() for new code: unmodifiableList() returns a read-only view backed by a mutable list, so changes to the source still appear in the view. List.of(), Set.of(), and Map.of() create truly immutable collections with no mutable backing reference.

Synchronized Wrappers

Wraps any collection with synchronized methods — thread-safe access with coarse-grained locking.

Java — synchronized wrappers and iteration lock

// Synchronized wrappers — every method acquires the collection lock
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Map<String,Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

// CRITICAL: manual synchronization required for iteration
synchronized (syncList) {
  for (String s : syncList) {
      process(s);
  }
}
      

Use ConcurrentHashMap instead of synchronizedMap() in most cases: Collections.synchronizedMap() acquires a single map-level lock on every operation, so concurrent reads block each other. ConcurrentHashMap allows concurrent reads and finer-grained write coordination. Prefer it unless you need strict external locking semantics for compound actions.

Section Nine · Generics

Generics and Type Safety

Generics were added in Java 5 to eliminate the ClassCastException errors that occurred when pre-generics collections returned Object and the developer had to cast every element manually. The compiler enforces type safety at compile time — a List<String> cannot hold an Integer, and a method accepting List<Number> cannot be passed a List<Integer> without wildcards — catching errors that would otherwise surface as runtime exceptions in production. Understanding generics beyond the basic <T> syntax — particularly wildcards and bounded type parameters — is essential for writing reusable collection-processing utility methods.

Bounded Type Parameters — <T extends Comparable<T>>

Constrains the type parameter to a subset of types, enabling methods to call specific operations on the type argument.

Java — bounded type parameters

// Without bound — can only call Object methods on T
public static <T> T first(List<T> list) {
  return list.get(0);
}

// With upper bound — T must implement Comparable
public static <T extends Comparable<T>> T max(List<T> list) {
  T result = list.get(0);
  for (T item : list)
      if (item.compareTo(result) > 0) result = item;
  return result;             // works for String, Integer, any Comparable
}

// Multiple bounds
public static <T extends Serializable & Comparable<T>> void save(T item) { ... }
      

T extends — not T implements — even for interfaces: Java generics always use extends for upper bounds, whether T is constrained to a class or an interface — T extends Comparable<T> is correct even though Comparable is an interface. This syntax quirk is common and can be missed under pressure.

Wildcards — ? extends T and ? super T

Wildcards relax type constraints for collection parameters — ? extends T enables reading, ? super T enables writing.

Java — wildcard variance and PECS

// ? extends T (upper bounded) — read from collection, cannot add
public static double sumList(List<? extends Number> list) {
  double sum = 0;
  for (Number n : list) sum += n.doubleValue(); // read OK
  // list.add(1.5); — compile error: cannot add to ? extends
  return sum;
}
sumList(new ArrayList<Integer>());   // works
sumList(new ArrayList<Double>());    // works

// ? super T (lower bounded) — write to collection, reads as Object
public static void addNumbers(List<? super Integer> list) {
  list.add(1); list.add(2); list.add(3); // write OK
  // Integer n = list.get(0); — compile error: reads as Object
}
addNumbers(new ArrayList<Integer>());  // works
addNumbers(new ArrayList<Number>());   // works

// ? (unbounded) — read as Object, cannot add (except null)
public static void printAll(List<?> list) {
  list.forEach(System.out::println);
}
      

PECS — Producer Extends, Consumer Super: If the collection produces elements for your code to read, use ? extends T. If your code produces elements to add to the collection, use ? super T. If you both read and write, use the concrete type T.

Type Erasure — What Generics Are at Runtime

Generics are a compile-time feature — at runtime, type parameters are erased to their bounds (or Object), and all generic instances of the same class share one class object.

Java — type erasure and raw type pitfalls

// At runtime, these are all the same type: ArrayList
List<String>  strings = new ArrayList<>();
List<Integer> ints    = new ArrayList<>();
strings.getClass() == ints.getClass();  // true — both are ArrayList.class

// Raw types — never use these
List raw = new ArrayList();              // compiler warning
raw.add("hello");
raw.add(42);                              // no compile error
String s = (String) raw.get(1);         // ClassCastException at runtime

// Cannot create generic arrays — type erasure prevents this
// List<String>[] array = new ArrayList<String>[10]; — compile error
// Workaround: use List<List<String>> instead

// instanceof cannot check parameterized types
// if (list instanceof List<String>) — compile error
if (list instanceof List<?>) { ... }
      

Never use raw types in new code: Raw types exist only for backward compatibility with pre-Java-5 APIs. In new code, always parameterise your collections: List<String>, not List. Treat every unchecked warning as a real bug risk.

Section Ten · Decision Guide

Choosing the Right Collection

Every collection selection decision reduces to three questions asked in order: what is the shape of the data (sequence, set of unique items, or key-value pairs), what is the dominant operation (access, insert/delete, membership, range query), and are there constraints (thread safety, ordering, fixed capacity, null elements). The flowchart and tables below encode these three questions into a deterministic decision process that covers most real-world cases.

Master decision flowchart — choosing the right Java collection

Situation	Use This	Reason
Need O(1) index access	ArrayList<T>	Array-backed, direct index
Frequent head/tail operations	ArrayDeque<T>	Circular array, O(1) both ends
Priority-ordered processing	PriorityQueue<T>	Binary min-heap
Unique items, fast membership	HashSet<T>	Hash-backed, O(1) average
Unique items, sorted order	TreeSet<T>	Red-black tree
Unique items, insertion order	LinkedHashSet<T>	Hash + linked list
Key-value, O(1) lookup	HashMap<K,V>	Hash-backed, O(1) average
Key-value, sorted keys	TreeMap<K,V>	Red-black tree, NavigableMap
Key-value, LRU cache	LinkedHashMap<K,V>	Access-order linked entries
Key-value, multi-threaded	ConcurrentHashMap	High concurrency, atomic compute
Enum keys (Set or Map)	EnumSet / EnumMap	Bit-vector / ordinal array
Read-heavy concurrent list	CopyOnWriteArrayList	Snapshot reads, no CME
Immutable collection	List.of / Set.of / Map.of	Truly immutable (Java 9+)

Anti-Patterns — What to Never Do

Anti-Pattern	Problem	Correct Alternative
new Stack<>()	Synchronized legacy, exposes Vector API	Deque<T> = new ArrayDeque<>()
new Vector<>()	Fully synchronized legacy class	ArrayList<T> or CopyOnWriteArrayList
new Hashtable<>()	Legacy synchronization, no null support	ConcurrentHashMap or HashMap
Collections.synchronizedMap()	Single lock on every operation	ConcurrentHashMap
LinkedList for random access	get(i) is O(n), loops become O(n²)	ArrayList<T>
HashSet<MyEnum>	Hashing overhead for enum values	EnumSet<MyEnum>
HashMap<MyEnum,V>	Hashing overhead for enum keys	EnumMap<MyEnum, V>
Raw types (List, Map)	No compile-time safety	Always parameterize: List<T>
ArrayList<int>	Invalid: primitives not generic types	int[] or List<Integer>

Section Eleven · Patterns

Common Patterns and Idioms

Most Java collection code falls into a small number of recurring patterns — frequency counting, grouping, deduplication, intersection, union, LRU caching, and priority-based processing. Knowing these patterns by name and implementation means you can recognize them instantly in interview problems and production code.

Frequency Counting

Count how many times each element appears in a collection — the foundation of anagram detection, top-K, and histogram problems.

Java — frequency map idioms

// Method 1: merge() — cleanest
Map<String, Integer> freq = new HashMap<>();
for (String word : words)
  freq.merge(word, 1, Integer::sum);

// Method 2: getOrDefault()
freq.put(word, freq.getOrDefault(word, 0) + 1);

// Method 3: compute()
freq.compute(word, (k, v) -> v == null ? 1 : v + 1);

// Top-K most frequent with min-heap
PriorityQueue<Map.Entry<String,Integer>> pq =
  new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
for (var e : freq.entrySet()) {
  pq.offer(e);
  if (pq.size() > k) pq.poll();
}
      

merge() is the default idiom: It expresses “initialize or increment” as one operation and avoids duplicated lookups.

Grouping by Key

Group elements by a computed key — the core of anagram grouping, bucketing, and classify-then-process pipelines.

Java — grouping with computeIfAbsent and streams

// Group strings by sorted form (anagrams)
Map<String, List<String>> groups = new HashMap<>();
for (String s : words) {
  char[] chars = s.toCharArray();
  Arrays.sort(chars);
  String key = new String(chars);
  groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}

// Stream equivalent
Map<String, List<String>> grouped = words.stream()
  .collect(Collectors.groupingBy(
      s -> { char[] c = s.toCharArray(); Arrays.sort(c); return new String(c); }
  ));
      

computeIfAbsent is the key: It prevents null checks and creates buckets lazily only when needed.

Deduplication Preserving Order

Remove duplicate elements from a list while preserving first-occurrence order.

Java — dedupe with order preserved

List<String> original = Arrays.asList("b","a","c","a","b");

List<String> deduped = new ArrayList<>(new LinkedHashSet<>(original));
// Result: [b, a, c]

List<String> streamDeduped = original.stream().distinct()
  .collect(Collectors.toList());
      

Use LinkedHashSet when order matters: HashSet removes duplicates but does not preserve encounter order.

Set Operations — Intersection, Union, Difference

Compute mathematical set relationships with retainAll, addAll, and removeAll.

Java — set algebra operations

Set<Integer> a = new HashSet<>(Arrays.asList(1,2,3,4));
Set<Integer> b = new HashSet<>(Arrays.asList(3,4,5,6));

Set<Integer> intersection = new HashSet<>(a);
intersection.retainAll(b);            // {3, 4}

Set<Integer> union = new HashSet<>(a);
union.addAll(b);                        // {1,2,3,4,5,6}

Set<Integer> difference = new HashSet<>(a);
difference.removeAll(b);              // {1,2}

Set<Integer> symDiff = new HashSet<>(union);
symDiff.removeAll(intersection);       // {1,2,5,6}
      

These methods mutate: Always operate on a copy when you need the original sets later.

Sliding Window Maximum with Monotonic Deque

Maintain window maximum in O(n) total time using a monotonic decreasing deque.

Java — sliding window max

public static int[] slidingWindowMax(int[] nums, int k) {
  int[] result = new int[nums.length - k + 1];
  Deque<Integer> dq = new ArrayDeque<>();

  for (int i = 0; i < nums.length; i++) {
      while (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
          dq.pollFirst();

      while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
          dq.pollLast();

      dq.addLast(i);
      if (i >= k - 1) result[i - k + 1] = nums[dq.peekFirst()];
  }
  return result;
}
      

Why O(n): Each index enters and leaves the deque at most once.

BFS — Level-Order Graph/Tree Traversal

Explore nodes level by level with a queue to guarantee shortest-path discovery on unweighted graphs.

Java — level-order traversal

public static List<List<Integer>> levelOrder(TreeNode root) {
  List<List<Integer>> result = new ArrayList<>();
  if (root == null) return result;

  Queue<TreeNode> queue = new ArrayDeque<>();
  queue.offer(root);

  while (!queue.isEmpty()) {
      int levelSize = queue.size();
      List<Integer> level = new ArrayList<>();
      for (int i = 0; i < levelSize; i++) {
          TreeNode node = queue.poll();
          level.add(node.val);
          if (node.left != null) queue.offer(node.left);
          if (node.right != null) queue.offer(node.right);
      }
      result.add(level);
  }
  return result;
}
      

Snapshot queue.size(): It defines the current level boundary before adding children.

Top-K Elements with a Bounded Min-Heap

Find K largest elements in O(n log k) time and O(k) space with a bounded priority queue.

Java — top-K via bounded heap

public static List<Integer> topKLargest(int[] nums, int k) {
  PriorityQueue<Integer> heap = new PriorityQueue<>(k);
  for (int n : nums) {
      heap.offer(n);
      if (heap.size() > k) heap.poll();
  }
  return new ArrayList<>(heap);
}

// For top-K smallest, use Comparator.reverseOrder()
      

Use O(n log k), not O(n log n): A bounded heap is better when k is much smaller than n.

Iterative DFS with a Stack

Convert recursive DFS to iterative form using an explicit stack to avoid deep recursion limits.

Java — iterative preorder DFS

public static List<Integer> dfsIterative(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  if (root == null) return result;

  Deque<TreeNode> stack = new ArrayDeque<>();
  stack.push(root);

  while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      result.add(node.val);
      if (node.right != null) stack.push(node.right);
      if (node.left  != null) stack.push(node.left);
  }
  return result;
}
      

Push right before left: Stack order reverses pushes, so this preserves left-first preorder traversal.

Section Twelve · Cheatsheet

Performance Cheatsheet

This is the complete complexity reference for major JCF operations — the page to revisit when choosing data structures under performance pressure. All complexities assume correct hashCode() behavior and reasonable hash distribution; O(1) average means amortized O(1), with O(n) worst-case possible under pathological collisions.

List Implementations

Operation	ArrayList	LinkedList	CopyOnWriteArrayList	int[] (raw)
get(index)	O(1)	O(n)	O(1)	O(1)
set(index, val)	O(1)	O(n)	O(n) copy	O(1)
add() at end	O(1)*	O(1)	O(n) copy	N/A fixed
add(i, val)	O(n)	O(n)	O(n) copy	N/A fixed
remove(index)	O(n)	O(n)	O(n) copy	N/A fixed
remove(object)	O(n)	O(n)	O(n)	N/A
contains(val)	O(n)	O(n)	O(n)	N/A
indexOf(val)	O(n)	O(n)	O(n)	N/A
size()	O(1)	O(1)	O(1)	O(1)
iterator next()	O(1)	O(1)	O(1) snapshot	O(1)
Collections.sort()	O(n log n)	O(n log n)	O(n log n)	Arrays.sort()
subList()	O(1) view	O(1) view	O(1)	N/A
Space per element	1 ref	1 ref + 2 ptrs	1 ref (copy on write)	primitive

* amortized

Queue and Deque Implementations

Operation	ArrayDeque	PriorityQueue	LinkedList	BlockingQueue (avg)
offer(e) / add(e)	O(1)*	O(log n)	O(1)	O(log n) / O(1)
poll() / remove()	O(1)	O(log n)	O(1)	O(log n) / O(1)
peek() / element()	O(1)	O(1)	O(1)	O(1)
addFirst(e)	O(1)	N/A	O(1)	N/A
addLast(e)	O(1)	N/A	O(1)	N/A
removeFirst()	O(1)	N/A	O(1)	N/A
removeLast()	O(1)	N/A	O(1)	N/A
remove(object)	O(n)	O(n)	O(n)	O(n)
contains(e)	O(n)	O(n)	O(n)	O(n)
size()	O(1)	O(1)	O(1)	O(1)

* amortized for resize

Set Implementations

Operation	HashSet	LinkedHashSet	TreeSet	EnumSet
add(e)	O(1)*	O(1)*	O(log n)	O(1)
remove(e)	O(1)*	O(1)*	O(log n)	O(1)
contains(e)	O(1)*	O(1)*	O(log n)	O(1)
first() / last()	N/A	N/A	O(log n)	O(1)
floor(e) / ceiling(e)	N/A	N/A	O(log n)	N/A
subSet(from, to)	N/A	N/A	O(log n) view	N/A
iterator next()	O(1)	O(1)	O(1)	O(1)
size()	O(1)	O(1)	O(1)	O(1)
Iteration order	Undefined	Insertion	Sorted	Enum ordinal

* O(1) average, O(n) worst case with poor hash function

Map Implementations

Operation	HashMap	LinkedHashMap	TreeMap	ConcurrentHashMap	EnumMap
get(key)	O(1)*	O(1)*	O(log n)	O(1)*	O(1)
put(key, val)	O(1)*	O(1)*	O(log n)	O(1)*	O(1)
remove(key)	O(1)*	O(1)*	O(log n)	O(1)*	O(1)
containsKey(key)	O(1)*	O(1)*	O(log n)	O(1)*	O(1)
containsValue(val)	O(n)	O(n)	O(n)	O(n)	O(n)
firstKey() / lastKey()	N/A	N/A	O(log n)	N/A	N/A
floorKey() / ceilingKey()	N/A	N/A	O(log n)	N/A	N/A
subMap(from, to)	N/A	N/A	O(log n) view	N/A	N/A
entrySet iteration	O(n)	O(n) insertion	O(n) sorted	O(n)	O(n) ordinal
size()	O(1)	O(1)	O(1)	approx O(1)	O(1)
Null keys	Yes (1)	Yes (1)	No	No	No
Thread safe	No	No	No	Yes	No

* O(1) average, O(n) worst case when all keys collide. Note: ConcurrentHashMap.size() is approximate under concurrent updates; prefer mappingCount().

The five collections you use most: ArrayList for ordered sequences, HashMap for key-value lookup, HashSet for membership, ArrayDeque for stack/queue, and PriorityQueue for priority processing. Know these deeply before optimizing with niche alternatives.

The three questions before every collection choice: What is the data shape (sequence, unique items, key-value)? Which operation dominates (index access, membership, range query, priority)? What constraints apply (thread safety, ordering, null handling, capacity)? Answering these in order leads to the right collection.

LearningTree

Java Collections Framework | DSA Guide

Java Collections Framework

What Is the Java Collections Framework?

What it promises

How the promise is kept

What the framework provides

The Interface Hierarchy

Core Interfaces — What Each Promises

List Implementations

Queue and Deque Implementations

Set Implementations

Map Implementations

The Collections Utility Class

Generics and Type Safety

Choosing the Right Collection

Common Patterns and Idioms

Performance Cheatsheet