4. Generics, Collections, and Data Structures

Introduction and Context

Java programs rarely manipulate isolated values. They process groups of objects: users in a session, transactions in a ledger, vertices in a graph, or results returned by a database. The quality of such programs depends not only on the operations performed but also on how data is represented, constrained, searched, ordered, and shared between components.

Early Java collections stored elements as `Object`, which provided flexibility but transferred type checking to runtime. Generics, introduced in Java 5, made type relationships explicit at compile time. The Collections Framework then supplied standard interfaces, implementations, and algorithms for managing groups of objects. Together, generics and collections form a central abstraction layer in Java programming.

At postgraduate level, collection choice should be treated as an engineering decision. A list, set, queue, or map expresses a different logical model; two implementations of the same interface may have substantially different memory and time behaviour. Correct code therefore requires understanding generic type rules, collection contracts, hashing, ordering, iteration, concurrency implications, and algorithmic complexity.

Learning Objectives

After studying this chapter, a learner should be able to:

• explain generic classes, methods, bounds, wildcards, and type erasure;
• select collection interfaces and implementations according to semantics and complexity;
• apply iterator, equality, hashing, ordering, and comparator contracts correctly;
• distinguish compile-time type safety from runtime representation;
• analyse common collection operations using asymptotic complexity;
• identify professional, security, maintainability, and performance risks in collection-based designs.

Generics as Compile-Time Abstraction

A generic type declares one or more type parameters whose actual arguments are supplied by the client. `List<String>` communicates that the list is intended to contain strings, while `List<Integer>` communicates a different contract. The compiler can reject an invalid insertion before execution begins.

```java

List<String> names = new ArrayList<>();

names.add("Asha");

String first = names.get(0);

```

The diamond operator infers type arguments from context. Generic classes may define several parameters:

```java

class Pair<K, V> {

private final K key;

private final V value;

Pair(K key, V value) {

this.key = key;

this.value = value;

}

K key() { return key; }

V value() { return value; }

}

```

Generics reduce casts and document intended relationships. They do not, however, make objects immutable, prevent all runtime errors, or permit every type relationship that appears intuitively valid.

Generic Methods and Type Inference

A method may introduce its own type parameter independently of the enclosing class:

```java

static <T> T first(List<T> values) {

if (values.isEmpty()) throw new IllegalArgumentException("empty list");

return values.get(0);

}

```

The compiler often infers `T` from the argument and assignment context. A generic method is especially useful when the result type is related to an input type, such as copying values from one collection to another.

Invariance and Wildcards

Although `Integer` is a subtype of `Number`, `List<Integer>` is not a subtype of `List<Number>`. If it were, a `Double` could be inserted through a `List<Number>` reference and violate the original list’s intended type.

Wildcards express controlled flexibility. `List<?>` means a list of some unknown type. Values can safely be read as `Object`, but ordinary values cannot be added because the actual element type is unknown.

The most useful design rule is often expressed as PECS: Producer Extends, Consumer Super.

```java

static double total(List<? extends Number> values) {

double result = 0;

for (Number value : values) result += value.doubleValue();

return result;

}

static void addDefaults(List<? super Integer> target) {

target.add(0);

target.add(1);

}

```

An `extends` wildcard is appropriate when a method reads values from a producer. A `super` wildcard is appropriate when it inserts values into a consumer. A collection with an exact type, such as `List<Integer>`, is suitable when both reading and writing are required.

Bounds can restrict type parameters:

```java

static <T extends Comparable<? super T>> T maximum(List<T> values) {

if (values.isEmpty()) throw new IllegalArgumentException("empty list");

T result = values.get(0);

for (T value : values)

if (value.compareTo(result) > 0) result = value;

return result;

}

```

A bound communicates that the operation requires a capability, here comparison. Multiple bounds are possible, but a class bound, if present, precedes interface bounds.

Type Erasure and Its Consequences

Java generics are primarily a compile-time mechanism. During compilation, type information is checked and, in many cases, erased from the runtime representation. Consequently, `List<String>` and `List<Integer>` generally share the same runtime class. This preserves compatibility with older Java libraries but produces important restrictions:

• primitive type arguments such as `List<int>` are illegal; wrapper types are required;
• `new T()` and `new T[]` are not directly permitted;
• `instanceof List<String>` is illegal because the type argument is unavailable at runtime;
• static fields cannot depend on a class’s type parameter;
• unchecked casts and raw types can undermine compile-time guarantees.

