Skip to content
Tutorials Center
My learning

Topics

Lesson 79 of 201 ยท Collections

The Collections Framework

A map of the Java Collections Framework - Collection, List, Set, Queue, Deque, Map and sequenced collections, the main implementations and how to choose one.

Arrays are fast and simple, but they have a fixed size and almost no behavior: no "add", no "contains", no "remove duplicates". Real programs need to grow a list of orders, check whether a username is taken, process jobs in arrival order, or look up a price by product code. The Java Collections Framework is the standard library's answer: a family of interfaces that describe what a collection can do, and a set of well-tuned classes that implement them.

This lesson is the map for the whole chapter. You'll see how the interfaces fit together, what each main implementation is good at, why you should declare variables with interface types, and how to pick the right collection in a few seconds. The following lessons then cover each class in depth, starting with ArrayList.

The big picture

Everything lives in java.util (compact source files import it automatically). The framework has two separate trees: collections, which hold single elements, and maps, which hold key-value pairs.

TEXT
Iterable<E>                         anything you can loop over with for-each
โ””โ”€โ”€ Collection<E>                   a group of elements: add, remove, contains, size
    โ”œโ”€โ”€ SequencedCollection<E>      has a defined order: getFirst, getLast, reversed (Java 21)
    โ”‚   โ”œโ”€โ”€ List<E>                 ordered, indexed, duplicates allowed
    โ”‚   โ”‚     ArrayList, LinkedList
    โ”‚   โ”œโ”€โ”€ Deque<E>                add/remove at both ends (also a Queue)
    โ”‚   โ”‚     ArrayDeque, LinkedList
    โ”‚   โ””โ”€โ”€ SequencedSet<E>         a Set with an order (also a Set)
    โ”‚         LinkedHashSet, and SortedSet -> NavigableSet: TreeSet
    โ”œโ”€โ”€ Set<E>                      no duplicates
    โ”‚     HashSet
    โ””โ”€โ”€ Queue<E>                    elements waiting to be processed
          PriorityQueue, and Deque above

Map<K, V>                           keys mapped to values; NOT a Collection
โ”‚     HashMap
โ””โ”€โ”€ SequencedMap<K, V>              a Map with an order (Java 21)
      LinkedHashMap, and SortedMap -> NavigableMap: TreeMap

A class can implement several interfaces: LinkedList is both a List and a Deque, and TreeSet is a Set, a SequencedSet and a NavigableSet.

The sequenced interfaces arrived in Java 21. Before them, there was no common way to ask "what's the first element?" of a list, a deque and an ordered set. Now they all share getFirst(), getLast(), addFirst(), addLast(), removeFirst(), removeLast() and reversed().

The core interfaces

Each interface promises a different kind of behavior:

Interface Order Duplicates Typical question it answers
List insertion order, by index allowed "What's the 3rd item? Show them in order."
Set none (HashSet), insertion (LinkedHashSet) or sorted (TreeSet) not allowed "Have I seen this before?"
Queue processing order (FIFO or priority) allowed "What's next?"
Deque both ends allowed "Push/pop like a stack, or add at the back and take from the front."
Map none, insertion or sorted, like sets unique keys "What's the value for this key?"
Java One problem, four collection types

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The same data answers four different questions depending on the collection you put it in. Choosing a collection is really choosing which questions are cheap to ask.

What every Collection can do

Collection defines the methods shared by lists, sets and queues. Once you know them, you know a large part of every collection class:

Method What it does
add(e), addAll(other) add elements; return true if the collection changed
remove(o), removeAll(other), removeIf(predicate) remove matching elements
retainAll(other) keep only elements also in other
contains(o), containsAll(other) membership tests (using equals)
size(), isEmpty(), clear() size and emptiness
iterator(), for-each visit each element
stream() process with the Streams API
toArray(String[]::new) copy into an array
Java Shared Collection methods on a list and a set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Notice that add returns false when a set already holds the element. That return value is a cheap "was it new?" test you'll use often.

What elements must provide

Collections find elements by asking the elements themselves:

  • List.contains, indexOf, remove(Object) use equals.
  • Hash-based classes (HashSet, HashMap, LinkedHashSet, LinkedHashMap) use hashCode and then equals. If you override one, override both (The Object Class), and never change a key's fields while it's inside a hash collection (How HashMap Works Inside).
  • Sorted classes (TreeSet, TreeMap, PriorityQueue) use compareTo from Comparable or a Comparator you pass in (Sorting with Comparable and Comparator).

Records, String, the wrapper classes and enums already get all of this right, which is why they make excellent elements and keys.

The main implementations

You'll use a handful of classes for 95% of your work:

Class Implements Backed by Strengths
ArrayList List resizable array fast get(i), fast add at the end; the default list
LinkedList List, Deque doubly linked nodes add/remove at the ends; rarely the best choice (LinkedList)
ArrayDeque Deque circular array the default stack and queue
PriorityQueue Queue binary heap always hands out the smallest (or highest-priority) element
HashSet Set hash table fast contains, no order
LinkedHashSet SequencedSet hash table + linked list fast contains, keeps insertion order
TreeSet NavigableSet red-black tree sorted order, ranges, nearest element
HashMap Map hash table fast lookup by key; the default map
LinkedHashMap SequencedMap hash table + linked list insertion or access order (LRU caches)
TreeMap NavigableMap red-black tree keys in sorted order, range queries

