Generics

Why generics?

Before Java 5, collections stored Object. You could put anything in, and you had to cast on the way out:

class ObjectBox {
    private Object item;
    ObjectBox(Object item) { this.item = item; }
    Object get() { return item; }
}

ObjectBox b = new ObjectBox("text");
String s = (String) b.get();        // cast needed
Integer n = (Integer) b.get();      // compiles, fails at run time: ClassCastException

A generic type has a type parameter that the user fills in. The compiler then checks every use and inserts the casts for you:

class Box<T> {                      // T = type parameter
    private T item;
    Box(T item) { this.item = item; }
    T get() { return item; }
    void set(T item) { this.item = item; }
}

Box<String> b = new Box<>("hi");    // String = type argument
String s = b.get();                 // no cast
b.set(42);                          // compile-time error: int is not a String

What the compiler does, step by step. When you write Box<String>, the compiler reads the class as if every T were String:

In the class	For Box<String> it means	Effect
T item	String item	the box holds a String
T get()	String get()	get() returns a String: no cast
void set(T item)	void set(String item)	set(42) is rejected at compile time

The type parameter is the placeholder name (T) in the class. The type argument is the real type (String) that you write when you use the class — like a parameter and an argument of a method.

Generics move errors from run time to compile time, remove casts, and let one class (such as ArrayList<E>) serve every element type. All the data structures in this course will be generic.

Generic classes and the diamond

A class may have several type parameters:

class Pair<K, V> {
    private final K key;
    private final V value;
    Pair(K key, V value) { this.key = key; this.value = value; }
    K getKey()   { return key; }
    V getValue() { return value; }
}

Pair<String, Integer> p = new Pair<>("age", 20);
int age = p.getValue();             // auto-unboxing of Integer

Here K = String and V = Integer, so getKey() returns a String and getValue() returns an Integer, which Java automatically converts to int (auto-unboxing).

The diamond <> (Java 7+) lets the compiler infer the type arguments of the constructor call from the declared type: Map<String, List<Integer>> m = new HashMap<>();. The diamond goes on the new expression, never on the declared type (ArrayList<> x is illegal).

Type arguments must be reference types: List<int> does not compile; use the wrapper List<Integer> and let autoboxing convert.

Primitive	Wrapper to use as a type argument
int	Integer
double	Double
char	Character
boolean	Boolean
long	Long

Naming conventions

Type parameters are single upper-case letters, so that they cannot be confused with class names:

Letter	Usual meaning	Example
E	element of a collection	List<E>, Set<E>
K, V	key, value	Map<K, V>
T	any type	Box<T>, Comparable<T>
S, U	second, third type	<T, U> Pair<T, U> zip(...)
N	number	<N extends Number>

The letters are only a convention: the compiler would accept Box<Thing>, but readers would think Thing is a real class.

Generic interfaces

An interface can be generic too. A class implementing it chooses a type argument (or stays generic itself):

interface Container<T> {
    T get();
    void put(T item);
}

class IntBox implements Container<Integer> {      // fixes T = Integer
    private Integer v = 0;
    public Integer get() { return v; }
    public void put(Integer item) { v = item; }   // must be put(Integer), not put(Object)
}

class ListContainer<T> implements Container<T> { ... }   // stays generic

You already know the most important generic interface: Comparable<T>, with int compareTo(T other). When String says implements Comparable<String>, its compareTo takes a String — no cast from Object is needed.

Generic methods

A method can declare its own type parameters, written before the return type:

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

Integer[] nums = {1, 2, 3};
swap(nums, 0, 2);                    // T inferred as Integer
Util.<String>first(names);           // explicit type argument (rarely needed)

How inference works. You normally do not write the type argument of a method. The compiler looks at the arguments and works it out:

1. swap(nums, 0, 2) — nums is an Integer[].
2. The parameter type is T[], so T[] must match Integer[].
3. Therefore T = Integer. After the call, nums is {3, 2, 1}.

The order is: modifiers, <T>, return type, name. public static void <T> swap(...) and public <T> static void swap(...) do not compile. Because T must be a reference type, swap accepts an Integer[] but not an int[].