```java

@SuppressWarnings("unchecked")

T value = (T) object;

```

An unchecked warning should not be silenced casually. It indicates that the compiler cannot verify a type claim. APIs involving arrays, reflection, serialization, or legacy code require particular care because runtime checks may not match generic declarations.

The Collections Framework as a Conceptual Model

The Collections Framework separates abstract behaviour from implementation. `Collection<E>` represents a group of elements; `List<E>` adds positional access and permits duplicates; `Set<E>` models uniqueness; `Queue<E>` models elements awaiting processing; and `Map<K,V>` associates keys with values but is not itself a subtype of `Collection`.

This distinction is semantic as well as technical. Choosing `Set` states that duplicate membership is not meaningful. Choosing `Queue` states that removal follows a processing discipline. Programming to interfaces allows implementations to change without changing client code.

Lists

`ArrayList` is backed by a resizable array. Indexed access is constant-time in the usual model, appending is amortized constant-time, and insertion or removal near the beginning is linear because elements must be shifted. It is a strong default for iteration and random access.

`LinkedList` represents nodes connected by links. Insertion or removal at a known list position can be efficient, but locating that position is linear. Its node overhead and poor locality often make it less attractive than expected. It also implements `Deque`, so its use can be justified when double-ended queue operations are central.

Sets

`HashSet` uses hashing to provide expected constant-time insertion, lookup, and removal when hash distribution is reasonable. It does not promise iteration order.

`LinkedHashSet` maintains insertion order in addition to uniqueness. `TreeSet` maintains sorted order using natural ordering or a supplied comparator and commonly provides logarithmic-time basic operations. A sorted set is not merely a faster set; it provides range and order semantics.

Maps

`HashMap` is appropriate for key-based lookup when no ordering guarantee is required. A key’s `equals` and `hashCode` methods determine identity within the map. `LinkedHashMap` preserves a predictable insertion order and can also support access-order arrangements useful in bounded-cache designs.

`TreeMap` stores keys in sorted order and supports operations such as range views. Its ordering mechanism must be consistent with the intended notion of key identity. `EnumMap` is highly suitable when keys are enum constants, while `ConcurrentHashMap` is designed for concurrent access with stronger operational properties than a synchronized wrapper around a general map.

Queues and Deques

`Queue` exposes insertion, inspection, and removal operations. The paired method families differ in failure behaviour: `add`, `element`, and `remove` may throw exceptions, whereas `offer`, `peek`, and `poll` return failure indicators such as `false` or `null`.

`ArrayDeque` is generally an efficient choice for stack and double-ended queue behaviour. It avoids the legacy design issues associated with `Stack`. A priority queue orders removal by priority rather than insertion time; its head is the least element according to natural ordering or a comparator. Iterating through a priority queue should not be confused with repeatedly polling it, since iteration does not promise sorted traversal.

Contracts That Make Collections Work

Equality and Hashing

The `equals` contract requires reflexivity, symmetry, transitivity, consistency, and a false result when compared with `null`. If two objects are equal, they must have the same hash code. The reverse is not required: unequal objects may share a hash code, although excessive collisions reduce performance.

A class used as a hash key should normally be immutable with respect to fields involved in equality and hashing. If a key changes after insertion, the map may be unable to locate the entry in the bucket determined by its new hash code.

```java

record AccountId(String bank, long number) {}

```

Records provide value-oriented equality and hashing for their components, making them useful for stable keys when their components are themselves appropriate key values.

Natural Ordering and Comparators

`Comparable<T>` defines a type’s natural ordering through `compareTo`. A `Comparator<T>` defines ordering externally and permits multiple policies, such as ordering employees by salary, then name.

For sorted collections, comparison determines placement and often identity. If a comparator returns zero for two objects that are not equal, a `TreeSet` may retain only one of them. This is not necessarily a defect, but it must be deliberate. Comparators should be transitive, consistent, and safe from arithmetic overflow. Prefer `Comparator.comparingInt(Employee::age)` to subtracting ages directly.

```java

Comparator<Employee> bySalaryThenName =

Comparator.comparingInt(Employee::salary)

.thenComparing(Employee::name);

```

Iteration, Views, and Modification

