Generics, Collections, and Data Structures

Introduction

Most useful software must store, organize, search, and process groups of objects. A student-registration system stores learners, a banking platform stores transactions, and a web service maintains requests waiting for processing. Java provides two closely related facilities for this work: generics, which improve type safety and reuse, and the Collections Framework, which supplies standard data structures and algorithms.

Choosing a collection is not merely a syntactic decision. It is a design decision involving ordering, duplication, lookup requirements, memory use, concurrency, and algorithmic complexity. A programmer who understands these trade-offs can select an appropriate representation instead of relying on a single familiar class.

Learning Objectives

By the end of this chapter, you should be able to:

• define and use generic classes, interfaces, and methods;
• explain bounded type parameters, wildcards, and the PECS principle;
• describe type erasure and its practical consequences;
• select among lists, sets, queues, deques, and maps;
• use iterators, comparators, and collection algorithms safely;
• analyze common operations using Big-O notation;
• design a collection-based solution for a realistic application.

1. Why Generics Matter

Before Java generics, collections commonly stored values as Object. A retrieved object had to be cast to its intended type:

List names = new ArrayList();
names.add("Amina");
String name = (String) names.get(0);

This approach permits accidental insertion of incompatible objects and moves error detection from compilation to runtime. Generics express the element type as part of the declaration:

List<String> names = new ArrayList<>();
names.add("Amina");
String name = names.get(0);

The compiler now rejects names.add(42), and the cast is unnecessary. Generics provide compile-time type checking, reduce casts, document intent, and support reusable algorithms.

A type parameter is a placeholder for a type. By convention, T denotes a general type, E an element, K a map key, V a map value, and R a result.

Generic Classes

public class Pair<T, U> {
    private final T first;
    private final U second;

    public Pair(T first, U second) {
        this.first = first;
        this.second = second;
    }

    public T first()  { return first; }
    public U second() { return second; }
}

Pair<String, Integer> student = new Pair<>("ST204", 87);

Pair<String, Integer> is a parameterized type. The diamond operator <> allows Java to infer the constructor's type arguments from the variable declaration.

Generics work with reference types, not primitive types. Therefore, use wrapper classes such as Integer, Double, and Boolean; Java automatically performs autoboxing and unboxing when appropriate. Collections store references, so List<int> is invalid whereas List<Integer> is valid.

Generic Methods

A method may declare its own type parameters independently of the enclosing class:

public static <T> void swap(T[] values, int i, int j) {
    T temporary = values[i];
    values[i] = values[j];
    values[j] = temporary;
}

The type parameter appears before the return type. A generic method can be invoked as swap(words, 0, 1); the compiler infers T from the argument.

2. Bounds and Wildcards

An unconstrained type parameter permits operations available only on Object. Bounds restrict the type parameter and thereby provide additional guarantees.

public static <T extends Number> double total(List<T> values) {
    double result = 0.0;
    for (T value : values) {
        result += value.doubleValue();
    }
    return result;
}

T extends Number means that T is Number or a subclass. A type parameter may have an upper bound involving an interface:

public static <T extends Comparable<T>> T maximum(List<T> values) { ... }

This requires elements to be comparable with objects of the same type. Multiple bounds are allowed, with a class first and interfaces afterward, for example T extends Number & Comparable<T>.

Wildcards

A wildcard, written ?, represents an unknown type. It is useful when a method should accept a range of parameterized types.

• List<?> means a list of some unknown type. Values can safely be read as Object, but ordinary non-null values cannot be added.
• List<? extends Number> means a list of an unknown subtype of Number. It is suitable for reading numbers.
• List<? super Integer> means a list whose element type is Integer or a supertype such as Number or Object. Integers can safely be inserted.

The commonly used PECS rule is: Producer Extends, Consumer Super. If a parameterized object produces values for your method, use extends; if your method inserts values into it, use super.

public static double sum(List<? extends Number> numbers) {
    double total = 0;
    for (Number n : numbers) total += n.doubleValue();
    return total;
}

