Core Interfaces

The Java Collections Framework defines a hierarchy of interfaces — List, Set, Map, Queue, Deque — each representing a distinct contract for storing and accessing data.

---

1. Definition

What is it?

The Java Collections Framework (JCF) is a unified architecture for representing and manipulating groups of objects. At its core are a set of interfaces that define the contracts — the what, not the how — of different collection types.

Why does it exist?

Before JCF (pre-Java 1.2), Java had only Vector, Stack, Hashtable, and arrays — each with inconsistent APIs. JCF introduced a coherent hierarchy so that:

• Algorithms can be written against interfaces, not concrete classes
• Implementations are interchangeable without breaking callers
• Common operations (iteration, sorting, filtering) work uniformly

Where does it fit?

Main interface hierarchy summary:

• Iterable sits at the top.
• Collection extends Iterable.
• List is the ordered branch and allows duplicates.
• Set is the no-duplicates branch, with SortedSet and NavigableSet variants.
• Queue covers FIFO or priority-oriented access, with Deque as the double-ended variant.
• Map is a separate key-value hierarchy, with SortedMap and NavigableMap as ordered variants.

---

2. Core Concepts

2.1 `Collection` — the root interface

The root of the collection hierarchy (excluding Map). Provides:

• add(E e), remove(Object o), contains(Object o)
• size(), isEmpty(), clear()
• iterator(), forEach(), stream()
• Bulk operations: addAll, removeAll, retainAll, containsAll

2.1.1 Keywords and terms that must be understood precisely here

In this topic, it is not enough to memorize implementation names. The following keywords and concepts must be understood precisely:

• interface — defines a contract, not a concrete storage strategy.
• extends — an interface can extend another interface, for example Collection extends Iterable.
• implements — a concrete class fulfills an interface contract, for example ArrayList implements List.
• Iterable — guarantees that a structure can be traversed with for-each.
• Collection — the common base for most element-based collections, while Map is outside that hierarchy.
• List — order and position are part of the contract.
• Set — uniqueness is part of the contract.
• Map — a key-value association and a separate hierarchy.
• Queue / Deque — express access semantics, not just storage.

That is why in interviews and API design you should always state which word implies which contract, instead of merely saying "this is a collection".

2.2 `List` — ordered, index-accessible

Key additional methods: get(int), set(int, E), add(int, E), remove(int), indexOf(Object), subList(from, to), sort(Comparator).

2.3 `Set` — no duplicates

SortedSet adds: first(), last(), headSet(to), tailSet(from), subSet(from, to). NavigableSet adds: floor(e), ceiling(e), lower(e), higher(e), descendingSet().

2.4 `Queue` — FIFO access

Key implementations: LinkedList, ArrayDeque, PriorityQueue.

2.5 `Deque` — double-ended queue (extends Queue)

Allows insertion/removal at both ends. Also usable as a Stack (LIFO).

Key implementations: ArrayDeque (preferred), LinkedList.

2.6 `Map` — key-value pairs

Map does not extend Collection. Key operations:

• put(K, V), get(K), remove(K), containsKey(K), containsValue(V)
• keySet() → Set<K>, values() → Collection<V>, entrySet() → Set<Map.Entry<K,V>>
• Java 8+: getOrDefault, putIfAbsent, computeIfAbsent, merge, forEach

SortedMap adds: firstKey(), lastKey(), headMap(to), tailMap(from), subMap(from, to).

2.7 Iteration order and traversal guarantees

The interface choice also determines what you can safely assume about iteration.

• List guarantees stable positional traversal order
• HashSet and HashMap do not guarantee iteration order
• LinkedHashSet and LinkedHashMap preserve insertion order
• TreeSet and TreeMap iterate in comparator order
• PriorityQueue returns priority order through poll(), but not through arbitrary iteration

This is especially important in tests, logging, serialization, and UI output.

2.8 Read-only views vs immutable collections

Collections can also differ by mutation contract:

• Collections.unmodifiableList(list) returns a read-only view
• List.of(...) returns an immutable collection
• List.copyOf(...) returns an immutable snapshot copy

These distinctions are part of API design, not just syntax.

---

3. Practical Usage

When to use which interface?

Code to interface, not implementation

// ✅ Program to interface
List<String> names = new ArrayList<>();
Map<String, Integer> scores = new HashMap<>();

// ❌ Over-specifying implementation
ArrayList<String> names = new ArrayList<>();  // loses flexibility

When NOT to use Collections

• Fixed-size numeric data with known dimensions → use primitive arrays
• Concurrent updates with high contention → use java.util.concurrent types directly
• Stream pipeline intermediate results → don't collect prematurely

Quick API design checklist

When exposing collections in an API, ask:

1. Is ordering part of the contract?
2. Are duplicates meaningful?
3. Do callers need index access?
4. Do callers need membership checks?
5. Should the caller be able to mutate the result?

Those answers usually point to the smallest correct interface.

---

4. Code Examples

Basic Example — Interface contracts in action

import java.util.*;

public class InterfaceContracts {
    public static void main(String[] args) {
        // List — order preserved, duplicates allowed
        List<String> list = new ArrayList<>(List.of("banana", "apple", "apple", "cherry"));
        System.out.println(list);              // [banana, apple, apple, cherry]
        System.out.println(list.get(1));       // apple

        // Set — no duplicates, iteration order not guaranteed (HashSet)
        Set<String> set = new HashSet<>(list);
        System.out.println(set.size());        // 3 (apple deduplicated)

        // Queue — FIFO
        Queue<String> queue = new LinkedList<>(List.of("first", "second", "third"));
        System.out.println(queue.poll());      // first
        System.out.println(queue.peek());      // second

        // Deque as stack — LIFO
        Deque<String> stack = new ArrayDeque<>();
        stack.push("a"); stack.push("b"); stack.push("c");
        System.out.println(stack.pop());       // c (LIFO)

        // Map — key-value
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 90); map.put("Bob", 85);
        System.out.println(map.get("Alice"));  // 90
        System.out.println(map.getOrDefault("Charlie", 0)); // 0
    }
}

