Java Collections Framework — Complete Notes

Every list, set, map and queue in Java, explained from the ground up in plain language — then taken all the way down to the internals interviewers actually dig into (especially how HashMap really works).

00. What the Collections Framework actually is

A collection is just "a bunch of objects grouped together." The Collections Framework is Java's built-in, standardised toolbox of these groupings, so you never have to hand-roll a resizable array or a hash table again.

Before the framework existed (Java 1.1), everyone used raw arrays, Vector and Hashtable, and none of them shared a common interface — so code that worked with one couldn't work with another. Java 1.2 introduced a unified design: a small set of interfaces (what a collection can do), many implementations (how it does it), and a couple of utility classes (algorithms like sort and search). Learn the interfaces once and every implementation feels familiar.

01. The hierarchy — how the pieces fit

Get this map in your head and everything else slots into place. Everything below Collection shares the same core methods; only the rules differ.

Iterable
  └── Collection ............. add, remove, size, contains, iterator
        ├── List ............. ordered, index-based, allows duplicates
        │     ├── ArrayList
        │     ├── LinkedList
        │     └── Vector (legacy) → Stack (legacy)
        ├── Set .............. no duplicates
        │     ├── HashSet
        │     │     └── LinkedHashSet
        │     └── TreeSet (implements SortedSet/NavigableSet)
        └── Queue ............ ordered for processing (FIFO-ish)
              ├── ArrayDeque (also a Deque)
              ├── PriorityQueue
              └── LinkedList (also a Queue/Deque)

Map (SEPARATE tree) ......... key → value, no duplicate keys
  ├── HashMap
  │     └── LinkedHashMap
  ├── TreeMap (implements SortedMap/NavigableMap)
  └── Hashtable (legacy)

Iterable sits at the very top — it's the interface that lets a type be used in a for-each loop. Collection adds the bulk operations (add, remove, contains, size). Below that, each interface narrows the contract:

• List — keeps insertion order, indexes elements from 0, allows duplicates.
• Set — refuses duplicates (defined by equals).
• Queue — models "a line to be processed," usually first-in-first-out.
• Deque — a double-ended queue: add/remove at both ends.
• Map — stores pairs; look up a value by its key.

02. List — ArrayList vs LinkedList

A List is an ordered, index-based sequence that allows duplicates. Two implementations matter, and the whole interview is "which one, and why."

ArrayList — a growable array

Internally it's a plain array (Object[]). Because it's contiguous memory, reading list.get(i) is a single jump — O(1). When it fills up, it grows by ~50%: it allocates a bigger array and copies everything over. That copy is occasional, so appending is amortised O(1).

List<String> fruits = new ArrayList<>();
fruits.add("apple");            // append — O(1) amortised
fruits.add("banana");
fruits.add(1, "mango");         // insert at index 1 — shifts the rest, O(n)
fruits.get(0);                  // "apple" — O(1) random access
fruits.set(0, "avocado");       // replace — O(1)
fruits.remove("banana");        // remove by value — O(n) to find + shift
fruits.size();                  // 2
System.out.println(fruits);     // [avocado, mango]

LinkedList — a doubly-linked chain of nodes

Each element is a node holding the value plus pointers to the previous and next node. There's no array, so there's no shifting: inserting or deleting once you're at a node is O(1). But there's no index math either — to reach element #457 you must walk 457 links, so get(i) is O(n).

03. Set — HashSet, LinkedHashSet, TreeSet

A Set is a collection with no duplicates. "Duplicate" means a.equals(b) is true — which is exactly why equals/hashCode matter so much (covered in the OOP notes).

Set<Integer> hash = new HashSet<>(List.of(3, 1, 2, 1));
Set<Integer> linked = new LinkedHashSet<>(List.of(3, 1, 2, 1));
Set<Integer> tree = new TreeSet<>(List.of(3, 1, 2, 1));

System.out.println(hash);    // [1, 2, 3]  — no guaranteed order (looks sorted here by luck)
System.out.println(linked);  // [3, 1, 2]  — the order you inserted
System.out.println(tree);    // [1, 2, 3]  — always sorted ascending

04. Map — and how HashMap really works

A Map stores key → value pairs with unique keys. This is the single most-asked Java topic after OOP, because HashMap's internals touch hashing, equals/hashCode, and data structures all at once.

Map<String, Integer> ages = new HashMap<>();
ages.put("Asha", 30);
ages.put("Ravi", 25);
ages.put("Asha", 31);            // same key → OVERWRITES, not duplicates. Now Asha = 31
ages.get("Asha");                // 31
ages.getOrDefault("Zoe", 0);     // 0 — key absent, returns the default
ages.containsKey("Ravi");        // true
ages.putIfAbsent("Ravi", 99);    // no-op, Ravi already present

// Idiomatic counting / grouping:
Map<String, Integer> count = new HashMap<>();
for (String w : words) count.merge(w, 1, Integer::sum);   // +1 per word
count.computeIfAbsent("list", k -> new ArrayList<>());    // create-on-first-use pattern

for (Map.Entry<String, Integer> e : ages.entrySet())
    System.out.println(e.getKey() + " → " + e.getValue());

Inside HashMap — the part interviewers love

Step by step: what put(key, value) does