public static void addScores(List<? super Integer> destination) {
    destination.add(70);
    destination.add(85);
}

A wildcard is not the same as a type parameter. A type parameter can express a relationship between multiple arguments, whereas a wildcard generally describes one unknown type. For example, <T> T choose(T a, T b) links the argument and return types; ? does not express that relationship.

Invariance

Although Integer is a subtype of Number, List<Integer> is not a subtype of List<Number>. If it were, a Double could be inserted into a list intended to contain only integers. This property is called invariance and protects type safety. Wildcards provide controlled flexibility without removing that protection.

3. Type Erasure

Java implements generics primarily through type erasure. At compilation, generic type information is checked and then largely removed from ordinary bytecode. A List<String> and a List<Integer> have the same runtime class: ArrayList.

Consequences include:

1. A program cannot normally test value instanceof List<String>; it can test only value instanceof List<?>.
2. It is not possible to create new T() because the runtime type of T is unavailable.
3. Generic arrays such as new T[10] cannot be created directly.
4. A class cannot overload methods solely by changing type arguments, because erasure may give them identical signatures.
5. Static fields cannot use a class's type parameter as though each parameterization had a separate runtime field.

A common workaround for constructing objects is to pass a factory or Class<T> object. However, reflection and unchecked casts should be used cautiously. An unchecked warning indicates that the compiler cannot fully verify type safety; suppressing it is appropriate only after the relevant invariant has been established and documented.

4. The Java Collections Framework

The framework separates interfaces from implementations. Code should usually declare variables using the most general interface that expresses its requirements.

Collection<E> is the parent interface for lists, sets, and queues. Map<K,V> is part of the framework but is not a subtype of Collection because it represents associations rather than individual elements.

Lists

ArrayList uses a resizable array. Indexed access is constant-time on average, making it an excellent default for frequently accessed sequences. Appending is amortized constant-time: most additions are inexpensive, although occasional resizing copies elements. Inserting or removing near the beginning or middle requires shifting elements and is linear-time.

LinkedList stores nodes connected by links. Insertion at a known end is efficient, but indexed access requires traversal. In practice, ArrayList is often faster than LinkedList even for some insertions because arrays have better locality and fewer object allocations. Choose LinkedList only when its linked-node behavior is genuinely useful; for queue and deque operations, ArrayDeque is usually preferred.

Sets

A set models uniqueness. Equality and hashing are essential for hash-based sets. If a class overrides equals, it should also override hashCode so that equal objects have equal hash codes. Mutating fields used by equals or hashCode while an object is inside a HashSet can make that object difficult to find or remove.

HashSet normally offers constant-time average insertion, removal, and membership testing, but it provides no ordering guarantee. LinkedHashSet preserves insertion order with additional linking overhead. TreeSet maintains sorted order using a balanced search tree and typically provides logarithmic-time basic operations. Its ordering must be consistent with the intended notion of equality; otherwise, distinct objects may be treated as duplicates.

Maps

A map associates each key with at most one value:

Map<String, Integer> credits = new HashMap<>();
credits.put("IT204", 4);
credits.put("IT205", 3);
int value = credits.getOrDefault("IT204", 0);

HashMap is appropriate for fast average lookup without ordering. LinkedHashMap preserves insertion order and can also support access order, which is useful in cache designs. TreeMap maintains sorted key order and supports range-oriented operations such as subMap and ceilingKey.

A map may contain a null key or null values depending on implementation. HashMap permits them; TreeMap generally requires keys to be comparable or compared by its comparator and may reject null keys. ConcurrentHashMap is designed for concurrent access and does not permit null keys or values.

Queues, Deques, and Priority Queues

A queue normally follows FIFO—first in, first out. The Queue interface distinguishes methods that either return a special value or throw an exception when an operation cannot be completed:

ArrayDeque efficiently supports insertion and removal at both ends and is a strong choice for stacks and ordinary queues. A PriorityQueue removes the element with the highest priority according to natural ordering or a supplied comparator. It is not fully sorted during iteration; only the head is guaranteed to be the next element removed.

