Collections framework and generics notes — Unit 3

Arrays in Java have a fixed size. Once created, you cannot dynamically add or remove elements. The Java Collections Framework (JCF) solves this by providing a unified architecture to store, manipulate, and search dynamic groups of objects.

⇒1.1 The Core Hierarchy

The framework is primarily based on two root interfaces in the `java.util` package:

• `Collection`: The root of the hierarchy for Lists, Sets, and Queues.
• `Map`: A separate hierarchy for Key-Value pairs (like dictionaries).

Before Java 5, Collections stored pure `Object` types. This meant you could accidentally put a String and an Integer into the same List, causing a runtime crash when you tried to pull them out. Generics solve this by providing Compile-Time Type Safety.

⇒2.1 Syntax

Generics use angle brackets `< >` to specify the exact type a collection is allowed to hold.

A List is an ordered collection (sequence). It allows duplicate elements. You can access elements by their integer index.

⇒3.1 ArrayList

Backed by a dynamic array. Best for situations where you read data frequently, but don't insert/delete from the middle often.

• Fast random access `O(1)`.
• Slow insertion/deletion in the middle `O(n)` because elements must be shifted.

⇒3.2 LinkedList

Backed by a doubly-linked list. Best for situations where you frequently insert/delete data from the middle.

• Slow random access `O(n)`.
• Fast insertion/deletion `O(1)` once the node is located.

A Set is a collection that cannot contain duplicate elements. It models the mathematical set abstraction.

⇒4.1 HashSet

Backed by a Hash Table. The most commonly used Set.

• Extremely fast `O(1)` for add, remove, and contains operations.
• Elements are strictly unordered. You cannot guarantee the order they will print out.

⇒4.2 TreeSet

Backed by a Red-Black Tree.

• Slower `O(log n)` operations.
• Elements are automatically sorted (natural order, e.g., alphabetical).

Maps store data in Key-Value pairs. Keys must be unique, but values can be duplicated. (Note: Map does not inherit from the Collection interface).

⇒5.1 HashMap

The standard Map implementation. Unordered, `O(1)` lookup time. Allows one `null` key and multiple `null` values.

⇒5.2 TreeMap

A Map that automatically sorts its keys in ascending order.

An Iterator is an object used to loop through collections.

⇒6.1 Why use an Iterator?

If you try to remove an element from an ArrayList while looping through it using a standard `for` loop, you will crash the program with a `ConcurrentModificationException`. Iterators solve this.

If you have a List of Strings, `Collections.sort(list)` knows to sort them alphabetically. But if you have a List of `Student` objects, how does Java know whether to sort them by ID, Name, or Grade?

⇒7.1 Implementing Comparable

You make the `Student` class implement `Comparable<Student>` and override the `compareTo` method. This defines the Natural Ordering of the class.

What if you want to sort Students by ID sometimes, and by Name other times? You cannot use `Comparable` because it only allows one natural order. You must use `Comparator`.

⇒8.1 External Sorting Logic

Comparators are separate classes (or lambdas) passed directly to the sort method.

This is vastly preferred in modern Java because it decouples the sorting logic from the class itself.

The Streams API revolutionized how Collections are processed, allowing for declarative, functional-style operations (filter, map, reduce).

⇒9.1 What is a Stream?

A Stream is not a data structure. It does not store data. It is a pipeline that takes input from a Collection, processes it, and produces an output.

Stream pipelines are lazily evaluated. This means the processing doesn't actually begin until a Terminal operation is called.

⇒10.1 Intermediate Operations

These operations return another Stream, allowing you to chain them together.

• `filter(Predicate)`: Removes elements that don't match.
• `map(Function)`: Transforms elements.
• `sorted()`: Sorts the stream.

⇒10.2 Terminal Operations

These operations consume the stream and produce a final result. Once a terminal operation executes, the stream is closed and cannot be reused.

• `collect(Collectors.toList())`: Packs the result back into a List.
• `forEach(Consumer)`: Executes logic for each element.
• `count()`: Returns the number of elements.

You are not limited to using Generics in Collections; you can build your own Generic classes.

⇒11.1 The `<T>` Type Parameter

Common conventions: `T` (Type), `E` (Element), `K` (Key), `V` (Value).

Sometimes you want to restrict the types that can be passed into a Generic class. For example, a MathCalculator class should only accept Number types (Integer, Double), not Strings.

⇒12.1 The `extends` Keyword in Generics

Wildcards are used when you want a method to accept a collection of an unknown type.

⇒13.1 The Unbounded Wildcard

`List<?>` means a list of any type. Useful for methods that only read from the list and don't care about the type (like a method that prints the list size).

⇒13.2 Upper Bounded Wildcards

`List<? extends Number>` accepts a List of Numbers, or a List of Integers, or a List of Doubles. Read-only: You can read Numbers from it, but you cannot add anything to it because the compiler doesn't know the exact subtype.

⇒13.3 Lower Bounded Wildcards

`List<? super Integer>` accepts a List of Integers, or a List of Numbers, or a List of Objects. Write-only: You can safely add Integers to it.

Java Generics are a compile-time illusion. To maintain backward compatibility with older Java versions, the JVM knows nothing about Generics.

⇒14.1 How it works

When you compile `List<String>`, the compiler checks for safety, but then it completely erases the `<String>` part. The generated bytecode just uses raw `List` and casts the objects to Strings internally when you retrieve them.

Because of Type Erasure, you cannot do things like `T obj = new T();` or `if (obj instanceof T)`, because `T` does not exist at runtime.

Do not confuse the `Collection` interface with the `Collections` utility class. The latter contains static methods that operate on or return collections.

⇒15.1 Useful Methods

• `Collections.sort(list)`: Sorts a list.
• `Collections.reverse(list)`: Reverses the order of a list.
• `Collections.shuffle(list)`: Randomizes the list.
• `Collections.max(collection)`: Returns the largest element.
• `Collections.unmodifiableList(list)`: Returns a read-only view of the list.

The `Properties` class is a subclass of `Hashtable`. It is unique because it is heavily used for reading configuration data from files.

⇒16.1 Key Characteristics

Both keys and values in a Properties object are strictly Strings.

Before the JCF was introduced in Java 1.2, Java used older data structures. They were retrofitted to implement the new interfaces, but are generally avoided in modern code.

⇒17.1 Vector

Similar to `ArrayList`, but every single method is synchronized (thread-safe). This makes it significantly slower. Modern developers use `ArrayList` for single-threaded tasks, or `CopyOnWriteArrayList` for multithreaded tasks.

⇒17.2 Hashtable

Similar to `HashMap`, but fully synchronized and does not allow `null` keys or values. Replaced by `ConcurrentHashMap` in modern concurrent programming.

A Deque (Double Ended Queue) allows insertion and removal at both ends.

⇒18.1 ArrayDeque vs Stack

Historically, Java provided a `Stack` class (LIFO) that inherited from `Vector`, meaning it suffered from the same slow synchronization overhead. The official Java documentation now recommends using `ArrayDeque` when you need a Stack.

A normal Queue operates strictly FIFO (First In, First Out). A PriorityQueue orders elements based on their priority (either natural ordering or a custom Comparator).

⇒19.1 Implementation Details

Backed by a Heap data structure. When you `poll()` a PriorityQueue, you don't get the element that was inserted first; you get the 'smallest' (or highest priority) element in the queue.

It is widely used in pathfinding algorithms (like Dijkstra's) or task scheduling systems where urgent tasks jump the queue.

Exam questions frequently ask you to justify which collection to use in a given scenario based on Time Complexity (Big-O).