Advanced Example — Writing generic algorithms against interfaces

public class CollectionUtils {
    // Works with ANY List implementation
    public static <T extends Comparable<T>> T findMax(List<T> list) {
        if (list.isEmpty()) throw new NoSuchElementException();
        T max = list.get(0);
        for (T item : list) {
            if (item.compareTo(max) > 0) max = item;
        }
        return max;
    }

    // Works with ANY Collection
    public static <T> void printAll(Collection<T> collection) {
        collection.forEach(System.out::println);
    }

    // Returns unmodifiable view — callers get List contract only
    public static List<String> getNames() {
        List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie"));
        return Collections.unmodifiableList(names);
    }
}

Common Pitfall — Mutating while iterating

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

// ❌ ConcurrentModificationException!
for (String s : items) {
    if (s.equals("b")) items.remove(s);
}

// ✅ Use Iterator's remove()
Iterator<String> it = items.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove();
}

// ✅ Or use removeIf (Java 8+)
items.removeIf(s -> s.equals("b"));

---

5. Trade-offs

---

6. Common Mistakes

1. Using `List` when uniqueness matters

// ❌ Allows duplicates — bug if you need unique items
List<String> tags = new ArrayList<>();
tags.add("java"); tags.add("java"); // silent duplicate

// ✅ Use Set
Set<String> tags = new HashSet<>();
tags.add("java"); tags.add("java"); // size stays 1

2. Using `Stack` class (legacy)

// ❌ Stack extends Vector — synchronized, legacy, avoid!
Stack<Integer> stack = new Stack<>();

// ✅ Use Deque
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.pop();

3. Ignoring `null` behavior differences

// TreeSet/TreeMap: null throws NullPointerException
TreeSet<String> sorted = new TreeSet<>();
sorted.add(null); // ❌ NullPointerException — can't compare null

// HashSet: allows one null
HashSet<String> hashed = new HashSet<>();
hashed.add(null); // ✅ OK

4. Calling `remove(Object)` vs `remove(int)` on List

List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4));
numbers.remove(1);              // removes by INDEX → [1, 3, 4]
numbers.remove(Integer.valueOf(3)); // removes by VALUE → [1, 4]

---

7. Deep Dive

Interface segregation in API design

Return the narrowest useful type from your methods. If callers only need to iterate, return Iterable<T>. If they need to check membership, return Collection<T>. Only return List if index access is truly needed.

`Iterable` vs `Collection` vs `List`

Iterable → can iterate (for-each)
  Collection → + size, contains, add, remove
    List → + index access, sort

Each step adds overhead (memory, complexity) — choose the minimum contract.

`Collections.unmodifiableXxx` vs `List.of` / `Set.of`

• Collections.unmodifiableList(list) — view of a mutable list; underlying changes are visible!
• List.of(...) (Java 9+) — truly immutable; throws on any mutation attempt
• List.copyOf(collection) (Java 10+) — immutable copy, snapshot semantics

Performance implications of interface choice

Passing a LinkedList to a method that calls get(int) repeatedly is O(n²). Accepting List<T> in your API doesn't guarantee random access — consider accepting RandomAccess marker or documenting requirements.

`SortedSet` and `SortedMap` consistency

The comparator must be consistent with equals: if comparator.compare(a, b) == 0 then a.equals(b) should be true. Otherwise, the Set contract (no duplicates) breaks silently.

Live views are not immutable snapshots

List<String> source = new ArrayList<>(List.of("a", "b"));
List<String> view = Collections.unmodifiableList(source);

source.add("c");
System.out.println(view); // [a, b, c]

This is a read-only wrapper, not a frozen copy.

Narrow return types reduce coupling

If callers only need traversal, returning Iterable<T> can be more honest than returning List<T>. The narrower the contract, the easier it is to change the implementation later.

---

8. Interview Questions

Why does `Map` not extend `Collection`?

Because a map models key-value associations rather than a plain group of elements, so its core operations and semantics are different.

When would you return `Iterable`, `Collection`, or `List`?

Return the narrowest type that still supports the caller’s needs: Iterable for traversal, Collection for size and membership, and List only when ordering plus positional access matter.

What is the practical difference between `Queue` and `Deque`?

Queue models one-ended head/tail processing, while Deque allows efficient operations at both ends and can also replace the legacy stack use case.

Why can a `TreeSet` reject something that looks like a distinct value?

Because uniqueness is defined by ordering equivalence. If the comparator says two elements compare as zero, the set treats them as the same slot.

---

9. Glossary

---

10. Cheatsheet

• 📋 List — ordered, index access, duplicates OK → ArrayList (default)
• 🔑 Set — no duplicates, fast contains → HashSet (default)
• 🗺️ Map — key-value, fast get by key → HashMap (default)
• 📬 Queue — FIFO task processing → ArrayDeque (preferred over LinkedList)
• ↔️ Deque — both ends accessible, also a stack → ArrayDeque
• ⚠️ Stack class is legacy — use ArrayDeque instead
• ✅ Program to interface — List<E> not ArrayList<E> in signatures
• 🔒 Immutable collections → List.of(), Set.of(), Map.of() (Java 9+)
• 🚫 TreeSet/TreeMap reject null keys/elements
• 🔄 Mutate while iterating → use iterator.remove() or removeIf()