skip to content

Distinguish the List, Set, Queue, and Map interfaces in the Java Collections Framework. Which is not a Collection, and why?

level: juniorimportance: must knowfreq 80%

answer

  1. List = order + index, duplicates typically allowed
  2. Set = uniqueness (no two equal elements)
  3. Queue = processing order (FIFO/priority)
  4. Map = key->value pairs, NOT a Collection
  5. Map views: keySet / values / entrySet

basics

~20 s

List is an ordered, indexed sequence that typically allows duplicates. Set holds no duplicates. Queue orders elements for processing, usually FIFO. Map stores key-value pairs and is not a Collection: a mere collection of pairs could not look up by key.

solid answer

~50 s

The four core interfaces model different shapes of data. List<E> is an ordered, index-accessible sequence that typically permits duplicates (ArrayList, LinkedList). Set<E> models a mathematical set: no duplicates, typically unordered (HashSet) or ordered (LinkedHashSet/TreeSet). Queue<E> (and Deque) orders elements for processing - usually FIFO, or by priority (PriorityQueue) - with offer/poll/peek. List, Set, and Queue all extend Collection<E> (List through SequencedCollection since JDK 21), so they share bulk operations and are Iterable. Map<K,V> is the odd one out: it stores key->value associations and does NOT extend Collection, by design: the JDK's design FAQ says its only reasonable elements would be key-value pairs, too limited an abstraction to look up or delete by key. You bridge to the Collection world through Map's three views: keySet() (a Set), values() (a Collection), and entrySet() (a Set of Map.Entry).

go deeper

for a junior

Names the four interfaces and their basic purpose (order/uniqueness/processing/key-value) and knows Map is separate.

for a middle

Explains why Map is not a Collection (a mere collection of pairs could not look up by key), the three map views and their exact return types, and picks a sensible concrete class per use case.

for a senior

Discusses ordering/complexity trade-offs across implementations and the live, backing nature of map views (mutations propagate).

for a principal

Reasons about API design: why the framework split Map out, the cost of view-based mutation, and how interface choice shapes a library's public contract and evolution.

## The big picture The **Java Collections Framework (JCF)** is the set of interfaces and classes in `java.util` for storing groups of objects. At the top of the *single-element* side sits **`Collection<E>`** (which extends `Iterable<E>`). Three interfaces extend it - **`List`** (through `SequencedCollection` since JDK 21), **`Set`**, **`Queue`** - each adding a contract. **`Map<K,V>`** lives on its own, *outside* the `Collection` hierarchy. ## List<E> - ordered sequence, duplicates typically allowed A **`List`** is an ordered collection where every element has an **integer index** (position) starting at 0. It typically allows **duplicates**, and `null`s depending on the implementation; the Javadoc calls a list that refuses duplicates rare, not forbidden. It adds positional methods: `get(int)`, `set(int, E)`, `add(int, E)`, `remove(int)`, `indexOf(...)`. - `ArrayList` - backed by a resizable array; fast random access (`get` is O(1)), slower middle inserts. - `LinkedList` - doubly linked nodes; fast head/tail ops, slow random access. Use a List when **order and position matter** or duplicates are valid. ## Set<E> - uniqueness, no duplicates A **`Set`** models a mathematical set: **no duplicate elements** (the contract says no two elements where `e1.equals(e2)`; `HashSet` goes through `hashCode` and then `equals`, while `TreeSet` decides by `compareTo` or its `Comparator`). It adds *no* new instance methods beyond `Collection`, only static factories such as `Set.of` - the contract is the no-duplicates guarantee. - `HashSet` - unordered, O(1) average add/contains, backed by a hash table. - `LinkedHashSet` - preserves insertion order. - `TreeSet` - sorted order (a `NavigableSet`), O(log n), backed by a red-black tree. Use a Set when you need **membership tests** or to **deduplicate**. ## Queue<E> - processing order A **`Queue`** holds elements for **processing**, typically **FIFO** (first-in-first-out). It adds `offer(E)` (add), `poll()` (remove head, returns null if empty), `peek()` (look at head). **`Deque`** (double-ended queue) extends Queue and supports both ends (it's also used as a stack). - `ArrayDeque` - the recommended general-purpose queue/stack. - `PriorityQueue` - orders by natural ordering or a `Comparator` (a heap), not FIFO. - `LinkedList` - also implements Deque. Use a Queue when the **order of consumption** is the point (work queues, BFS, scheduling). ## Map<K,V> - key/value associations (NOT a Collection) A **`Map`** stores **key -> value** pairs with **unique keys**. Core methods: `put(k,v)`, `get(k)`, `remove(k)`, `containsKey`, `containsValue`, plus Java 8 helpers like `getOrDefault`, `putIfAbsent`, `computeIfAbsent`, `merge`. - `HashMap` - unordered, O(1) average. - `LinkedHashMap` - insertion (or access) order. - `TreeMap` - sorted by key. ### Why Map is NOT a Collection `Collection<E>` speaks in terms of **single elements** `E`: `add(E)`, `contains(Object)`, `iterator()`. So what would a map's elements be? The JDK's Collections API Design FAQ answers: "The only reasonable answer is 'Key-value pairs', but this provides a very limited (and not particularly useful) Map abstraction", because you could neither ask what value a key maps to nor delete an entry by key alone. Hence "This was by design": the designers kept `Map` as a **separate interface**. You reach the Collection world through three **views** (live, backed by the map): - `keySet()` -> `Set<K>` - `values()` -> `Collection<V>` (not a Set - values may repeat) - `entrySet()` -> `Set<Map.Entry<K,V>>` ## Decision cheat-sheet - Need **position / duplicates** -> `List`. - Need **uniqueness / membership** -> `Set`. - Need **processing order (FIFO/priority)** -> `Queue`/`Deque`. - Need **lookup by key** -> `Map`.

  • Why does values() return a Collection but keySet() return a Set?
    Keys are unique by definition, so they form a Set. Values can repeat across different keys, so they only form a general Collection.
  • Is List a subtype of Set or vice versa?
    Neither. Both extend Collection independently. They have different contracts (order and position vs uniqueness) and are siblings.

  • Saying Map extends Collection
  • Claiming every Set keeps insertion order (LinkedHashSet does; TreeSet sorts; HashSet promises no order)
  • Thinking values() returns a Set (it's a Collection - values can duplicate)
  • Assuming all Queues are FIFO (PriorityQueue orders by comparator)

Checked against JDK 27. The family tree has carried SequencedCollection, SequencedSet and SequencedMap since JDK 21, so the answer reads the same at JDK 25.

context