Collections, Generics, and Data Structures

Introduction

Most useful programs manage groups of values rather than isolated variables. A banking application stores accounts, a web service processes queues of requests, and a student system maps identification numbers to records. Java provides a systematic solution through the Java Collections Framework (JCF), a set of interfaces, implementations, algorithms, and utility methods for storing and processing objects.

This chapter explains generic types and the principal collection abstractions: lists, sets, maps, queues, and iterators. It also introduces comparators and shows how to select a collection according to ordering, duplication, access, memory, and performance requirements.

Learning Objectives

After completing this chapter, you should be able to:

• Explain the purpose of generics and type safety.
• Distinguish lists, sets, maps, queues, and deques.
• Use common JCF implementations such as ArrayList, LinkedList, HashSet, TreeSet, HashMap, and ArrayDeque.
• Traverse collections using enhanced for loops and iterators.
• Sort objects with Comparable and Comparator.
• Choose an appropriate collection using functional requirements and asymptotic performance.
• Avoid common errors involving equality, hashing, modification, and mutable keys.

1. The Collections Framework

A collection is an object that groups multiple elements. Java separates an abstraction from its implementation. The List interface describes ordered, index-based behavior, while ArrayList and LinkedList provide different implementations of that behavior.

The main interfaces are:

Map is part of the Collections Framework but is not a subtype of Collection, because a map stores associations rather than individual elements.

Programming to an interface is an important design practice:

List<String> names = new ArrayList<>();
Set<Integer> ids = new HashSet<>();
Map<String, Double> prices = new HashMap<>();

The variable type states what operations the client needs, while the object type selects the implementation. This makes later replacement easier.

2. Generics and Type Safety

A generic type receives one or more type arguments. In List<String>, String is the element type; in Map<String, Integer>, String is the key type and Integer is the value type.

Without generics, a collection could contain unrelated objects and every retrieval would require a cast. Generics move many errors from run time to compile time:

List<String> cities = new ArrayList<>();
cities.add("Lagos");
// cities.add(42);              // compile-time error
String city = cities.get(0);    // no cast required

The diamond operator infers type arguments from the declaration:

List<Integer> scores = new ArrayList<>();

2.1 Generic classes and methods

A class can define a type parameter:

public class Box<T> {
    private T value;

    public void set(T value) { this.value = value; }
    public T get() { return value; }
}

A method may also be generic:

public static <T> void printAll(List<T> items) {
    for (T item : items) {
        System.out.println(item);
    }
}

A bounded type parameter restricts acceptable types:

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

Here T must be Number or a subclass. Java generics use reference types, so primitive values use wrapper classes such as Integer, Double, and Boolean. Autoboxing and unboxing usually convert between primitives and wrappers automatically.

2.2 Wildcards

A wildcard represents an unknown type. List<?> can refer to a list of any reference type, but values cannot generally be added to it except null.

Two useful forms are:

• ? extends T: a producer of values compatible with T; values can safely be read as T.
• ? super T: a consumer that can safely accept values of type T.

For example:

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

Type erasure means generic type arguments are mainly enforced at compile time and are not normally available at run time. Consequently, Java does not permit new T() or new ArrayList<String>[10] in ordinary generic code.

3. Lists

A List preserves insertion order and permits duplicate elements. It supports positional operations such as get(index), set(index, value), and add(index, value).

ArrayList

ArrayList uses a resizable array. Access by index is efficient, typically constant time, written as O(1). Appending is typically amortized O(1), although occasional resizing requires copying elements. Inserting or removing near the beginning or middle usually requires shifting elements and is typically O(n), where n is the number of elements.

List<String> tasks = new ArrayList<>();
tasks.add("Compile");
tasks.add("Test");
tasks.remove("Compile");

ArrayList is usually the default list choice when frequent indexed access and iteration matter more than middle insertion.

LinkedList

LinkedList stores elements in linked nodes. Inserting or removing at a known end is efficient, but finding an element by index requires traversal and is typically O(n). It is therefore not automatically faster than ArrayList. For queue or deque behavior, ArrayDeque is often a clearer and more efficient choice.

4. Sets

A set rejects duplicate elements according to equality. The meaning of order depends on the implementation:

• HashSet: no guaranteed iteration order; usually fast membership operations.
• LinkedHashSet: preserves insertion order while retaining hash-based lookup.
• TreeSet: maintains sorted order and commonly provides O(log n) insertion, removal, and search.

Set<String> languages = new HashSet<>();
languages.add("Java");
languages.add("Python");
languages.add("Java");
System.out.println(languages.size()); // 2

A set depends on a correct definition of equality. For hash-based sets, objects should consistently implement equals and hashCode. If two objects are equal according to equals, they must return the same hash code.

5. Maps

A map associates each key with at most one value. Calling put with an existing key replaces its previous value.

Map<String, Integer> inventory = new HashMap<>();
inventory.put("Keyboard", 12);
inventory.put("Mouse", 30);
inventory.merge("Keyboard", 3, Integer::sum);

