Beginner Reading time: ~9 min

Core Interfaces

List, Set, Map, Queue and Deque interfaces

📖 Collections Framework 3 topics
📑 Table of Contents 9
🎼 Games 1 game type

Collections Framework — 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.2 `List` — ordered, index-accessible

Property Details
Order Insertion order preserved
Duplicates ✅ Allowed
Index access ✅ get(int index)
Null elements ✅ Usually allowed
Key implementations ArrayList, LinkedList, CopyOnWriteArrayList

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

Property Details
Order Depends on implementation (none/insertion/sorted)
Duplicates ❌ Not allowed (determined by equals/hashCode)
Index access ❌ No get(int)
Null elements ✅ At most one null
Key implementations HashSet, LinkedHashSet, TreeSet

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

Operation Throws exception Returns special value
Insert add(e) offer(e) → false
Remove head remove() poll() → null
Examine head element() peek() → null

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).

Operation Front Back
Insert addFirst(e) / offerFirst(e) addLast(e) / offerLast(e)
Remove removeFirst() / pollFirst() removeLast() / pollLast()
Examine peekFirst() peekLast()
Stack use push(e) = addFirst pop() = removeFirst

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).

3. Practical Usage

When to use which interface?

Scenario Interface Why
Ordered list of items, index access needed List O(1) positional access
Unique elements, fast membership test Set contains in O(1) (HashSet)
Key → value lookup Map O(1) lookup by key
Task queue / event processing Queue FIFO semantics
Undo/redo stack, browser history Deque Both ends accessible
Sorted elements, range queries SortedSet / SortedMap Natural or custom order

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

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

Interface ⚡ Access Speed đŸ’Ÿ Memory 🔧 Features Use Case
List O(1) index (array), O(n) search Moderate Index, sort, subList Ordered sequences
Set O(1) contains (hash), O(log n) (tree) Low–Moderate Uniqueness Membership test, deduplication
Queue O(1) head operations Low FIFO semantics Task scheduling
Deque O(1) both ends Low Stack + Queue Undo, sliding window
Map O(1) by key (hash), O(log n) (tree) Moderate–High Key-value, merge ops Caching, indexing

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. Senior-level Insights

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.

8. Glossary

Term Definition
JCF Java Collections Framework — the unified hierarchy of collection interfaces and implementations
Contract The behavioral guarantee an interface makes to its callers
RandomAccess Marker interface on ArrayList etc. indicating O(1) index access
FIFO First-In-First-Out — insertion order determines removal order (Queue)
LIFO Last-In-First-Out — most recently added item is removed first (Stack/Deque)
NavigableSet Extension of SortedSet with methods for floor/ceiling/lower/higher queries
Fail-fast iterator Iterator that throws ConcurrentModificationException if the collection is modified during iteration
Structural modification Any change to the size of a collection (add/remove), as opposed to set

9. 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()

🎼 Games

10 questions