Data structures and collections help us organize data in our program. For example, the
TreeSet class is a collection data structure that always keep the objects sorted, and the
Stack class always keep the last object added at the front. Both classes are data structures built into the Java standard library
When we write a data structure or an algorithm, it may be useful to keep them generic so that the same data structure can be used for different data types. Generics is a feature in Java allows us to write generic algorithms and data structures, and at the same time offers type-safety at compile time. In fact, both
Stack implement generics. In this article, we see how generics work and how to write general data structures. Generics was added in Java 5 (1.5).
It is possible to write generic collections without generics. Before the introduction of generics in Java 1.5, built-in collections use the most general data type, the
Object class. As we mentioned in the article Java Inheritance, every class inherits from the
Object class, so any type can be stored in these collections that take object of
Object as data type.
For example, the
ArrayList class before Java 1.5 may have methods similar to the following that work with objects of
This approach works fine; however, if a programmer is not careful and add an object of the wrong type into the list, an error is introduced. The follow example program outputs the length of a list of String objects, but because an object of Integer was added to the list, the program exited with exception.
Output: Length of Hello is 5 Length of good is 4 Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String at ObjectList.main(ObjectList.java:7)
Notice that the compiler did not catch this type-safety error because the list takes data of type
Object. Since both
Integer are of type
Object, this program is perfectly legal for the compiler.
What we need is to keep our collections generic so it can be used with any types, but also be able to specify the type we will add to the collection so that the compiler can check it for us. This is how Java generics work.
Generic programming (using generics) is accomplished using type parameters. A type parameter is a placeholder in our class for a data type. When someone uses our generic class, that person will specify the actual type and replace the type parameter. This concept is similar to method parameter variables, which are placeholders for actual values that are passed in when a method is called. Type parameters are defined using <>.
The following example defines a simple generic class,
Node, which defines one type parameter
Note that because the type parameter
<T> is defined at the class level, it can be used throughout the class.
Generic Type Instantiation
During instantiation, we specify the actual type for type parameters. However, only reference types can be used. If you want to put a primitive data type in a generic collection, you’ll have to use one of the wrapper classes.
The following code uses our generic
<Integer> to specify the type we want to use and to replace the type parameter
As we mentioned earlier with generics, compiler actually checks for correct type for us. For example, the following does not compile, because we intend to use
Integer, but we’re passing in a
String into our constructor.
error: constructor Node in class Node<T> cannot be applied to given types; Node<Integer> node = new Node<Integer>("Hello", null); ^ required: Integer,Node found: String,<null>
The compiling error basic says that the
Node class requires an
Integer, but a
String is found.
Bounded Type Parameter
When we define a type parameter, any type can be used to take place of the type parameter. However, Java also allow us to limit the types we can use as parameter through
extends keyword. This is called bounded type parameters.
The following example shows a generic
Node class that only takes numeric types (types that extends Number class: Integer, Float, Long, Double, etc).
The following version of the
Node class only take types that implements the
Note that the
Comparable interface is also an generic interface, so that we need to use
Comparable<T> to bind a type.
Methods can also be generic. The following generic method finds the index of
target in the array
target is not found, -1 is returned.
Two things to notice:
- Notice the syntax to define type parameters for a method is slightly different from the syntax for a class (or interface).
<T>is only defined at the method level, so it’s only accessible in the compare method.
The following code calls the
Output: Target is found at index 1