10.1 Introduction to the Collection Framework

Start after arrays and interfaces. List<String> means a list of String elements, and Map<String, Integer> maps String keys to Integer values; Chapter 12 explains generics in full. With about 30 minutes of running the Java 17 examples, you should be able to narrow down your choice to the appropriate collection interface and implementation based on access method, order, repetition, and concurrency requirements.

An array could store the names, but the length had to be determined when creating it. If the number of people exceeded the estimate, you would need to allocate a larger array and copy the elements. If the number was smaller, there would be unused spaces left. Inserting elements in the middle would still require moving subsequent elements.

The collection framework encapsulates expansion, lookup, deduplication, and queue operations into a unified API. It does not eliminate the costs of data structures. ArrayList.add(0, value) still requires moving existing elements, and HashMap also relies on reliable hashCode and equals.

1. Arrays Still Have Their Place

String[] fixedTeam = new String[3];
fixedTeam[0] = "Zhang San";
fixedTeam[1] = "Li Si";
fixedTeam[2] = "Wang Wu";

Arrays are suitable for scenarios where the length is fixed and basic types need to be stored, or when an API explicitly requires an array. Collections are better for situations involving variable size, the need to insert or delete elements, or when you want to express "list, set, queue, or map" through an interface.

Generic collections cannot directly use primitive types; you must use List<Integer> instead of List<int>. This results in boxing; for large-scale numerical computations, primitive type arrays or specialized structures may be more appropriate.

2. Interface Mapping

Iterable<E>
└── Collection<E>
    ├── List<E>
    │   ├── ArrayList<E>
    │   └── LinkedList<E>
    ├── Set<E>
    │   ├── HashSet<E>
    │   ├── LinkedHashSet<E>
    │   └── SortedSet<E> / NavigableSet<E>
    │       └── TreeSet<E>
    └── Queue<E>
        ├── Deque<E>
        │   ├── ArrayDeque<E>
        │   └── LinkedList<E>
        └── PriorityQueue<E>

Map<K, V>                         // does not inherit from Collection
├── HashMap<K, V>
├── LinkedHashMap<K, V>
└── SortedMap<K, V> / NavigableMap<K, V>
    └── TreeMap<K, V>

Four types of interfaces express different constraints:

Interface	Primary Issue	Typical Guarantees
List	What element is at a given index	Has encounter order, permits duplicates, and supports index access
Set	Does this value already exist	Does not retain duplicate elements based on equality rules
Queue / Deque	What element comes next or sits at either end	Accesses elements according to queue strategy, does not provide a general index
Map	What value is associated with a particular key	Each key maps to at most one value

"Ordered" needs to clarify which order it refers to. List maintains the encounter order of elements; LinkedHashSet and a default LinkedHashMap preserve insertion order (LinkedHashMap can also be configured for access order); TreeSet/TreeMap sorts elements according to natural order or Comparator; HashSet/HashMap does not guarantee iteration order.

3. Run It in Three Minutes

First, prepare a temporary directory:

chapter10_choice_root=$(mktemp -d)
readonly chapter10_choice_root
mkdir -p "$chapter10_choice_root/out"
cd "$chapter10_choice_root"

Save as CollectionChoiceDemo.java:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;

public class CollectionChoiceDemo {
    public static void main(String[] args) {
        List<String> claims = new ArrayList<>();
        claims.add("Zhang San");
        claims.add("Li Si");
        claims.add("Zhang San");

        Set<String> uniquePeople = new LinkedHashSet<>(claims);

        Queue<String> waiting = new ArrayDeque<>();
        waiting.offer("Zhang San");
        waiting.offer("Li Si");

        Map<String, Integer> stock = new LinkedHashMap<>();
        stock.put("Component", 50);
        stock.put("Wood", 30);
        stock.merge("Component", -2, Integer::sum);

        checkEquals(List.of("Zhang San", "Li Si", "Zhang San"), claims);
        checkEquals(List.of("Zhang San", "Li Si"), List.copyOf(uniquePeople));
        checkEquals("Zhang San", waiting.poll());
        checkEquals(48, stock.get("Component"));

        System.out.println("Material request log: " + claims);
        System.out.println("Unique people: " + uniquePeople);
        System.out.println("Next person: " + waiting.peek());
        System.out.println("Inventory: " + stock);
        System.out.println("Collection selection check passed");
    }

    static void checkEquals(Object expected, Object actual) {
        if (!Objects.equals(expected, actual)) {
            throw new AssertionError("expected=" + expected + ", actual=" + actual);
        }
    }
}

Compile and run:

javac --release 17 -encoding UTF-8 -Xlint:all -d out CollectionChoiceDemo.java
java -cp out CollectionChoiceDemo

Expected output:

Material request log: [Zhang San, Li Si, Zhang San]
Unique people: [Zhang San, Li Si]
Next person: Li Si
Inventory: {Component=48, Wood=30}
Collection selection check passed

After saving the required output, clean up:

cd
ls -ld -- "$chapter10_choice_root"
rm -r -- "$chapter10_choice_root"

This example demonstrates collection operations; nonnegative stock, integer overflow, and concurrent deductions need additional rules. It deliberately uses LinkedHash implementations to make output order part of the contract. If you switch to HashSet or HashMap, the test should compare the content rather than the string display order.

4. Choose the Interface First, Then the Implementation

Variables are typically declared with the narrowest interface needed:

List<String> names = new ArrayList<>();
Map<String, Integer> stock = new HashMap<>();

