Skip to main content
PreparationZone Logo
PrepZone

The Collections Framework

How List, Set, Queue and Map relate, and how to pick one from the shape of your problem.

Pass checkpoint below

Read these first

Why this matters

  • The framework has dozens of classes, and picking by habit rather than by shape is how an application ends up doing linear scans where a hash lookup would do.
  • Interviews reliably ask you to justify a choice, and "I always use ArrayList" is not a justification.
  • Knowing the interface you should declare — as opposed to the class you instantiate — is what keeps code swappable.

The shape of the framework

Iterable → Collection
Collectionadd, remove, size
ListOrdered, duplicates
SetNo duplicates
QueueEnds-first access
Map — separate branch
Mapput, get, keySet
HashMapNo order
LinkedHashMapInsertion order
TreeMapSorted keys
Map sits outside the Collection branch because it stores pairs rather than single elements. That is why it has no iterator() of its own.

Two roots, not one. Collection covers things holding single elements; Map holds pairs and is deliberately separate because its operations have a different shape.

The four interfaces that matter

  • List — ordered by position, duplicates allowed, indexed access. Use when sequence matters.
  • Set — no duplicates, usually no positional access. Use when membership is the question.
  • Queue / Deque — ordered for processing, with access at the ends. Use for pipelines, buffers and stacks.
  • Map — unique keys mapped to values. Use when you look things up by something other than position.

Choosing, in four questions

AspectWhat you needReach for
An ordered list, mostly read by indexArrayListO(1) indexed access, cache-friendly
Heavy insertion and removal at the endsArrayDequeFaster than LinkedList in practice
Uniqueness, order irrelevantHashSetO(1) membership test
Uniqueness, insertion order keptLinkedHashSetPredictable iteration
Uniqueness, sortedTreeSetO(log n), plus range queries
Key-value lookupHashMapO(1) average get and put
Key-value, sorted keysTreeMapO(log n), navigable
Key-value across threadsConcurrentHashMapConcurrent reads, segmented writes
Highest-priority item firstPriorityQueueA binary heap, O(log n) insert
  • An ordered list, mostly read by index

    What you needArrayList
    Reach forO(1) indexed access, cache-friendly
  • Heavy insertion and removal at the ends

    What you needArrayDeque
    Reach forFaster than LinkedList in practice
  • Uniqueness, order irrelevant

    What you needHashSet
    Reach forO(1) membership test
  • Uniqueness, insertion order kept

    What you needLinkedHashSet
    Reach forPredictable iteration
  • Uniqueness, sorted

    What you needTreeSet
    Reach forO(log n), plus range queries
  • Key-value lookup

    What you needHashMap
    Reach forO(1) average get and put
  • Key-value, sorted keys

    What you needTreeMap
    Reach forO(log n), navigable
  • Key-value across threads

    What you needConcurrentHashMap
    Reach forConcurrent reads, segmented writes
  • Highest-priority item first

    What you needPriorityQueue
    Reach forA binary heap, O(log n) insert

These nine cover the overwhelming majority of real code.

Cost at a glance

The operation that dominates your code is the one to optimise for.

AspectOperationCost by implementation
get by indexArrayList O(1)LinkedList O(n)
add at endArrayList amortised O(1)LinkedList O(1)
add or remove at frontArrayList O(n)ArrayDeque O(1)
containsArrayList O(n)HashSet O(1), TreeSet O(log n)
get by keyHashMap O(1) averageTreeMap O(log n)
iterate in sorted orderTreeMap O(n), freeHashMap requires sorting first
  • get by index

    OperationArrayList O(1)
    Cost by implementationLinkedList O(n)
  • add at end

    OperationArrayList amortised O(1)
    Cost by implementationLinkedList O(1)
  • add or remove at front

    OperationArrayList O(n)
    Cost by implementationArrayDeque O(1)
  • contains

    OperationArrayList O(n)
    Cost by implementationHashSet O(1), TreeSet O(log n)
  • get by key

    OperationHashMap O(1) average
    Cost by implementationTreeMap O(log n)
  • iterate in sorted order

    OperationTreeMap O(n), free
    Cost by implementationHashMap requires sorting first

ArrayList's amortised O(1) append hides an occasional O(n) array copy when it grows.

The rest of this guide is part of Pro

Free covers every fresher guide in full. Pro unlocks Senior, Staff and Architect guides across every track.

Still to come · 6 sections

  • Declare the interface, instantiate the class
  • Immutable and unmodifiable collections
  • Null tolerance differs
  • Methods on the interfaces themselves
  • Legacy classes to avoid
  • Common misreadings

Test yourself

Answer these before moving on — recall is what makes it stick.