HashMap generally provides expected constant-time lookup, insertion, and removal, but it does not guarantee iteration order. LinkedHashMap preserves insertion order, or can be configured for access order. TreeMap keeps keys sorted and generally provides O(log n) basic operations.

Safe map traversal should use views such as entrySet:

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

get returns null when a key is absent, but a map may also explicitly store null. Use containsKey when the distinction matters. getOrDefault is useful when a default value is appropriate.

6. Queues and Deques

A queue generally processes elements in first-in, first-out order. The methods offer, poll, and peek are preferred when failure should be represented by a return value rather than an exception.

Queue<String> printJobs = new ArrayDeque<>();
printJobs.offer("Report.pdf");
printJobs.offer("Invoice.pdf");
String next = printJobs.poll();

A PriorityQueue removes the element with the smallest natural ordering, or according to a supplied comparator. It is not a fully sorted collection: iteration does not guarantee sorted order. Removing the priority element is typically O(log n).

A deque supports both ends and can implement a stack without the legacy Stack class:

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second

7. Iterators and Safe Modification

An iterator provides sequential traversal independent of the collection’s internal representation:

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

Iterator.remove() is the supported way to remove the last element returned by that iterator. Removing directly from a collection during an enhanced for loop can produce ConcurrentModificationException.

For modern code, removeIf is often clearer:

names.removeIf(String::isBlank);

Most standard collections are not synchronized. If several threads access a mutable collection, design for thread safety using suitable concurrent collections, synchronization, immutability, or confinement. ConcurrentHashMap is designed for concurrent map operations; it is not a general replacement for every synchronized map.

8. Ordering: Comparable and Comparator

Comparable<T> defines a type’s natural ordering through compareTo. A comparator returns a negative value, zero, or a positive value when its first argument is respectively less than, equal to, or greater than its second argument.

record Student(String name, double average) {}

List<Student> students = new ArrayList<>();
students.sort(Comparator.comparingDouble(Student::average)
                        .reversed()
                        .thenComparing(Student::name));

A comparator should be transitive and consistent. If a sorted set considers two objects equal according to its comparator, it may retain only one even when their equals methods say they differ. This is a common source of unexpected data loss.

Avoid subtraction-based comparators such as (a, b) -> a - b, because integer overflow can produce incorrect ordering. Use Integer.compare(a, b) or comparator factory methods instead.

9. Selecting a Collection

Selection should begin with requirements rather than habit.

Complexity is a guide, not a complete decision rule. Memory overhead, locality, ordering, concurrency, expected data size, and clarity also matter. Big-O notation describes growth as input size increases; it does not predict exact execution time on every machine.

10. Worked Application: A Course-Enrollment Service

Consider an illustrative course-enrollment service. It must prevent duplicate student identifiers, preserve the order in which students enroll, find a student by identifier, and process wait-listed students in first-in, first-out order.

A suitable design is:

record Student(String id, String name) {}

Set<String> enrolledIds = new LinkedHashSet<>();
Map<String, Student> studentsById = new HashMap<>();
Queue<Student> waitList = new ArrayDeque<>();

When a student enrolls, the service first checks capacity. If space exists, it attempts to add the identifier to enrolledIds. Because the set rejects duplicates, a repeated enrollment does not create a second enrollment. The student record is then placed in studentsById. If the course is full, the student is placed in waitList.

When a place becomes available, poll() removes the earliest waiting student. A production implementation should define transactional behavior so that updates to related structures cannot leave inconsistent state if an operation fails. It should also validate identifiers, protect personal information, and restrict access to authorized users.

Analysis

The set expresses uniqueness, the map expresses direct lookup, and the queue expresses waiting order. Using one list for all three responsibilities would require repeated searches and would obscure the business rules. The design also separates identity (id) from descriptive data (Student).

Learning points

1. A collection should express the rule it enforces.
2. Multiple collections may legitimately represent different views of the same domain data.
3. Correct equality and stable identifiers are essential.
4. Security and privacy requirements apply to collection contents, not only to databases.

11. Common Errors and Best Practices

Use interfaces in declarations, choose names that communicate the collection’s role, and specify initial capacity when a reliable estimate is available. Do not assume that a hash collection has stable order. Do not use a mutable object as a hash-map key if fields used by equals or hashCode may change after insertion.

Prefer immutable or unmodifiable results when callers should not alter internal state:

return List.copyOf(results);

This creates an unmodifiable list containing the current elements. It does not make mutable element objects themselves immutable.

Avoid raw types such as List values; they disable much of generic type checking. Also avoid unnecessary conversion between collections, repeated linear searches, and accidental exposure of internal mutable collections.

For concurrent programs, identify the required atomic operation. A thread-safe individual method does not automatically make a sequence of operations atomic. For example, “check then put” may require a map method such as computeIfAbsent or external synchronization.

Contemporary Practice

Modern Java development commonly uses records for simple immutable data carriers, factory methods such as List.of, and stream operations for expressive transformations. Streams do not replace collection knowledge: a stream is a processing pipeline, whereas a collection stores data. Parallel streams should be used only after measuring and confirming that the workload benefits from parallelism.