If a caller only needs List, it should not depend on the specific methods of ArrayList. This reduces the number of affected code segments when the implementation is changed. When a range query is needed for NavigableMap, the capability should be explicitly declared, and the type should not be narrowed down to just Map.

Ask these questions in order:

1. Are you looking up a value by key or iterating by element? For the former, choose Map.
2. Does the presence of duplicate elements make sense? If not, choose Set.
3. Do you need indexing, FIFO, LIFO, or priority? Consider List, Queue/Deque, and PriorityQueue accordingly.
4. Is the iteration order part of the business result? If insertion order is needed, use LinkedHash. If sorting and range queries are required, use Tree/Navigable.
5. Is null allowed? The contract varies between implementations. Both ArrayDeque and List.of reject null.
6. Are there concurrent writes? Ordinary collections are not automatically thread-safe containers.

5. Common Cost Models for Implementations

Set/Map costs below refer to one lookup, insertion, or deletion, not a full traversal. The table shows the typical complexity of common implementations in Java 17, assuming the data structure is not concurrently modified, the hash distribution is reasonable, and the cost of the comparator is manageable:

Requirement	Common Choice	Typical Cost and Boundaries
Index-based reading	ArrayList	get O(1), middle insertion/deletion O(n)
Double-ended queue	ArrayDeque	Double-ended operations amortized O(1), no null allowed
Link list end operations	LinkedList	End O(1), index-based lookup O(n)
Unsorted deduplication	HashSet	Expected O(1), iteration order is undefined
Deduplication while preserving insertion order	LinkedHashSet	Expected O(1), maintaining links has additional overhead
Sorted deduplication/range	TreeSet	O(log n), equality is determined by comparison results
Key lookup	HashMap	Expected O(1), order is undefined
Ordered keys and range	TreeMap	O(log n), provides NavigableMap operations

Big O is not the same as fixed time. Contiguous storage, object allocation, cache hits, comparator costs, and data size all affect the actual results. When performance conclusions are needed, use representative data and JMH measurements, not a set of milliseconds from a single machine.

6. Two Groups of Methods for Queue

Queue offers two sets of methods for a full or empty queue. Invalid elements and other errors may still throw exceptions; offer does not mean “never throws”:

Operation	Returns a special value	Throws an exception on failure
Enqueue	offer	add
Dequeue	poll	remove
Peek at the front	peek	element

The poll/peek methods of an empty queue return null. Since ArrayDeque prohibits null values, null can clearly represent "no elements". In a bounded queue, offer can return false to indicate that the capacity is full.

When used as a stack, prioritize declaring Deque<E>, and call push, pop, and peek. The legacy Stack class extends Vector, and its API and synchronization model are not suitable for the new design.

The PriorityQueue's poll returns the current minimum element (or the highest priority as defined by Comparator), but directly iterating over PriorityQueue does not guarantee overall sorting. When sorting output is required, repeatedly poll a copy of the queue, or sort the elements separately.

7. Traverse and Modify Separately

for (String claim : claims) {
    System.out.println(claim);
}

for (Map.Entry<String, Integer> entry : stock.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

stock.forEach((item, count) ->
        System.out.println(item + " -> " + count));

When iterating over the keys and values of a Map, entrySet can retrieve both at the same time. Use keySet when only keys are needed, and values when only values are required.

An enhanced for loop uses an Iterator for an Iterable and indexed access for an array. Structurally changing a collection through another path during iteration often causes ConcurrentModificationException in fail-fast implementations. Detection is best-effort, and it does not provide thread safety. The deletion rules will be elaborated in the next section.

8. Mutability, Nulls, and Concurrency Depend on the Contract

The statement "Java collections allow null" is not valid. HashMap allows a null key and multiple null values, while TreeMap rejects null keys when using natural ordering. ArrayDeque rejects null, and List.of/Set.of/Map.of also reject null.

Similarly, interfaces do not guarantee mutability: List.of returns an unmodifiable list; Arrays.asList returns a fixed-size array view; and Collections.unmodifiableList returns a read-only wrapper, but the underlying list may still be modified by other references.

Standard classes like ArrayList and HashMap do not support un-synchronized concurrent writes. When concurrency semantics are required, define composite operations first, then choose between ConcurrentHashMap, blocking queues, external locks, or immutable snapshots. Putting a synchronized wrapper around each method does not necessarily protect the entire "check-and-write" logic.

9. Language Boundaries

Python lists can grow; the common CPython implementation uses a dynamic array. For efficient operations at both ends, use collections.deque; since Python 3.7, dict has maintained insertion order, but it does not automatically sort by key.

C++'s vector, deque, list, and unordered_map can only be conceptually compared with Java types. Iterator invalidation, memory ownership, and concurrency contracts are all different. This chapter only verifies Java 17 examples.

Check the Container Contract

Try representing the same material requests with a List, Set, and Queue. Identify which operations each choice adds or removes, then check whether nulls are allowed and whether callers may modify the collection.

Reviewing the Official Contracts for Java 17

• Java Collections Framework Overview: Interface hierarchy, optional operations, and common implementations.
• Collection and Map: Two independent interface lines.
• Queue and Deque: Two sets of operations that return special values and throw exceptions.
• OpenJDK JMH: Use benchmark testing to verify real workloads when comparing the performance of implementations.

Next Step: Organizing the List Ledger

The next lesson continues to organize the material requisition records. You will actually check the costs of ArrayList and LinkedList, the shared relationship between subList and Arrays.asList, and why some removals fail during iteration.

Continue learning about List