The enhanced `for` statement uses an iterator or an equivalent traversal mechanism. An iterator maintains traversal state and may support removal through its own `remove` operation. Direct structural modification of many collections during iteration causes `ConcurrentModificationException`, although this is a fail-fast diagnostic rather than a synchronization guarantee.

```java

Iterator<String> it = names.iterator();

while (it.hasNext()) {

if (it.next().isBlank()) it.remove();

}

```

Modern Java also provides `removeIf`, which expresses this operation more directly. A collection view, such as `Map.keySet()` or `subList`, is backed by the original structure. Changes may therefore affect both objects. Views are useful but require awareness of lifetime, structural modification, and ownership.

Streams offer declarative traversal and transformation, but they do not replace collection knowledge. A stream is generally single-use, intermediate operations are lazy, and parallel execution is not automatically faster. Side effects inside stream pipelines can produce correctness and thread-safety problems.

Complexity as a Selection Tool

Big-O notation describes how resource requirements grow with input size; it does not predict exact running time on every machine. Typical complexity patterns include:

| Structure or operation | Typical complexity | Interpretation |

|---|---:|---|

| `ArrayList.get(i)` | O(1) | direct index calculation |

| `ArrayList` insertion at front | O(n) | elements shift |

| `HashMap.get` | expected O(1) | depends on hashing and resizing |

| `TreeMap.get` | O(log n) | balanced ordered structure |

| `PriorityQueue.offer`/`poll` | O(log n) | heap adjustment |

| `ArrayDeque` end operation | O(1) amortized | circular-buffer behaviour |

| sorting a list | O(n log n) typical | comparison sorting |

Amortized analysis explains why an occasional expensive array resize does not make every append linear. Complexity should be considered together with memory locality, allocation cost, workload distribution, ordering requirements, and concurrency. A theoretically attractive structure may perform poorly if its access pattern causes excessive allocation or cache misses.

A Decision Framework for Data-Structure Selection

A disciplined selection process begins by describing the abstract operation rather than naming a familiar class. Ask whether duplicates matter, whether positional access is required, whether keys are used, whether sorted or insertion order must be observable, and whether operations occur at one end or both ends.

Next, identify the dominant workload: random reads, sequential scans, membership tests, range queries, priority removal, or frequent updates. Establish expected scale and memory constraints. Then select the narrowest suitable interface and choose an implementation whose contract and complexity match the workload. Finally, test realistic data distributions, including empty input, duplicate values, collisions, large collections, and concurrent access if relevant.

A common error is to select `LinkedList` merely because insertion is said to be O(1). The insertion is constant-time only when the relevant node or iterator position is already known. If finding that position costs O(n), the total operation remains linear.

Applied Case: Designing a Student-Assessment Service

Background

Consider an illustrative university assessment service that receives submissions, records marks, identifies students, and produces ranked reports. The service has three distinct requirements: retrieve a student by registration identifier, preserve submissions in arrival order for audit, and produce a ranked view by mark.

Situation and Analysis

Using one collection for all tasks would create unnecessary compromises. A list is appropriate for audit order but inefficient for identifier lookup. A hash map supports direct lookup but does not express arrival order by itself. A sorted set could provide ranking, but ties and mutable marks create identity risks.

Design Approach

The service may use:

```java

Map<StudentId, Submission> byStudent = new HashMap<>();

List<Submission> auditTrail = new ArrayList<>();

List<Submission> ranking = new ArrayList<>();

```

`StudentId` should be an immutable value type with correct equality and hashing. Each accepted submission is inserted into the map and audit list. When a report is requested, a snapshot of submissions is copied and sorted using a comparator that orders marks descending and registration identifiers as a deterministic tie-breaker:

```java

ranking = new ArrayList<>(byStudent.values());

ranking.sort(Comparator.comparingInt(Submission::mark)

.reversed()

.thenComparing(Submission::studentId));

```

If the service must preserve arrival order during lookup, a `LinkedHashMap` could replace the separate audit list. If frequent range queries by mark are required, another index, such as a sorted structure, may be justified. The design should not mutate a key after insertion, and concurrent requests would require an explicit concurrency strategy rather than an assumption that ordinary collections are thread-safe.

Outcome and Learning Points

The design gives expected constant-time student lookup, linear-time report preparation, deterministic ordering, and a clear separation between operational storage and presentation ordering. It also demonstrates that data-structure choice follows requirements: one collection rarely optimizes every operation. Stable identifiers, explicit ordering, and interface-based declarations improve correctness and future changeability.