5. Iteration and Collection Algorithms

The enhanced for loop is concise and works with arrays and Iterable objects:

for (String item : names) {
    System.out.println(item);
}

An Iterator<E> provides controlled traversal. Its remove method is the safe way to remove the most recently returned element during iteration:

Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    if (iterator.next().isBlank()) iterator.remove();
}

Removing directly from a collection during a conventional iteration can cause ConcurrentModificationException. This exception is a fail-fast diagnostic, not a guarantee of thread safety and not a substitute for synchronization.

The Iterable and Collection interfaces support methods such as removeIf, forEach, and stream. The Collections utility class supplies operations including sort, reverse, shuffle, binarySearch, min, and max. Binary search requires a sorted list and uses a compatible ordering; applying it to an unsorted list produces unreliable results.

Ordering with Comparable and Comparator

A class implements Comparable<T> when it has a natural ordering:

public final class Course implements Comparable<Course> {
    private final String code;
    public Course(String code) { this.code = code; }
    public String code() { return code; }
    @Override
    public int compareTo(Course other) {
        return code.compareTo(other.code);
    }
}

A Comparator<T> represents an external ordering and is preferable when an object has several legitimate orderings:

Comparator<Course> byCodeDescending =
    Comparator.comparing(Course::code).reversed();

Comparators should ideally be transitive, antisymmetric, and consistent. Avoid subtracting integers to compare values, because overflow can produce incorrect results. Use Integer.compare(a, b) instead.

6. Complexity and Data-Structure Selection

Algorithmic complexity describes how resource requirements grow as input size n increases. Big-O notation gives an asymptotic upper-growth classification and ignores machine-specific constants. It does not predict exact execution time.

Common classes include:

Hash-table operations are commonly described as O(1) on average, assuming a good hash function and a controlled load factor. Their worst case can be O(n) under severe collisions, although modern implementations may treeify some collision structures. Tree-based operations are generally O(log n) when the tree remains balanced.

Complexity must be interpreted alongside memory, ordering, duplicates, locality, and workload. For example, a HashSet may provide fast membership testing but cannot answer “which values are between 100 and 200?” as naturally as a TreeSet.

7. Worked Example: Choosing a Collection

Suppose a library system must:

1. preserve books in the order acquired;
2. find a book quickly by ISBN;
3. prevent duplicate ISBN values;
4. process borrowing requests in arrival order.

A suitable design is:

List<Book> acquisitionOrder = new ArrayList<>();
Map<String, Book> byIsbn = new HashMap<>();
Set<String> isbnRegistry = new HashSet<>();
Queue<BorrowRequest> requests = new ArrayDeque<>();

The list supports reporting in acquisition order. The map provides average constant-time ISBN lookup. The set makes uniqueness explicit, although the map's unique keys may itself be sufficient if duplicate insertion is carefully handled. The queue models FIFO request processing. If requests instead require urgent medical-reference materials to be served first, a PriorityQueue would better represent the policy.

The design illustrates an important principle: one application can legitimately use several structures, each selected for a distinct operation.

8. Applied Case: A University Assessment Service

Background

This illustrative case concerns a university service that receives assessment submissions from many students. It must record submissions, identify the latest submission for each student, display students ordered by mark, and process moderation tasks.

Problem

The original prototype stored every record in an ArrayList and searched the list linearly for a student's latest submission. With n records, each lookup could require O(n) comparisons. Repeated lookup across many requests caused avoidable growth in response time. The system also needed to preserve arrival order and prevent duplicate submission identifiers.

Analysis

Different operations impose different structural requirements:

• submission identifiers must be unique;
• a student identifier must map to the latest submission;
• arrival order is needed for audit reporting;
• moderation tasks have priorities;
• marks must be displayed in descending order.

One list cannot optimize all these requirements simultaneously.

Approach and Solution

The revised design uses:

