Dynamic Arrays of Integers

Generic programming means writing code that works for many types of data instead of rewriting nearly identical code for each type.

Programming

Writing the Same Container Twice

Imagine you have written a working dynamic array for integers. It is a container that grows as you add items. Now you need the same thing for strings, then for decimal numbers, then for colors. The obvious first move is to copy the integer version, rename the class, and change the element type each time. That works, but it means you are copying the same logic over and over and editing one word each time.

Programmers find this tedious, and it causes a deeper problem: every copy must be maintained separately. A fix to the growing logic in one copy has to be made in all of them. Generic programming is the response to this situation. Its goal is to write the code once, in a form that works for many different types of data.

What do you think happens?

If an IntList and a StringList are copies of the same logic, what is the only thing that should differ between them?

The methods they contain
The name of the element type they store
The way they grow their storage
Nothing, they should be identical in every way

Reveal answer

Answer:

The name of the element type they store

The steps for adding an item, growing the storage, and reading an item back are the same in both. The only detail that differs is the type of item being stored.

Tracing the Copies Side by Side

Read the two versions below as a learner would, looking for what stays fixed and what moves. The first class stores integers. The second stores strings. Everything except the element type and the parameter name is the same.

java

class IntList {
    private int[] items = new int[10];
    private int size = 0;

    void add(int value) {
        items[size] = value;
        size++;
    }
}

class StringList {
    private String[] items = new String[10];
    private int size = 0;

    void add(String value) {
        items[size] = value;
        size++;
    }
}

class IntList {
    private int[] items = new int[10];
    private int size = 0;

    void add(int value) {
        items[size] = value;
        size++;
    }
}

class StringList {
    private String[] items = new String[10];
    private int size = 0;

    void add(String value) {
        items[size] = value;
        size++;
    }
}

Notes on the code

The two classes differ only in the element type: int in one, String in the other
The storage array, the size counter, and the add logic are otherwise identical
Storage growth is left out here for brevity; a real dynamic array repeats that logic too

Which parts of the integer version change when it is copied for strings, and which parts stay exactly the same?

Only the element type node differs between the two columns. The add, grow, and get steps carry over unchanged. This is the signal generic programming looks for: when two pieces of code differ only by a type name, the underlying idea is general and the type is an input that has not yet been abstracted away.

What Generic Programming Removes

Definition

Generic programming means writing code that works for many types of data instead of rewriting nearly identical code for each type.

The pattern generic programming targets is code that differs only by a type name. A dynamic array of int, a dynamic array of String, and a dynamic array of Color all follow the same steps for adding an item, growing the storage, and reading an item back. The type name is the only part that changes. Generic programming removes the need to write each copy by hand, so the logic lives in one place and the type becomes a parameter that the caller supplies.

Key point

The benefit is twofold: the code is written once, and a correction to the shared logic only has to be made once instead of in every type-specific copy.

Reading ArrayList<String> Piece by Piece

Java's approach to this problem is parameterized types. A class such as ArrayList leaves its element type open, and the caller fills in that type inside angle brackets. You will see it written as ArrayList<String>, ArrayList<Color>, or, when talking about the general form, ArrayList<T>.

In ArrayList<String>, which part is the general container and which part is the type parameter?

Read the expression from left to right. ArrayList names the general container. The angle brackets mark a slot. The text inside the brackets, here String, is the type parameter. It tells the container what kind of item it holds in this particular use. The type parameter is the part that changes between uses; the container itself does not.

java

ArrayList<String> names = new ArrayList<String>();
ArrayList<Color> palette = new ArrayList<Color>();

ArrayList<String> names = new ArrayList<String>();
ArrayList<Color> palette = new ArrayList<Color>();

Notes on the code

Both lines use the same ArrayList class
names holds String items; palette holds Color items
Only the text inside the angle brackets differs between the two declarations

One Class Serving Many Types

A common misreading is that ArrayList<String> and ArrayList<Color> are two different classes. They are not. There is only one ArrayList class. The type inside the angle brackets is what changes between uses. A single generic implementation is shared, and each use attaches a specific element type to it.

How does one generic class relate to the specific types it is used with?

The diagram shows the relationship. There is one generic class at the centre, and each specific type is a separate use of its type parameter. Adding a new element type does not require a new copy of the class's logic.

Tracing One Class Through Two Uses

Worked example

Following the Type Parameter Through a Program

A program creates an ArrayList<String> named names and an ArrayList<Color> named palette. Trace which parts are shared and which are specific to each use.

1
Identify the shared class
Both declarations use ArrayList. This is the single generic implementation the program depends on.
2
Identify the type parameter in each use
In names, the parameter is String. In palette, the parameter is Color. The angle-bracket slot is filled differently in each declaration.
3
Check the operations
Adding an item and reading an item back follow the same steps in both lists. Only the kind of item being stored differs.
4
Conclude what generic programming provided
The container logic was written once. Each list gets its specific behaviour by supplying a different type parameter.

Result

One class serves both lists. The only per-use difference is the type parameter written inside the angle brackets.

Mistakes Learners Make With Type Parameters

Common mistake
Believing ArrayList<String> and ArrayList<Color> are separate classes
What it looks like
Assuming you must write a new ArrayList implementation for every element type.
Why it fails
There is only one ArrayList class. The type inside the angle brackets is what changes between uses.
Do this instead
Treat the angle-bracket text as a parameter supplied to the one shared class.
Common mistake
Treating the type parameter as a second container
What it looks like
Reading ArrayList<String> as if String were a list that is wrapped inside another list.
Why it fails
The text inside the brackets names the element type stored in the container. It does not add a container layer.
Do this instead
Read ArrayList as the container and String as the kind of item it holds.
Common mistake
Copying a type-specific class whenever a new element type appears
What it looks like
Creating a separate StringList and ColorList by copying IntList and renaming the type.
Why it fails
This repeats the same logic in several places, so every later fix must be made in each copy.
Do this instead
Recognise that code differing only by a type name is the pattern generic programming removes, and write the shared logic once.

Practice Removing the Duplicate

EASY

You have two classes: one holds int items and one holds String items. Both have an add method, a grow method, and a get method, and their code differs only in the element type. Describe in words what single generic class you would write instead, and state which part of its declaration would be the type parameter.

Hints

Ask which parts of the two classes are identical and which part differs.
The differing part is the element type. Decide what name you would give to the placeholder that stands in for it.
Think about how a caller would then specify the element type, using the same angle-bracket notation as ArrayList<String>.

Your attempt (not saved)

Key Takeaways

Generic programming means writing code that works for many types of data instead of rewriting nearly identical code for each type.
Code that differs only by a type name, such as dynamic arrays of int, String, or Color, is the repeated pattern generic programming removes.
Java uses parameterized types: ArrayList leaves its element type open and is used as ArrayList<String>, ArrayList<Color>, or the general form ArrayList<T>.
There is only one ArrayList class; the type inside the angle brackets is the type parameter that changes between uses.