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 + duplicates + index
  2. Set = uniqueness (equals/hashCode)
  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 sequence that allows duplicates and index access. Set holds unique elements. Queue orders elements for processing (usually FIFO). Map stores key-to-value pairs. Map is not a Collection because it deals with pairs, not single elements.

solid answer

~50 s

The four core interfaces model different shapes of data. List<E> is an ordered, index-accessible sequence that 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>, 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, because a Collection is a container of single elements while a Map is a container of pairs. You bridge to the Collection world through Map's three views: keySet() (a Set), values() (a Collection), and entrySet() (a Set of Map.Entry). Choosing among them is about the access pattern you need: position, uniqueness, processing order, or lookup by key.

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 (pairs vs single elements), 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`**, **`Set`**, **`Queue`** - each adding a contract. **`Map<K,V>`** lives on its own, *outside* the `Collection` hierarchy. ## List<E> - ordered sequence, duplicates allowed A **`List`** is an ordered collection where every element has an **integer index** (position) starting at 0. It allows **duplicates** and `null`s (depending on impl). 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** (uniqueness defined by `equals`/`hashCode`). It adds *no* new methods beyond `Collection` - 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>` is defined as a container of **single elements** `E` - its methods (`add(E)`, `contains(Object)`, `iterator()`) all speak in terms of one element. A `Map` is a container of **pairs**, with two type parameters `K` and `V`. There is no single "element type" that fits the `Collection<E>` contract - what would `add` take, a key, a value, or a pair? So the designers kept `Map` as a **separate interface** rather than forcing a bad fit. 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 (ordering+duplicates vs uniqueness) and are siblings.

saying these in an interview costs you the question

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

context

resolving links…