Map<String, Submission> latestByStudent = new HashMap<>();
Set<String> submissionIds = new HashSet<>();
List<Submission> auditLog = new ArrayList<>();
PriorityQueue<Submission> moderation =
    new PriorityQueue<>(Comparator.comparingInt(Submission::mark).reversed());

When a submission arrives, the service checks submissionIds, adds the identifier if new, appends the object to auditLog, updates latestByStudent, and inserts the item into moderation when moderation is required. The map and set provide average constant-time membership or lookup, while the list preserves historical sequence and the priority queue retrieves the highest-mark item first.

A production implementation must define equality carefully, validate input, protect against unauthorized access, and decide whether concurrent collections or external synchronization are required. If multiple threads update the structures, using separate unsynchronized collections without a coordinated consistency policy may produce lost updates or contradictory state.

Outcome

The revised design makes each requirement explicit and avoids repeated linear scans for ordinary student lookup. It also improves maintainability because the data structures communicate the domain rules directly.

Learning Points

A data structure is a model of expected operations, not merely a container. Requirements should be translated into operations and then matched to structures using complexity, semantics, and operational constraints.

9. Limitations, Safety, and Professional Practice

Collections are not automatically immutable or thread-safe. Collections.unmodifiableList creates a read-only view; it does not necessarily make the underlying list immutable if another reference can modify it. List.copyOf creates an unmodifiable copy and rejects null elements. Choose deliberately between a live view and a defensive copy.

For concurrent systems, consider ConcurrentHashMap, concurrent queues, immutable objects, or explicit locking. Thread safety concerns include atomicity: a sequence such as “check then insert” may need one atomic operation such as putIfAbsent.

Generics improve compile-time safety but do not validate data arriving from files, networks, or unchecked legacy APIs. Boundary data should be validated and converted into trusted domain objects. Avoid raw types, document unavoidable unchecked operations, and do not expose mutable internal collections unnecessarily.

Collections may retain sensitive personal information. Access control, minimization, retention policies, secure logging, and privacy regulations must be considered in enterprise applications. A collection choice cannot by itself guarantee confidentiality or compliance.

Modern Java also supports streams, records, pattern matching, and immutable collection factories. Streams can express transformations clearly, but they do not remove the need to understand data structures, ordering, side effects, or complexity. Parallel streams are not automatically faster and require operations that are safe under parallel execution.

Chapter Summary

Generics provide reusable, compile-time type-safe abstractions. Bounds express capabilities, while wildcards express controlled flexibility; the PECS rule helps distinguish producers from consumers. Type erasure explains why generic type information is largely unavailable at runtime and why certain arrays, casts, and overloads are restricted.

The Collections Framework offers lists, sets, queues, deques, and maps with different semantic and performance properties. ArrayList, HashMap, HashSet, ArrayDeque, and PriorityQueue are common choices, but ordering, equality, hashing, concurrency, memory, and workload must guide selection. Iterators and collection methods support safe traversal and modification, while Comparable and Comparator define ordering. Big-O analysis provides a disciplined way to compare operations, while recognizing average-case assumptions and practical hardware effects. Effective software often combines several structures so that each requirement is represented directly.

Key Terms

Generics: A Java mechanism for parameterized, reusable types.

Type parameter: A placeholder such as T representing a type.

Bound: A restriction placed on a type parameter.

Wildcard: The ? notation representing an unknown type.

PECS: “Producer Extends, Consumer Super,” a wildcard-design guideline.

Type erasure: Compilation of generic type information into largely non-generic runtime representations.

Invariance: The property that List<Child> is not a subtype of List<Parent>.

Collection: An object representing a group of elements.

List: An ordered collection that may contain duplicates.

Set: A collection that does not contain duplicate elements.

Map: A collection of key–value associations with unique keys.

Queue: A structure for processing elements according to a service policy.

Deque: A double-ended queue supporting both ends.

Iterator: An object used to traverse a collection safely.

Comparable: An interface defining a type’s natural ordering.