On top of these, java.util.concurrent adds thread-safe versions such as ConcurrentHashMap and CopyOnWriteArrayList (Concurrent Collections), and a few specialized classes (EnumMap, EnumSet, BitSet) are covered in Specialized Collections. Old classes like Vector, Stack and Hashtable still exist but are legacy; don't use them in new code.

Most general-purpose implementations accept null elements (and HashMap a null key), but TreeSet, TreeMap with natural ordering, ArrayDeque, PriorityQueue and the immutable List.of-style collections reject null with a NullPointerException. Avoiding null in collections altogether keeps your code simpler.

Program to interfaces

Declare variables, fields, parameters and return types with the interface type, and mention the implementation class only where you create the object:

Java
List<String> names = new ArrayList<>();          // good
ArrayList<String> names = new ArrayList<>();     // works, but ties you to ArrayList

This has two benefits. Your methods accept any list, not just one class. And you can switch implementations by changing a single line, without touching the code that uses the collection:

Java Swapping the implementation behind an interface

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

addTags and describe work unchanged with all three sets, and all three drop the duplicate "java"; only the iteration order differs. HashSet order depends on hash codes (here maps jumps to second place; don't rely on any particular order), LinkedHashSet keeps insertion order, and TreeSet sorts alphabetically.

Take the most general type that does the job as a parameter: Collection<String> if you only loop and add, List<String> if you need indexes or order. Return the most specific interface callers need, but still an interface.

Modifiable, unmodifiable and immutable

Some Collection methods are documented as optional operations: an implementation may refuse them by throwing UnsupportedOperationException. You'll meet this with the factory methods:

Java Collections that refuse to change

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The class names in the output (List12, UnmodifiableRandomAccessList) are private JDK classes; all you need to know is that they implement List.

  • List.of, Set.of and Map.of create truly immutable collections: nothing can change them, and they reject null.
  • Collections.unmodifiableList(list) creates a read-only view: you can't change it through the view, but changes to the original list still show through.
  • Arrays.asList is a fixed-size view of an array: set works, add and remove don't.
  • When you need a modifiable collection, copy into a new one: new ArrayList<>(List.of(...)).

Immutable Collections and Utility Methods covers these in depth.

Sequenced collections (Java 21)

Lists, deques, LinkedHashSet, TreeSet, LinkedHashMap and TreeMap all have a defined encounter order, and since Java 21 they share one API for working with their ends:

Java getFirst, getLast and reversed everywhere

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

reversed() returns a view, not a copy: it costs nothing to create, and changes to the original show through. Before Java 21 you had to write list.get(list.size() - 1) for the last element; getLast() says what you mean. A plain HashSet or HashMap has no defined order, so they are not sequenced.

Choosing a collection

Ask these questions in order:

  1. Key-value pairs? Use a map: HashMap by default, LinkedHashMap to keep insertion order, TreeMap for sorted keys or range queries.
  2. Must elements be unique? Use a set: HashSet by default, LinkedHashSet for insertion order, TreeSet for sorted order.
  3. Processing order (next job, undo stack)? Use ArrayDeque for FIFO queues and stacks, PriorityQueue for "smallest first".
  4. Otherwise, an ordered list of items? Use ArrayList.

If the size is fixed and the elements are primitives in a performance-critical loop, a plain array may still be the best choice. Choosing the Right Collection at the end of this chapter adds a big-O table and measurements.

The helper classes

Two utility classes with static methods complete the framework:

  • Collections (with an s): sort, shuffle, reverse, max, min, frequency, nCopies, unmodifiableXxx, synchronizedXxx, emptyList and more.
  • Arrays: works on arrays, and converts between arrays and lists (Arrays.asList, Arrays.stream). See The Arrays Class.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which interface does Map extend?

    Map holds key-value pairs and is not a Collection. You iterate it through views such as entrySet(), keySet() and values(), which are collections.
  2. 2. What does this print? Set<String> s = new HashSet<>(); s.add("a"); System.out.println(s.add("a"));

    add returns true only if the collection changed. The set already contains "a", so the second add changes nothing and returns false.
  3. 3. You need to keep usernames unique and print them in the order they signed up. Which class fits best?

    LinkedHashSet rejects duplicates like any Set and also remembers insertion order. HashSet has no order and TreeSet sorts alphabetically.
  4. 4. What happens? List<Integer> nums = List.of(1, 2); nums.add(3);

    List.of returns an immutable list. add is an optional operation, and immutable lists refuse it at run time. Copy into new ArrayList<>(...) to get a modifiable list.
  5. 5. Why is List<String> names = new ArrayList<>(); preferred over declaring the variable as ArrayList?

    Programming to the interface keeps the rest of the code independent of the concrete class, so swapping implementations is a one-line change.

Summary

  • The Collections Framework (java.util) separates interfaces (what a collection does) from implementations (how it does it).
  • Collection has three main branches: List (ordered, indexed), Set (unique) and Queue/Deque (processing order). Map is a separate tree for key-value pairs.
  • Java 21's sequenced interfaces give ordered collections and maps getFirst, getLast, addFirst, addLast and reversed.
  • Defaults: ArrayList, HashSet, HashMap and ArrayDeque; linked and tree variants add insertion or sorted order.
  • Hash collections rely on equals and hashCode; sorted ones on Comparable or a Comparator.
  • Declare with interface types; copy List.of results into a new collection when you need to modify them.

Next: ArrayList, the resizable list you'll use more than any other collection.