Artificial intelligence tools can suggest collection choices or code, but generated code must be reviewed for equality contracts, thread safety, privacy, complexity, and correctness. A tool may produce code that compiles while selecting an unsuitable data structure or exposing mutable state.

Chapter Summary

The Java Collections Framework provides abstractions for sequences, unique elements, associations, and processing order. Generics improve compile-time safety and reduce casts. ArrayList is a strong default for indexed sequences; sets express uniqueness; maps provide key-based lookup; queues and deques express processing order. Hash-based structures are generally efficient when equality and hashing are correct, while tree-based structures maintain sorted order at logarithmic cost. Iterators support traversal and controlled removal, and comparators provide flexible ordering. Effective collection selection considers semantics, expected operations, complexity, memory, ordering, and concurrency rather than relying on a single universal implementation.

Key Terms

Generic type: A type parameterized by one or more compile-time types.

Type parameter: A placeholder such as T used in generic declarations.

Wildcard: The ? notation representing an unknown generic type.

Collection: An object that groups multiple elements.

List: An ordered collection that may contain duplicates.

Set: A collection that does not contain duplicate elements.

Map: A key–value association structure.

Queue: A structure for processing elements in an order.

Deque: A double-ended queue supporting both ends.

Iterator: An object used to traverse a collection.

Equality: The rule determining whether two objects represent the same value for a context.

Hash code: An integer used to support hash-based lookup.

Natural ordering: The ordering defined by Comparable.

Comparator: An object or function defining an ordering externally.

Type erasure: Translation of generic code so type arguments are generally unavailable at run time.

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

Unmodifiable collection: A collection through which structural changes are not permitted.

Concurrent collection: A collection designed for specified patterns of multi-threaded access.

Review Questions

Short Answer Questions

1. What problem do generic types solve in Java collections?
2. How does a Set differ from a List?
3. Why is ArrayList usually suitable for indexed access?
4. What is the purpose of Iterator.remove()?
5. Why must equal objects have equal hash codes?

Long Answer Questions

1. Compare HashSet, LinkedHashSet, and TreeSet, including ordering and typical performance.
2. Explain the differences among HashMap, LinkedHashMap, and TreeMap.
3. Discuss Comparable and Comparator, including a situation in which each is useful.
4. Explain bounded wildcards using ? extends and ? super.
5. Describe the factors that should influence collection selection in a production application.

Analytical / Application Questions

1. Design collections for a library system that requires unique book ISBNs, lookup by ISBN, and a FIFO reservation list. Justify each choice.
2. A program repeatedly calls get(i) on a LinkedList inside a large loop. Diagnose the likely performance issue and propose a redesign.
3. A HashMap no longer finds an object after one of its fields changes. Explain why this can happen and recommend a safe design.

Multiple Choice Questions with Answers

Question 1

Which collection is designed to preserve insertion order while preventing duplicates?

A. HashSet

B. LinkedHashSet

C. TreeMap

D. ArrayList

Correct Answer: B. LinkedHashSet

Question 2

Which declaration maps student identifiers to student names?

A. Map<String, String>

B. List<String, String>

C. Set<String, String>

D. Queue<String, String>

Correct Answer: A. Map<String, String>

Question 3

What is the usual complexity of indexed access in an ArrayList?

A. O(log n)

B. O(n²)

C. O(1)

D. O(n log n)

Correct Answer: C. O(1)

Question 4

Which method removes and returns the next available queue element without throwing an exception when the queue is empty?

A. peek

B. poll

C. element

D. remove

Correct Answer: B. poll

Question 5

What is the primary purpose of a generic type such as List<String>?

A. To force alphabetical ordering

B. To provide compile-time type safety

C. To make all operations constant time

D. To synchronize the collection

Correct Answer: B. To provide compile-time type safety

Question 6

Which implementation maintains its elements in sorted order?

A. HashSet

B. ArrayList

C. TreeSet

D. ArrayDeque

Correct Answer: C. TreeSet

Question 7

Which interface defines an object’s natural ordering?

A. Runnable

B. Iterable

C. Comparable

D. Serializable

Correct Answer: C. Comparable

Question 8

What is the safest standard approach for removing matching elements during traversal?

A. Remove directly inside an enhanced for loop

B. Use Iterator.remove or removeIf

C. Clear the collection after every match

D. Cast the collection to a Map

Correct Answer: B. Use Iterator.remove or removeIf

Question 9

Why is a mutable object usually unsuitable as a HashMap key?

A. Maps cannot store objects

B. Its hash code may change after insertion

C. HashMap permits only strings as keys

D. Mutable objects are automatically sorted

Correct Answer: B. Its hash code may change after insertion

Question 10

Which collection is most appropriate for highest-priority removal rather than FIFO removal?

A. PriorityQueue

B. LinkedHashSet

C. ArrayList

D. HashMap

Correct Answer: A. PriorityQueue