1. Call key.hashCode() to get a raw 32-bit number.
2. Spread the bits (Java does h ^ (h >>> 16)) so that even keys with similar hashes land in different buckets. This mixing reduces collisions.
3. Map that to a bucket index with hash & (n - 1), where n is the table length. (This works as a fast modulo because the table length is always a power of two — that's why it is.)
4. Go to that bucket. If it's empty, place the entry. If something's already there — a collision — walk the entries in that bucket comparing with hashCode then equals. If a key equals an existing one, overwrite its value; otherwise append the new entry.

Collisions: linked list, then tree

When many keys land in the same bucket, they're chained together. Historically that chain was a linked list, so a badly-collided bucket degraded lookups to O(n). Since Java 8, once a single bucket holds 8+ entries (TREEIFY_THRESHOLD) and the table is at least 64 slots, that bucket is converted into a balanced red-black tree, bringing worst-case lookup back down to O(log n). If the bucket later shrinks below 6, it turns back into a list.

Resizing (rehashing)

The map tracks a load factor (default 0.75). When the number of entries exceeds capacity × loadFactor — e.g. 12 entries in a 16-slot table — it doubles the table size and redistributes every entry into the new, larger table. This keeps buckets short. Resizing is O(n) when it happens, but it's rare, so put/get stay amortised O(1).

The other Maps

• LinkedHashMap — a HashMap that also threads a linked list through its entries to remember insertion order (or, with a flag, access order — the basis of a simple LRU cache).
• TreeMap — keeps keys sorted (red-black tree), O(log n) operations, and adds navigation like firstKey, floorKey, headMap, subMap.
• Hashtable — legacy, fully synchronized, no null keys/values. For thread-safety today use ConcurrentHashMap instead.

05. Queue, Deque & PriorityQueue

A Queue models a line of items waiting to be processed. A Deque ("deck") is a double-ended queue — push and pop at both ends, so it can act as either a queue (FIFO) or a stack (LIFO).

Deque<Integer> dq = new ArrayDeque<>();

// As a FIFO queue:
dq.offer(1); dq.offer(2);       // add to tail
dq.poll();                      // 1 — remove from head

// As a LIFO stack (use this, NOT the legacy Stack class):
dq.push(10); dq.push(20);       // add to head
dq.pop();                       // 20 — remove from head
dq.peek();                      // 10 — look without removing

PriorityQueue — a heap

A PriorityQueue doesn't return items in insertion order — it returns the smallest (or by your Comparator, the "highest priority") first. It's backed by a binary heap: offer and poll are O(log n), peeking at the top is O(1). It's the go-to for "top-K," scheduling, and Dijkstra-style algorithms.

PriorityQueue<Integer> pq = new PriorityQueue<>();     // min-heap by default
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll();   // 1  (smallest first)
pq.poll();   // 3

// Max-heap: reverse the comparator
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());

06. Iterating — and the fail-fast trap

You'll loop over collections constantly. The one thing that bites everyone is modifying a collection while iterating it.

List<String> names = new ArrayList<>(List.of("a", "b", "c"));

for (String n : names) { ... }                  // for-each (uses an Iterator under the hood)

Iterator<String> it = names.iterator();         // explicit iterator
while (it.hasNext()) {
    String n = it.next();
    if (n.equals("b")) it.remove();             // SAFE removal during iteration
}

names.removeIf(n -> n.startsWith("a"));         // cleanest conditional removal (Java 8+)

07. Comparable vs Comparator — sorting

To sort objects, Java needs to know what "less than" means. Two mechanisms: build the ordering into the class (Comparable), or supply it from outside (Comparator).

• Comparable<T> — implemented by the class itself; defines its one natural ordering via compareTo. Example: String sorts alphabetically, Integer numerically.
• Comparator<T> — a separate object defining an ordering. You can make many (by name, by age, reversed) without touching the class.

class Person implements Comparable<Person> {
    String name; int age;
    // natural ordering: by age
    public int compareTo(Person o) { return Integer.compare(this.age, o.age); }
}

List<Person> people = ...;
Collections.sort(people);                        // uses compareTo (by age)

// External comparators — compose them fluently:
people.sort(Comparator.comparing(p -> p.name));                    // by name
people.sort(Comparator.comparingInt((Person p) -> p.age).reversed());  // oldest first
people.sort(Comparator.comparing((Person p) -> p.name)
                      .thenComparingInt(p -> p.age));               // name, then age

08. Collections & Arrays utility classes

Two helper classes carry the algorithms. Collections (with an "s") operates on collections; Arrays operates on arrays.

Collections.sort(list);
Collections.reverse(list);
Collections.max(list);  Collections.min(list);
Collections.frequency(list, x);
Collections.unmodifiableList(list);        // read-only VIEW (throws on modify)
Collections.synchronizedList(list);        // thread-safe wrapper (coarse locking)

int[] arr = {3, 1, 2};
Arrays.sort(arr);
Arrays.toString(arr);                      // "[1, 2, 3]"
List<Integer> view = Arrays.asList(1, 2, 3);   // FIXED-SIZE list backed by an array

// Immutable factory methods (Java 9+): truly unmodifiable, reject nulls:
List<String> ro = List.of("a", "b");
Map<String, Integer> m = Map.of("a", 1, "b", 2);

09. Complexity cheat sheet

* amortised — occasional resize copies are O(n) but rare.

10. How to choose — a decision guide

11. Gotchas — where Java surprises you

12. Interview Q&A

13. Cheat sheet

• Two trees: Collection (List/Set/Queue) and Map (separate).
• Default picks: ArrayList, HashSet, HashMap, ArrayDeque.
• Need order? LinkedHashSet/LinkedHashMap (insertion) or TreeSet/TreeMap (sorted).
• HashMap: 16 buckets, load factor 0.75, doubles on resize, treeifies buckets at 8.
• Keys & set elements must have correct, immutable equals/hashCode.
• Mutating while iterating? Use Iterator.remove or removeIf, never the collection directly.
• Sorting: Comparable = one natural order in the class; Comparator = many orders from outside.
• Thread-safe map: ConcurrentHashMap, not Hashtable.