public static  <T>   void   swap (T[] a, int i, int j)
└── modifiers ─┘ │     │      │
                 │     │      └── method name
                 │     └── return type
                 └── type parameter: always just before the return type

A static method cannot use the type parameter of its class (class Box<T> { static T make() ... } is illegal: T belongs to an instance). It must declare its own: static <U> Box<U> of(U item).

Bounded type parameters

To call compareTo on a T, the compiler must know that every T has that method. A bound says so:

public static <T extends Comparable<T>> T max(T a, T b) {
    return a.compareTo(b) >= 0 ? a : b;
}

max(3, 7)             // 7          (T = Integer)
max("pear", "apple")  // "pear"     (T = String)
max(3, "x")           // compile-time error: no T is both

Worked example: max("pear", "apple").

Step	What happens
1	Both arguments are String, so the compiler chooses T = String.
2	Check the bound: does String implement Comparable<String>? Yes → the call compiles.
3	At run time: "pear".compareTo("apple") is positive (p comes after a).
4	Positive is >= 0, so the method returns a, which is "pear".

Without the bound (<T> T max(T a, T b)), the line a.compareTo(b) would not compile: an unknown T might be a type with no compareTo method at all.

In a bound, extends means "is a subtype of", for classes and interfaces alike (implements is never used here). Several bounds are joined with &, and a class bound must come first: <T extends Number & Comparable<T>>.

Generics are invariant

Integer is a subtype of Number, but List<Integer> is not a subtype of List<Number>, and List<String> is not a List<Object>:

List<Object> objs = new ArrayList<String>();    // compile-time error

If it were allowed, objs.add(42) would put an Integer into a list of strings. Arrays made the opposite choice (they are covariant) and pay for it at run time:

Object[] arr = new String[2];   // compiles
arr[0] = 1;                     // ArrayStoreException at run time

Invariant means "no subtype relation between List<A> and List<B>, even if A and B are related". Covariant means "if A is a subtype of B, then A[] is a subtype of B[]".

Integer   is-a  Number           ✓
Integer[] is-a  Number[]         ✓   (arrays are covariant: checked at run time)
List<Integer> is-a List<Number>  ✗   (generics are invariant: checked at compile time)

Wildcards

A wildcard ? stands for "some unknown type" and gives back the flexibility invariance takes away:

Parameter type	Accepts	You can read as	You can add
List<?>	any list	Object	only null
List<? extends Number>	List<Number>, List<Integer>, List<Double> …	Number	only null
List<? super Integer>	List<Integer>, List<Number>, List<Object>	Object	Integer

static double sum(List<? extends Number> xs) {          // producer: we only read
    double s = 0;
    for (Number n : xs) s += n.doubleValue();
    return s;
}

static void fillWith(List<? super Integer> dst, int n) { // consumer: we only add
    for (int i = 1; i <= n; i++) dst.add(i);
}

Why these rules? Reason with the worst case.

• A List<? extends Number> might really be a List<Integer>, or a List<Double>. Whatever it is, every element is some kind of Number, so reading a Number is always safe. But adding an Integer would be wrong if the list is really a List<Double> — and the compiler cannot know — so adding is forbidden.
• A List<? super Integer> might really be a List<Integer>, List<Number> or List<Object>. All three can safely hold an Integer, so adding is allowed. But when you read, the element could be any Object (maybe a String in a List<Object>), so you only get Object.

Worked example: which lines compile? (checked with javac)

Code	Compiles?	Why
sum(Arrays.asList(1, 2, 3))	yes → 6.0	a List<Integer> is a producer of Numbers
sum(Arrays.asList(1.5, 2.5))	yes → 4.0	a List<Double> too
fillWith(new ArrayList<Number>(), 3)	yes → [1, 2, 3]	a List<Number> can hold Integers
fillWith(new ArrayList<Object>(), 2)	yes → [1, 2]	so can a List<Object>
inside sum: xs.add(Integer.valueOf(5))	no	xs might be a List<Double>
inside fillWith: Integer i = dst.get(0)	no	get only gives an Object
List<?> xs; xs.add("x")	no	the element type is unknown; only null fits