Professional and Technical Considerations

Collection APIs are widely used at system boundaries: database repositories return lists or maps, JSON libraries materialize collections, caches use maps, and messaging systems use queues. Public APIs should expose the least powerful abstraction necessary. Returning an unmodifiable view or defensive copy can prevent callers from violating invariants, whereas returning a mutable internal list exposes representation details.

Null handling deserves explicit policy. Some implementations permit null keys or values, while others reject them; concurrent and sorted collections often impose stricter constraints. Empty collections are usually preferable to `null` because they simplify callers and make absence explicit through size or iteration.

Security and governance also matter. Untrusted input can create memory exhaustion by requesting enormous collections, exploit poor hashing distributions, or trigger expensive sorting. Bounded caches, input limits, timeouts, and monitoring are practical safeguards. Sensitive data should not be retained in collections longer than necessary, and logs or diagnostic dumps must avoid exposing personal information.

Thread safety must be designed, not inferred. `ArrayList`, `HashMap`, and most ordinary collections are not safe for unsynchronized concurrent mutation. Options include confinement, immutable snapshots, concurrent collections, locks, or atomic update methods. A synchronized wrapper protects individual operations but may not make compound sequences atomic.

Common Mistakes and Limitations

Raw types such as `List values` discard generic checking and should be confined to unavoidable legacy interfaces. Using `==` for object value comparison, omitting `hashCode` when overriding `equals`, and mutating hash keys are frequent defects. Comparators that violate transitivity can produce unpredictable sorting behaviour. Assuming hash-based operations are always constant-time ignores collisions and resizing.

Another mistake is confusing an unmodifiable collection with an immutable object. An unmodifiable view prevents modification through that reference, but changes through another reference may remain visible. Defensive copying is required when an independent snapshot is intended.

Finally, micro-optimizing before measuring can obscure the real issue. Profiling, representative benchmarks, complexity analysis, and tests of collection contracts should guide optimization.

Current Developments and Best Practices

Modern Java encourages immutable data carriers, records for value objects, factory methods such as `List.of`, and enhanced comparator and stream APIs. Pattern matching and improved language inference reduce incidental code, but they do not remove the need to understand collection contracts. Primitive-specialized collections remain important in high-throughput systems because boxing increases allocation and memory use; such libraries should be selected after evaluating compatibility and operational needs.

Recommended practice is to program to interfaces, prefer generic types, choose structures from workload requirements, use immutable keys, define deterministic comparators, document ordering and null policies, measure before optimizing, and test empty, duplicate, large, adversarial, and concurrent cases. Collection design is ultimately a balance among semantics, complexity, memory, safety, and maintainability.

Chapter Summary

Generics provide compile-time type relationships through parameterized classes, methods, bounds, and wildcards. Type erasure explains both compatibility and restrictions such as the inability to create generic arrays or test most parameterized types at runtime. The Collections Framework supplies interfaces whose semantics guide implementation choice: lists preserve sequence, sets express uniqueness, maps support key association, and queues model processing order.

Correct collection use depends on equality, hashing, comparison, iteration, and modification contracts. Hash-based structures offer expected constant-time access, ordered trees offer logarithmic operations and range semantics, arrays support efficient indexed access, and queues support specialized processing patterns. Effective engineers select structures by workload, complexity, memory behaviour, mutability, and concurrency requirements rather than by habit.

Key Terms

Generic type: A type declared with one or more type parameters.

Type parameter: A symbolic type variable used in a generic declaration.

Wildcard: The `?` notation representing an unknown type argument.

Upper bound: A restriction such as `T extends Number`.

Lower-bounded wildcard: A wildcard such as `? super Integer`.

Type erasure: Compilation treatment that removes most generic type arguments from runtime representation.

Raw type: A generic type used without its type arguments.

Collection: An abstraction representing a group of elements.

List: An ordered collection that commonly permits duplicates.

Set: A collection whose contract models uniqueness.

Map: An association between keys and values.

Hashing: Mapping a value to a hash code used for table placement.

Equality contract: Rules governing consistent value comparison through `equals`.

Comparator: An object defining an external ordering policy.

Natural ordering: Ordering defined by a type’s `Comparable` implementation.

Iterator: An object that traverses collection elements.

Fail-fast: Behaviour that detects some structural changes during iteration and reports them.

