Getting everything ready for you…

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

0s

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 a List<Integer> removes index 1, not the value 1 — use remove(Integer.valueOf(1)).
  • Comparing Integer objects 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() without hashCode() breaks HashSet/HashMap.
  • Arrays.asList(...) can't grow; List.of(...) can't change at all.
  • Using Stack/Vector/Hashtable — legacy and synchronized; prefer ArrayDeque/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(...));

References