The rule of thumb is PECS: Producer extends, Consumer super. If a parameter produces values that you read, use ? extends T; if it consumes values that you write, use ? super T; if it does both, use plain T. The library's copy method is the textbook example:

static <T> void copy(List<? super T> dst, List<? extends T> src) {
    for (T t : src) dst.add(t);
}

With src a List<Integer> and dst a List<Object>, the call works with T = Integer: src produces Integers, and dst can consume them.

            src (produces)                      dst (consumes)
  List<? extends T>  ──── read T ────>  T  ──── add T ────>  List<? super T>
  e.g. List<Integer>                          e.g. List<Object>

Raw types

Using a generic type without type arguments (List, ArrayList) gives a raw type. It exists only for compatibility with pre-2004 code. The compiler stops checking and only emits an unchecked warning:

List<String> names = new ArrayList<>();
List raw = names;           // raw alias of the same list
raw.add(42);                // compiles (warning); the list now holds an Integer
String s = names.get(0);    // ClassCastException here, far from the real mistake

Step by step:

Step	Line	State of the one list object	What the compiler/JVM says
1	names = new ArrayList<>()	[]	fine
2	raw = names	[] (two variables, one list)	fine
3	raw.add(42)	[42]	only a warning: raw types are not checked
4	names.get(0)	[42]	the hidden cast to String fails: ClassCastException

The bug is on line 3, but the program crashes on line 4 — possibly in a completely different method. This situation (a List<String> that contains an Integer) is called heap pollution.

Never write raw types in new code. If you truly do not care about the element type, write List<?>, which is still type-safe.

Type erasure

Generics are a compile-time feature. After checking, the compiler erases the type parameters: each T becomes its bound (Object when there is none, Comparable for <T extends Comparable<T>>) and casts are inserted where values come out. At run time a List<String> and a List<Integer> are both just ArrayList:

new ArrayList<String>().getClass() == new ArrayList<Integer>().getClass()   // true

What erasure does to Box<T>:

What you write                     What the JVM runs (after erasure)
--------------------------------   ------------------------------------
class Box<T> {                     class Box {
    private T item;                    private Object item;
    T get() { return item; }           Object get() { return item; }
}                                  }

Box<String> b = new Box<>("hi");   Box b = new Box("hi");
String s = b.get();                String s = (String) b.get();   // cast inserted

That inserted cast is why the raw-type example above fails exactly on the get line.

Consequences you must know:

Not allowed	Why	Workaround
new T()	the run-time type of T is unknown	pass a factory or a Class<T>
new T[10], new List<String>[10]	arrays must know their element type	(T[]) new Object[10] kept private, or an ArrayList<T>
List<int>	erasure needs a reference type	List<Integer>
x instanceof List<String>	the type argument no longer exists	x instanceof List<?>
static T field; in Box<T>	one static field is shared by all Box<…>	make it an instance field
void f(List<String>) and void f(List<Integer>) in one class	same erasure f(List): name clash	use different names

A good way to remember the whole table: ask "does this need to know T while the program runs?" If yes, it is not allowed, because at run time T has been erased.

Key takeaways

• Generics = labelled boxes: the compiler checks every use, removes casts, and moves errors from run time to compile time.
• <T> on a class goes after the class name; on a method it goes just before the return type. Use <> (the diamond) on new.
• Type arguments must be reference types: List<Integer>, never List<int>.
• A bound <T extends Comparable<T>> lets you call compareTo on T; in bounds, extends covers interfaces too.
• Generics are invariant: List<Integer> is not a List<Number>. Arrays are covariant and fail at run time with ArrayStoreException.
• PECS: read from ? extends T (producer), add to ? super T (consumer), use plain T for both.
• Raw types switch the checks off: they cause warnings and late ClassCastExceptions. Use List<?> instead.
• Type erasure removes T after compilation, so anything that needs T at run time (new T(), new T[], instanceof List<String>) is illegal.