Amortized complexity: Average cost per operation over a sequence of operations.

Immutable key: A key whose equality-relevant state does not change after insertion.

View: A collection-facing representation backed by another collection.

Review Questions

Short Answer Questions

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

2. State the PECS rule and explain its purpose.

3. What relationship must hold between `equals` and `hashCode`?

4. Why can changing a map key after insertion make an entry inaccessible?

5. Distinguish a `HashMap` from a `TreeMap` in terms of ordering.

Long Answer Questions

1. Explain generic classes, generic methods, bounded type parameters, wildcards, and type erasure with suitable code examples.

2. Compare `ArrayList`, `LinkedList`, `HashSet`, `TreeSet`, `HashMap`, and `TreeMap` in terms of semantics and typical complexity.

3. Discuss the contracts of `equals`, `hashCode`, `Comparable`, and `Comparator`, including consequences of violating them.

4. Explain how workload, ordering, memory, and concurrency requirements influence data-structure selection.

5. Describe iterator behaviour, collection views, structural modification, and safe removal during traversal.

Analytical / Application Questions

1. A system performs one million identifier lookups, occasional sequential reports, and no sorted queries. Which primary collection would you choose, and what key-design conditions must hold?

2. A program uses a `TreeSet` of employees but employees with different names disappear when their salaries match. Analyse the likely comparator problem and propose a correction.

3. A service uses `LinkedList` for frequent insertion at arbitrary indexes but first searches from the beginning for each index. Analyse the actual complexity and recommend a design based on the likely workload.

22. Multiple Choice Questions with Answers

Question 1

Which declaration allows a method to read numeric values from a List<Integer> and a List<Double>?

A. List<Number>

B. List<? extends Number>

C. List<? super Number>

D. List<Object>

Correct Answer: B. List<? extends Number>

Question 2

Why is List<Integer> not assignable to List<Number>?

A. Integer is not a subtype of Number

B. Lists cannot contain wrapper objects

C. It could permit insertion of an incompatible Number such as Double

D. Generic types are always invariant at runtime only

Correct Answer: C. It could permit insertion of an incompatible Number such as Double

Question 3

Which operation is typically expected to be constant time in a HashMap?

A. Lookup by key, assuming suitable hashing

B. Lookup by sorted key range

C. Traversal in key order

D. Sorting all keys

Correct Answer: A. Lookup by key, assuming suitable hashing

Question 4

What is the safest general practice for an object used as a HashMap key?

A. Mutate its hash-relevant fields after insertion

B. Use identity comparison only

C. Keep equality-relevant state stable after insertion

D. Override equals but not hashCode

Correct Answer: C. Keep equality-relevant state stable after insertion

Question 5

What does a TreeSet primarily use to determine both order and practical element identity?

A. Object memory address

B. Hash code only

C. Insertion timestamp

D. Natural ordering or a supplied Comparator

Correct Answer: D. Natural ordering or a supplied Comparator

Question 6

Which statement about a PriorityQueue iterator is correct?

A. It always visits elements in priority order

B. It necessarily removes each visited element

C. It should not be assumed to provide sorted traversal

D. It can only contain String values

Correct Answer: C. It should not be assumed to provide sorted traversal

Question 7

What does type erasure imply?

A. Generic type arguments are generally unavailable for ordinary runtime instanceof checks

B. Generic collections cannot be compiled

C. All generic operations become compile-time errors

D. Primitive type arguments become legal

Correct Answer: A. Generic type arguments are generally unavailable for ordinary runtime instanceof checks

Question 8

A program repeatedly inserts elements at the front and removes them from the front. Which is generally the most suitable standard structure?

A. TreeMap

B. ArrayDeque

C. TreeSet

D. PriorityQueue

Correct Answer: B. ArrayDeque

Question 9

Why can an ArrayList append be described as amortized O(1)?

A. Every append always performs no allocation

B. Occasional resizing costs are averaged over many inexpensive appends

C. Appending requires binary search

D. The list is implemented as linked nodes

Correct Answer: B. Occasional resizing costs are averaged over many inexpensive appends

Question 10

A comparator returns zero for employees with equal salaries even when their names differ. What may happen in a TreeSet?

A. Both employees are guaranteed to remain

B. The set may treat them as duplicates

C. The comparator is ignored

D. Hash codes determine their order instead

Correct Answer: B. The set may treat them as duplicates