Comparator: An external object defining an ordering.

Hashing: Mapping values to hash codes for efficient table lookup.

Big-O notation: An asymptotic description of resource-growth rate.

Fail-fast iteration: Iteration that may report structural modification through an exception.

Immutability: A property in which an object's observable state cannot be changed after creation.

Review Questions

Short Answer Questions

1. Why does Java reject List<int> but accept List<Integer>?
2. State the PECS rule and explain its purpose.
3. What is the main difference between HashSet and TreeSet?
4. Why must equals and hashCode be consistent for hash-based collections?
5. What does type erasure mean?

Long Answer Questions

1. Compare ArrayList and LinkedList, including access, insertion, memory, and practical use.
2. Explain bounded type parameters and bounded wildcards with suitable Java examples.
3. Describe the roles of Comparable and Comparator and discuss when each is appropriate.
4. Explain how a HashMap, LinkedHashMap, and TreeMap differ in ordering and typical complexity.
5. Discuss why a real application may use a list, set, map, and queue simultaneously.

Analytical / Application Questions

1. Design collections for an online ticketing system that needs unique ticket IDs, lookup by customer, chronological audit history, and urgent-ticket processing. Justify every choice.
2. A program repeatedly performs indexed access and membership tests on 500,000 records. Compare possible list, set, and map designs and explain which operations dominate the decision.
3. A method accepts List<Integer> but callers need to pass List<Double> and List<Long>. Redesign the method using an appropriate wildcard and explain what values it may safely read or write.

Multiple Choice Questions with Answers

Question 1

Which declaration is type-safe and valid Java?

A. List<int> values = new ArrayList<>();

B. List<Integer> values = new ArrayList<>();

C. List<number> values = new ArrayList<>();

D. List<primitive> values = new ArrayList<>();

Correct Answer: B. List<Integer> values = new ArrayList<>();

Question 2

According to PECS, which parameter is most appropriate for a method that only reads numeric values?

A. List<? extends Number>

B. List<? super Number>

C. List<Number> only

D. List<?> with unrestricted insertion

Correct Answer: A. List<? extends Number>

Question 3

What is a typical average-case complexity for lookup in a HashMap?

A. O(n²)

B. O(log n)

C. O(1)

D. O(n log n)

Correct Answer: C. O(1)

Question 4

Which collection preserves insertion order while enforcing uniqueness?

A. HashSet

B. LinkedHashSet

C. TreeSet

D. PriorityQueue

Correct Answer: B. LinkedHashSet

Question 5

Which structure is most appropriate for repeatedly removing the highest-priority item?

A. ArrayList

B. HashMap

C. PriorityQueue

D. LinkedHashSet

Correct Answer: C. PriorityQueue

Question 6

What is the safest way to remove the current element during Iterator traversal?

A. Call collection.clear()

B. Call iterator.remove()

C. Create a second iterator and remove through it

D. Change the element's hash code

Correct Answer: B. Call iterator.remove()

Question 7

Why is List<Integer> not a subtype of List<Number>?

A. Lists cannot store wrapper objects

B. Java generics are invariant

C. Number is not a reference type

D. Integer cannot be compared

Correct Answer: B. Java generics are invariant

Question 8

Which implementation is generally suited to efficient operations at both ends?

A. ArrayDeque

B. TreeMap

C. HashSet

D. ArrayList only

Correct Answer: A. ArrayDeque

Question 9

What is a principal consequence of type erasure?

A. Generic type arguments are always available through reflection

B. A program can create new T directly at runtime

C. List<String> and List<Integer> normally have the same runtime class

D. Primitive types become valid generic arguments

Correct Answer: C. List<String> and List<Integer> normally have the same runtime class

Question 10

Which statement about binary search is correct?

A. It requires a list ordered compatibly with the search key

B. It always works on an unsorted HashSet

C. It has O(n²) complexity in every implementation

D. It requires all elements to be unique

Correct Answer: A. It requires a list ordered compatibly with the search key