10. Generics Lesson

Java Generics

Java Generics

To see sample solutions, click on the "Configure activity" button and select "Show solutions" from the menu that appears.

Sample solutions not included, because "Show solutions" was not selected before printing.

Lesson Objectives

Use Node<ItemType> to interpret and manipulate linked lists. By the end of this lesson, you should be able to distinguish type parameters from type arguments, explain why different parameterizations are not interchangeable, write generic methods, and use a type bound to make an ordering operation available.

Predict each result before opening its solution. In execution diagrams, the highlighted line is the next line to execute. A method parameter receives a copy of an argument's value; copying a reference value does not copy the object. Type arguments constrain source-level operations; they do not create a separate runtime class for each parameterization.

Part 1: Motivation

Getting Started: Removing Method Redundancy

Is there a better way to write code to print stars than what is presented below? Discuss with your groups. What would you do instead? If you have an alternative, discuss why yours is better.

Example Code

public static void printFourStars() {
   for (int i = 0; i < 4; i++) {
      System.out.print("*");
   } // for
   System.out.println();
} // printFourStars

public static void printFiveStars() {
   for (int i = 0; i < 5; i++) {
      System.out.print("*");
   } // for
   System.out.println();
} // printFiveStars

Sample Solution

public static void printStars(int count) {
   for (int i = 0; i < count; i++) {
      System.out.print("*");
   } // for
   System.out.println();
} // printStars

Factor out the common code into a single method that uses a method parameter so that callers can supply different values, as needed!

Motivating Example: Removing Class Redundancy

GOAL: Imagine we want to create a linked list that can store items with a datatype other than String. For example, maybe you are implementing a playlist (of type Song) or a wait list (of type Person).

ONE IDEA: You might be tempted to create multiple versions of the Node class as seen below:

SVG PNG

What is problematic about this approach?

We have multiple files with essentially the same code!

The class names (and constructors) and datatypes for item and next are different, but everything else is the same.

Can an interface or inheritance relationship help?

The getters have the same method names and parameter lists. A method's return type is not part of its signature. An interface or superclass could provide a common API, but using Object for items would lose the specific item type at the call site. Generics let one implementation preserve the relationship between the item type and the node type.

What can we do?

GENERICIZE: Factor out the differences into a single generic class with a type parameter.

This is the same thing we saw with the method example, but instead of factoring out a value into a parameter, you factor out a type into a parameter using Java's generics syntax.

Solution: Removing Class Redundancy

Instead of creating separate classes for each type, Generics allow us to create a single generic class with a type parameter.

Without Generics

SVG PNG

With Generics

SVG PNG

Note

We won't implement this in class - we implement a similar class (ShippingContainer) in the "Generic Classes" video assigned earlier this week.

• When the generic class is used, we parameterize it – that simply means that we supply a type argument for its type parameter. This is similar to how we supply an argument for a method parameter when calling a method.

• Therefore, a type parameter is essentially a variable for a type, and a type argument is a specific type that we supply for a type parameter.

Can you name all of the type parameters declared by Node?

• There is only one type parameter.

• The name of that type parameter is ItemType.

Part 2: Code Interpretation

Activity: Code Interpretation (1)

What is the output of the code below?

SVG PNG

Important

Assume the Person class exists and has a constructor that takes the name of the person. You can also assume it has a getter and setter for name.

Node<String> head1 = null;
head1 = new Node<String>("a", head1);
head1 = new Node<String>("b", head1);

System.out.println(head1.getItem());

Person joe = new Person("Joe");
Person sally = new Person("Sally");

Node<Person> head2 = new Node<Person>(sally);
head2.setNext(new Node<Person>(joe));
Node<Person> tail2 = head2.getNext();

System.out.println(tail2.getItem().getName());

Solution

Advance to the final step to see the complete output.

|< < Prev

Step 1 of 2: Interpretation.java:13

Next > >|

12

Memory state at the breakpoint on line 13 in Interpretation.java. [download] [open]

b

>_ Console Output

Memory state at the breakpoint on line 19 in Interpretation.java. [download] [open]

b
Joe

>_ Console Output

The two lists have different item types. tail2 and head2.getNext() refer to the same node; that node's item reference value refers to the same person as joe.

Activity: Code Interpretation (2)

Consider each example independently. Does it compile? Does it preserve generic type safety? Explain any error or use of a raw type before opening that example's sample solution.

SVG PNG

Important

Assume Person has a constructor that takes a name, along with a getter and setter for name. Each example includes all the variable declarations it needs.

Example 1

Node head1 = null;

Sample Solution

This compiles, but Node is a raw type. Use a parameterized type to preserve generic type checking. The value of head1 is null, which means it does not refer to an object.

Node head1 = null;

Final captured memory state. [code listing] [download] [open]

Example 2

Node<String> head2 = new Node<>("A");

Sample Solution

This compiles and preserves generic type safety. Java infers String for the diamond <>. The node stores an item reference value that refers to the string "A".

Node<String> head2 = new Node<>("A");

Final captured memory state. [code listing] [download] [open]

Example 3

Node<Person> head3 = new Node<>(4.2);

Sample Solution

This does not compile. The target type requires Person as the item type, but boxing 4.2 produces a Double reference value. These requirements cannot be satisfied by the same type argument.

Node<Person> head3 = new Node<>(4.2);

Compiler error (expected)

Driver.java:4: error: incompatible types: cannot infer type arguments for Node<>
        Node<Person> head3 = new Node<>(4.2);
                                     ^
    reason: inference variable ItemType has incompatible bounds
      equality constraints: Person
      lower bounds: Double
  where ItemType is a type-variable:
    ItemType extends Object declared in class Node
1 error

Example 4

Node<Person> head4 = new Node<Person>(new Person("Joe"));

Sample Solution

This compiles and preserves generic type safety. The node stores an item reference value that refers to the newly constructed person.

Node<Person> head4 = new Node<Person>(new Person("Joe"));

Final captured memory state. [code listing] [download] [open]

Example 5

Node<Person> head4 = new Node<Person>(new Person("Joe"));
String val = head4.getItem();

Sample Solution

The declaration of head4 is valid, but the assignment to val does not compile. Here, getItem has return type Person; its result is not assignment-compatible with String.

Node<Person> head4 = new Node<Person>(new Person("Joe"));
String val = head4.getItem();

Compiler error (expected)

Driver.java:5: error: incompatible types: Person cannot be converted to String
        String val = head4.getItem();
                                  ^
1 error

Example 6

Node<Person> head4 = new Node<Person>(new Person("Joe"));
head4.setNext(new Node<String>("Sally"));

Sample Solution

The declaration of head4 is valid, but the setNext call does not compile. It requires a Node<Person> reference value; a Node<String> reference value is incompatible.

Node<Person> head4 = new Node<Person>(new Person("Joe"));
head4.setNext(new Node<String>("Sally"));

Compiler error (expected)

Driver.java:5: error: incompatible types: Node<String> cannot be converted to Node<Person>
        head4.setNext(new Node<String>("Sally"));
                      ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

Example 7

Node<Double> head5 = new Node<Double>(4.2);

Sample Solution

This compiles and preserves generic type safety. Boxing converts the primitive double value 4.2 to a reference value that refers to a Double object. The node stores that reference value.

Node<Double> head5 = new Node<Double>(4.2);

Final captured memory state. [code listing] [download] [open]

Example 8

Node<Double> head5 = new Node<Double>(4.2);
head5.setItem("ABC");

Sample Solution

The declaration of head5 is valid, but the setItem call does not compile. It requires a Double reference value; a String reference value is incompatible.

Node<Double> head5 = new Node<Double>(4.2);
head5.setItem("ABC");

Compiler error (expected)

Driver.java:5: error: incompatible types: String cannot be converted to Double
        head5.setItem("ABC");
                      ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

Example 9

Node head6 = new Node("Sally");

Sample Solution

This compiles, but uses raw types and produces an unchecked constructor-call warning. It bypasses the generic item-type check. The visualization shows a node storing a reference to "Sally"; successful execution does not establish generic type safety.

Node head6 = new Node("Sally");

Final captured memory state. [code listing] [download] [open]

Better Solution (1)

Choose Object for ItemType to preserve generic type checking without raw types. This permits a heterogeneous linked list: item reference values may refer to strings, people, and other objects, or they may be null. Each next-node field still has type Node<Object>.

The getter method getItem has return type Object, so direct method calls on head6.getItem() must use methods declared by Object. The example uses toString and prints Sally; calling length or getName directly on that expression would not compile.

|< < Prev

Step 1 of 3: line 4

Next > >|

123

Node<Object> head6 = new Node<Object>("Sally");
System.out.println(head6.getItem().toString());

Node<Object> head6 = new Node<Object>("Sally");
System.out.println(head6.getItem().toString());

Memory state at the breakpoint on line 4. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Node<Object> head6 = new Node<Object>("Sally");
System.out.println(head6.getItem().toString());

Memory state at the breakpoint on line 5. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Node<Object> head6 = new Node<Object>("Sally");
System.out.println(head6.getItem().toString());

Memory state at the breakpoint on line 6. [code listing] [download] [open]

Sally

>_ Console Output

Better Solution (2)

Choose String for ItemType when each non-null item reference value should refer to a String object. This does not permit heterogeneous item types: String is final, so it has no subclasses. The getter method getItem has return type String, so string methods such as length and inherited Object methods such as getClass are available without a cast. The example calls length and prints 5.

|< < Prev

Step 1 of 3: line 4

Next > >|

123

Node<String> head6 = new Node<String>("Sally");
System.out.println(head6.getItem().length());

Node<String> head6 = new Node<String>("Sally");
System.out.println(head6.getItem().length());

Memory state at the breakpoint on line 4. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Node<String> head6 = new Node<String>("Sally");
System.out.println(head6.getItem().length());

Memory state at the breakpoint on line 5. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Node<String> head6 = new Node<String>("Sally");
System.out.println(head6.getItem().length());

Memory state at the breakpoint on line 6. [code listing] [download] [open]

5

>_ Console Output

Better Solution (3)

Choose Person for ItemType to preserve generic type checking without raw types. Each non-null item reference value must then refer to a Person object or an object of one of its subclasses. The getter method getItem has return type Person, so callers can use the getter method getName and setter method setName without a cast. The example prints Sally.

A domain class can define additional convenience methods for the operations its users need. This lesson's Person class provides getName and setName for working with a person's name.

|< < Prev

Step 1 of 3: line 4

Next > >|

123

Node<Person> head6 = new Node<Person>(new Person("Sally"));
System.out.println(head6.getItem().getName());

Node<Person> head6 = new Node<Person>(new Person("Sally"));
System.out.println(head6.getItem().getName());

Memory state at the breakpoint on line 4. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Node<Person> head6 = new Node<Person>(new Person("Sally"));
System.out.println(head6.getItem().getName());

Memory state at the breakpoint on line 5. [code listing] [download] [open]

> (no output yet)

>_ Console Output

Node<Person> head6 = new Node<Person>(new Person("Sally"));
System.out.println(head6.getItem().getName());

Memory state at the breakpoint on line 6. [code listing] [download] [open]

Sally

>_ Console Output

Example 10

SVG PNG

Node<Number> head7 = new Node<Double>(2.0);

Sample Solution

This does not compile. Although Double extends Number, Node<Double> is not a child of Node<Number>. Java's generic types are invariant: an inheritance or interface relationship between type arguments does not establish the same relationship between parameterized types that incorporate them.

Node<Number> head7 = new Node<Double>(2.0);

Compiler error (expected)

Driver.java:4: error: incompatible types: Node<Double> cannot be converted to Node<Number>
        Node<Number> head7 = new Node<Double>(2.0);
                             ^
1 error

Example 11

SVG PNG

Integer i = 42;
Double d = 12.5;

Node<Number> head8 = new Node<Number>(i);
head8 = new Node<Number>(d, head8);

Sample Solution

This compiles and preserves generic type safety. Boxing supplies the Integer and Double reference values stored in i and d. Both classes extend Number, so both reference values are compatible with the item type of Node<Number>.

Step through the assignments. At the final step, head8 refers to the node whose item reference value is a copy of d. Its next-node reference value refers to the first node, whose item reference value is a copy of i.

|< < Prev

Step 1 of 5: line 4

Next > >|

12345

Integer i = 42;
Double d = 12.5;

Node<Number> head8 = new Node<Number>(i);
head8 = new Node<Number>(d, head8);

Integer i = 42;
Double d = 12.5;

Node<Number> head8 = new Node<Number>(i);
head8 = new Node<Number>(d, head8);

Memory state at the breakpoint on line 4. [code listing] [download] [open]

Integer i = 42;
Double d = 12.5;

Node<Number> head8 = new Node<Number>(i);
head8 = new Node<Number>(d, head8);

Memory state at the breakpoint on line 5. [code listing] [download] [open]

Integer i = 42;
Double d = 12.5;

Node<Number> head8 = new Node<Number>(i);
head8 = new Node<Number>(d, head8);

Memory state at the breakpoint on line 7. [code listing] [download] [open]

Integer i = 42;
Double d = 12.5;

Node<Number> head8 = new Node<Number>(i);
head8 = new Node<Number>(d, head8);

Memory state at the breakpoint on line 8. [code listing] [download] [open]

Integer i = 42;
Double d = 12.5;

Node<Number> head8 = new Node<Number>(i);
head8 = new Node<Number>(d, head8);

Memory state at the breakpoint on line 9. [code listing] [download] [open]

Example 12

SVG PNG

Node<Shape> head9 = new Node<Shape>(new Rectangle(1.5, 2.0));

Sample Solution

This compiles and preserves generic type safety. Rectangle extends Shape, so a reference value that refers to a Rectangle object is compatible with the item type of Node<Shape>.

The first step shows the state before the declaration executes. At the final step, head9 refers to a node whose item reference value refers to a Rectangle object with width 1.5 and height 2.0. The value of the node's next field is null, which means it does not refer to another node.

|< < Prev

Step 1 of 2: line 4

Next > >|

12

Node<Shape> head9 = new Node<Shape>(new Rectangle(1.5, 2.0));

Node<Shape> head9 = new Node<Shape>(new Rectangle(1.5, 2.0));

Memory state at the breakpoint on line 4. [code listing] [download] [open]

Node<Shape> head9 = new Node<Shape>(new Rectangle(1.5, 2.0));

Memory state at the breakpoint on line 5. [code listing] [download] [open]

Example 13

SVG PNG

Node<Square> head9 = new Node<Square>(new Rectangle(1.5, 2.0));

Sample Solution

This does not compile. The Node<Square> constructor requires a Square reference value for its item, but the argument expression has type Rectangle. Although Square extends Rectangle, Rectangle is not a child of Square. A reference value that refers to a newly constructed Rectangle object is not compatible with the item type Square.

Node<Square> head9 = new Node<Square>(new Rectangle(1.5, 2.0));

Compiler error (expected)

Driver.java:4: error: incompatible types: Rectangle cannot be converted to Square
        Node<Square> head9 = new Node<Square>(new Rectangle(1.5, 2.0));
                                              ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

Part 3: Code Writing with Node<ItemType>

Getting Started

SVG PNG

Consider the following method. Throughout this lesson, linked lists are finite and acyclic. For getListItem, assume index is at least zero and less than the list length, so it identifies an existing node. The implementation relies on this precondition. The item reference value stored in that node may be null.

Listing 117 In Driver.java

/**
 * Return with the item reference value stored at the specified {@code index} in a linked list.
 * @param head the first-node reference value (null for an empty list)
 * @param index The position of the node (distance from the first node).
 * @return the item reference value stored in the node at the specified {@code index}
 */
public static String getListItem(Node<String> head, int index) {
    throw new UnsupportedOperationException("not implemented");
} // getListItem

Example: Code using the getListItem method

Assume getListItem has been implemented according to its contract.

Listing 118 In Driver.java

public static void main(String[] args) {

    // d, c, b, a
    Node<String> head1 = null;
    head1 = new Node<String>("a", head1);
    head1 = new Node<String>("b", head1);
    head1 = new Node<String>("c", head1);
    head1 = new Node<String>("d", head1);

    String second = Driver.getListItem(head1, 1);

    System.out.println(second);
    System.out.println(second.length());

} // main

• What are the outputs?

Solution

Listing 119 Output from the code above

c
1

Activity: Write the getListItem method

SVG PNG

public static String getListItem(Node<String> head, int index) {
    //
    // your code here
    //
} // getListItem

In your groups, write the code for getListItem on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include the Javadoc comment, unless you need it for your notes.

Sample Solution: The getListItem method (1)

Predict whether advancing the parameter head changes the caller's head1. Follow the call, then check the final output.

|< < Prev

Step 1 of 7: StringTraversal.java:13

Next > >|

1234567

StringTraversal.java

/** Executable StringTraversal example for the generics lesson. */
public class StringTraversal {

    /**
     * Run the example.
     * @param args unused command-line arguments
     */
    public static void main(String[] args) {
        Node<String> head1 = new Node<String>("a");
        head1 = new Node<String>("b", head1);
        head1 = new Node<String>("c", head1);
        head1 = new Node<String>("d", head1);
        String second = getListItem(head1, 1);
        System.out.println(second);
        System.out.println(second.length());
        System.out.println(head1.getItem());
    } // main

    /**
     * Return with the item reference value at an existing zero-based index.
     * The list must be finite and acyclic; the index must identify an existing node.
     * @param head the first-node reference value
     * @param index the position of an existing node
     * @return the item reference value stored in that node, possibly null
     */
    public static String getListItem(Node<String> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

} // StringTraversal

Node.java

/**
 * A singly linked node storing item and next-node reference values.
 * @param <ItemType> the item type
 */
public class Node<ItemType> {

    private ItemType item;
    private Node<ItemType> next;

    /**
     * Construct a node with a null next-node reference value.
     * @param item the item reference value
     */
    public Node(ItemType item) {
        this(item, null);
    } // Node

    /**
     * Construct a node with the supplied reference values.
     * @param item the item reference value
     * @param next the next-node reference value
     */
    public Node(ItemType item, Node<ItemType> next) {
        this.item = item;
        this.next = next;
    } // Node

    /**
     * Return with the stored item reference value.
     * @return the item reference value, possibly null
     */
    public ItemType getItem() {
        return item;
    } // getItem

    /**
     * Replace the stored item reference value.
     * @param item the new item reference value
     */
    public void setItem(ItemType item) {
        this.item = item;
    } // setItem

    /**
     * Return with the stored next-node reference value.
     * @return the next-node reference value, possibly null
     */
    public Node<ItemType> getNext() {
        return next;
    } // getNext

    /**
     * Replace the stored next-node reference value.
     * @param next the new next-node reference value
     */
    public void setNext(Node<ItemType> next) {
        this.next = next;
    } // setNext

} // Node

    public static void main(String[] args) {
        Node<String> head1 = new Node<String>("a");
        head1 = new Node<String>("b", head1);
        head1 = new Node<String>("c", head1);
        head1 = new Node<String>("d", head1);
        String second = getListItem(head1, 1);
        System.out.println(second);
        System.out.println(second.length());
        System.out.println(head1.getItem());
    } // main

Memory state at the breakpoint on line 13 in StringTraversal.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static String getListItem(Node<String> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

Memory state at the breakpoint on line 27 in StringTraversal.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static String getListItem(Node<String> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

Memory state at the breakpoint on line 28 in StringTraversal.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static String getListItem(Node<String> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

Memory state at the breakpoint on line 30 in StringTraversal.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Node<String> head1 = new Node<String>("a");
        head1 = new Node<String>("b", head1);
        head1 = new Node<String>("c", head1);
        head1 = new Node<String>("d", head1);
        String second = getListItem(head1, 1);
        System.out.println(second);
        System.out.println(second.length());
        System.out.println(head1.getItem());
    } // main

Memory state at the breakpoint on line 14 in StringTraversal.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Node<String> head1 = new Node<String>("a");
        head1 = new Node<String>("b", head1);
        head1 = new Node<String>("c", head1);
        head1 = new Node<String>("d", head1);
        String second = getListItem(head1, 1);
        System.out.println(second);
        System.out.println(second.length());
        System.out.println(head1.getItem());
    } // main

Memory state at the breakpoint on line 16 in StringTraversal.java. [code listing] [download] [open]

c
1

>_ Console Output

    public static void main(String[] args) {
        Node<String> head1 = new Node<String>("a");
        head1 = new Node<String>("b", head1);
        head1 = new Node<String>("c", head1);
        head1 = new Node<String>("d", head1);
        String second = getListItem(head1, 1);
        System.out.println(second);
        System.out.println(second.length());
        System.out.println(head1.getItem());
    } // main

Memory state at the breakpoint on line 17 in StringTraversal.java. [code listing] [download] [open]

c
1
d

>_ Console Output

Only the local parameter is reassigned. The caller's head1 still refers to the node containing the reference to "d". On normal completion, the method returns with a copy of the selected node's item reference value; it does not create a new string.

Sample Solution: The getListItem method (2)

Listing 120 In Driver.java: With Temporary Variable

public static String getListItem(Node<String> head, int index) {
    Node<String> current = head;
    for (int i = 0; i < index; i++) {
        current = current.getNext();
    } // for
    return current.getItem();
} // getListItem

Part 4: Writing Generic Methods

Generic Methods

Consider the method below (repeated from the previous section). Is it currently a generic method?

Listing 121 In Driver.java

/**
 * Return with the item reference value stored at the specified {@code index} in a linked list.
 * @param head the first-node reference value (null for an empty list)
 * @param index The position of the node (distance from the first node).
 * @return the item reference value stored in the node at the specified {@code index}
 */
public static String getListItem(Node<String> head, int index) {
   // ...
} // getListItem

Solution

This is not a generic method as it does not have a generic type parameter. While the Node class is generic, the head variable is of type Node<String> which uses a specific type argument that doesn't change.

Discussion: Generic Methods

What if we want to get an item from a linked list whose nodes store references to Song objects? What about Person objects and other kinds of object? Consider each declaration below separately.

public static String getListItem(Node<String> head, int index) { ...

public static Song getListItem(Node<Song> head, int index) { ...

public static Person getListItem(Node<Person> head, int index) { ...

public static Shape getListItem(Node<Shape> head, int index) { ...

Can we write one method that works for all reference types?

Our solution should be one drop in replacement that works in all of these scenarios:

Would this Work?

public static Object getListItem(Node<Object> head, int index) { ...

Thinking about getListItem with Node<Object>

This will NOT work as a drop in replacement. In your groups,

1. Write down two or more reasons why the last version of getListItem with Node<Object> cannot be used as a drop in replacement for the other versions of getListItem in all cases.

2. Write down one small code example of something that you can do with one of the other versions of getListItem that you cannot do with the one with Node<Object>.

Sample Solutions

1. Reasons:

   1. The return type is less specific; and

   2. None of the other parameterized Node<ItemType> types are compatible with Node<Object>.

2. These independent examples separate the two problems:

   A Node<String> reference value cannot be passed where a Node<Object> reference value is required. This assignment exhibits the same incompatibility:

   Node<String> strings = new Node<>("c");
   Node<Object> objects = strings;
   

   Compiler error (expected)

   Driver.java:5: error: incompatible types: Node<String> cannot be converted to Node<Object>
           Node<Object> objects = strings;
                                  ^
   1 error

   Even with a compatible Node<Object>, the item expression has type Object, so this assignment fails:

   Node<Object> objects = new Node<>("c");
   String second = objects.getItem();
   

   Compiler error (expected)

   Driver.java:5: error: incompatible types: Object cannot be converted to String
           String second = objects.getItem();
                                          ^
   1 error

   Storing that value in an Object variable is legal, but Object does not declare length:

   Object second = "c";
   System.out.println(second.length());
   

   Compiler error (expected)

   Driver.java:5: error: cannot find symbol
           System.out.println(second.length());
                                    ^
     symbol:   method length()
     location: variable second of type Object
   1 error

Lack of Covariance

Java generics are invariant: even when String is a subtype of Object, Node<String> is not a subtype of Node<Object>. Here is the hierarchy for this example:

SVG PNG

For example:

• String extends Object

• Node<String> extends Object (NOT Node<Object>)

Genericize

Activity: Write the generic getListItem signature

In your groups, write the method signature for the generic getListItem method on your exit ticket. Make sure to include a type parameter.

Solution

public static <T> T getListItem(Node<T> head, int index) { ... }

Write the generic getListItem method

Let's write the method body together.

Sample Solution: The generic getListItem method

public static <T> T getListItem(Node<T> head, int index) {
    for (int i = 0; i < index; i++) {
        head = head.getNext();
    } // for
    return head.getItem();
} // getListItem

Note the placement of <T>. It declares that getListItem has one type parameter named T

• it is used in the return type; and

• it is used as the type argument for ItemType in Node<T>.

The method declares its own type parameter T. The class declares ItemType; supplying T connects these roles.

The bundled generic operations are static methods of ListMethods. Earlier examples used Driver for the non-generic version.

Example: Code using the generic getListItem method

Node<String>

// c, b, a
Node<String> head1 = null;
head1 = new Node<String>("a", head1);
head1 = new Node<String>("b", head1);
head1 = new Node<String>("c", head1);

// Fill in the code below to get the second item in the list using getListItem
String second = ______________;

System.out.println(second);
System.out.println(second.length());

Solution

Listing 122 The line with the blank should be:

String second = ListMethods.<String>getListItem(head1, 1);

Java can infer the type argument here. The equivalent call is ListMethods.getListItem(head1, 1). The explicit form makes the type argument visible.

Node<Person>

// Pam, Bob, Sue
Node<Person> head1 = null;
head1 = new Node<Person>(new Person("Sue"), head1);
head1 = new Node<Person>(new Person("Bob"), head1);
head1 = new Node<Person>(new Person("Pam"), head1);

// Fill in the code below to get the second item in the list using getListItem
Person second = _______________;

System.out.println(second.getName());
System.out.println(second.getName().length());

Solution

Listing 123 The line with the blank should be:

Person second = ListMethods.<Person>getListItem(head1, 1);

Here too, ListMethods.getListItem(head1, 1) permits inference. The exercise prints Bob and 3.

The extended example below adds reference comparisons and checks the caller's head. Predict whether second refers to a new person or to the person already in the list.

|< < Prev

Step 1 of 7: GenericTraversal.java:12

Next > >|

1234567

GenericTraversal.java

/** Executable GenericTraversal example for the generics lesson. */
public class GenericTraversal {

    /**
     * Run the example.
     * @param args unused command-line arguments
     */
    public static void main(String[] args) {
        Node<Person> head = new Node<Person>(new Person("Sue"));
        head = new Node<Person>(new Person("Bob"), head);
        head = new Node<Person>(new Person("Pam"), head);
        Person second = ListMethods.<Person>getListItem(head, 1);
        System.out.println(second.getName());
        System.out.println(second == head.getNext().getItem());
        System.out.println(head.getItem().getName());
    } // main

} // GenericTraversal

ListMethods.java

/** Generic operations on finite, acyclic singly linked lists. */
public class ListMethods {

    /**
     * Return with the item reference value at an existing zero-based index.
     * The caller must supply an index at least zero and less than the list length.
     * @param <T> the item type
     * @param head the first-node reference value
     * @param index the position of an existing node
     * @return the item reference value stored in that node, possibly null
     */
    public static <T> T getListItem(Node<T> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

    /**
     * Prepend a node without changing the existing nodes.
     * @param <T> the item type
     * @param head the first-node reference value, or null for an empty list
     * @param item the item reference value to store
     * @return a reference to the new first node
     */
    public static <T> Node<T> prepend(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item, head);
        return newNode;
    } // prepend

    /**
     * Append a node, linking it from the previous last node when one exists.
     * @param <T> the item type
     * @param head the first-node reference value, or null for an empty list
     * @param item the item reference value to store
     * @return a reference to the first node of the resulting list
     */
    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

    /**
     * Store a copy of the supplied item reference value in every node.
     * @param <T> the item type
     * @param head the first-node reference value, or null for an empty list
     * @param item the item reference value to store in every node
     * @return the original first-node reference value, possibly null
     */
    public static <T> Node<T> setAll(Node<T> head, T item) {
        Node<T> current = head;
        while (current != null) {
            current.setItem(item);
            current = current.getNext();
        } // while
        return head;
    } // setAll

} // ListMethods

Node.java

/**
 * A singly linked node storing item and next-node reference values.
 * @param <ItemType> the item type
 */
public class Node<ItemType> {

    private ItemType item;
    private Node<ItemType> next;

    /**
     * Construct a node with a null next-node reference value.
     * @param item the item reference value
     */
    public Node(ItemType item) {
        this(item, null);
    } // Node

    /**
     * Construct a node with the supplied reference values.
     * @param item the item reference value
     * @param next the next-node reference value
     */
    public Node(ItemType item, Node<ItemType> next) {
        this.item = item;
        this.next = next;
    } // Node

    /**
     * Return with the stored item reference value.
     * @return the item reference value, possibly null
     */
    public ItemType getItem() {
        return item;
    } // getItem

    /**
     * Replace the stored item reference value.
     * @param item the new item reference value
     */
    public void setItem(ItemType item) {
        this.item = item;
    } // setItem

    /**
     * Return with the stored next-node reference value.
     * @return the next-node reference value, possibly null
     */
    public Node<ItemType> getNext() {
        return next;
    } // getNext

    /**
     * Replace the stored next-node reference value.
     * @param next the new next-node reference value
     */
    public void setNext(Node<ItemType> next) {
        this.next = next;
    } // setNext

} // Node

Person.java

/** A person with a mutable name; distinct from the oracle model's Person record. */
public class Person {

    private String name;

    /**
     * Construct a person with the supplied name reference value.
     * @param name the name reference value
     */
    public Person(String name) {
        this.name = name;
    } // Person

    /**
     * Return with the stored name reference value.
     * @return the name reference value
     */
    public String getName() {
        return name;
    } // getName

    /**
     * Replace the stored name reference value.
     * @param name the new name reference value
     */
    public void setName(String name) {
        this.name = name;
    } // setName

} // Person

    public static void main(String[] args) {
        Node<Person> head = new Node<Person>(new Person("Sue"));
        head = new Node<Person>(new Person("Bob"), head);
        head = new Node<Person>(new Person("Pam"), head);
        Person second = ListMethods.<Person>getListItem(head, 1);
        System.out.println(second.getName());
        System.out.println(second == head.getNext().getItem());
        System.out.println(head.getItem().getName());
    } // main

Memory state at the breakpoint on line 12 in GenericTraversal.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> T getListItem(Node<T> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

Memory state at the breakpoint on line 13 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> T getListItem(Node<T> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

Memory state at the breakpoint on line 14 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> T getListItem(Node<T> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

Memory state at the breakpoint on line 16 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Node<Person> head = new Node<Person>(new Person("Sue"));
        head = new Node<Person>(new Person("Bob"), head);
        head = new Node<Person>(new Person("Pam"), head);
        Person second = ListMethods.<Person>getListItem(head, 1);
        System.out.println(second.getName());
        System.out.println(second == head.getNext().getItem());
        System.out.println(head.getItem().getName());
    } // main

Memory state at the breakpoint on line 13 in GenericTraversal.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Node<Person> head = new Node<Person>(new Person("Sue"));
        head = new Node<Person>(new Person("Bob"), head);
        head = new Node<Person>(new Person("Pam"), head);
        Person second = ListMethods.<Person>getListItem(head, 1);
        System.out.println(second.getName());
        System.out.println(second == head.getNext().getItem());
        System.out.println(head.getItem().getName());
    } // main

Memory state at the breakpoint on line 15 in GenericTraversal.java. [code listing] [download] [open]

Bob
true

>_ Console Output

    public static void main(String[] args) {
        Node<Person> head = new Node<Person>(new Person("Sue"));
        head = new Node<Person>(new Person("Bob"), head);
        head = new Node<Person>(new Person("Pam"), head);
        Person second = ListMethods.<Person>getListItem(head, 1);
        System.out.println(second.getName());
        System.out.println(second == head.getNext().getItem());
        System.out.println(head.getItem().getName());
    } // main

Memory state at the breakpoint on line 16 in GenericTraversal.java. [code listing] [download] [open]

Bob
true
Pam

>_ Console Output

This extended example prints Bob, true, and Pam. The call supplies a copy of the existing item reference value.

Discussion: Node<Shape>

Code Interpretation (1)

SVG PNG

Will this code compile? Write your answer on your exit ticket. If not, say why not. If so, what is the output?

// head to tail: Circle(r=1.0), Square(side=1.0), Rectangle(w=2.0, h=1.0)
Node<Shape> head1 = null;
head1 = new Node<Shape>(new Rectangle(2.0, 1.0), head1);
head1 = new Node<Shape>(new Square(1.0), head1);
head1 = new Node<Shape>(new Circle(1.0), head1);

Shape second = ListMethods.<Shape>getListItem(head1, 1);

System.out.println(second.getArea());

Solution

Yes. The output is 1.0: index 1 identifies the node whose item reference value refers to the square.

The visualization uses a minimal shape model with the same inheritance relationships and area calculations as the diagram.

Memory state at the breakpoint on line 14 in ShapeExample.java. [download] [open]

Code Interpretation (2)

SVG PNG

Will this code compile? Write your answer on your exit ticket. If not, say why not. If so, what is the output?

// head to tail: Circle(r=1.0), Square(side=1.0), Rectangle(w=2.0, h=1.0)
Node<Shape> head1 = null;
head1 = new Node<Rectangle>(new Rectangle(2.0, 1.0), head1);
head1 = new Node<Square>(new Square(1.0), head1);
head1 = new Node<Circle>(new Circle(1.0), head1);

Shape second = ListMethods.<Shape>getListItem(head1, 1);

System.out.println(second.getArea());

Solution

No, it will not compile. Node<Rectangle> is not compatible with Node<Shape>. The constructor's second argument also requires a Node<Rectangle> reference value, but head1 has type Node<Shape>. The example below isolates the assignment error by omitting that argument:

Node<Shape> head = new Node<Rectangle>(new Rectangle(2.0, 1.0));

Compiler error (expected)

Driver.java:4: error: incompatible types: Node<Rectangle> cannot be converted to Node<Shape>
        Node<Shape> head = new Node<Rectangle>(new Rectangle(2.0, 1.0));
                           ^
1 error

Lack of Covariance

Even though Rectangle is a subtype of Shape, Node<Rectangle> is not a subtype of Node<Shape>. A Node<Shape> can store a reference to a rectangle, but its item can later be replaced with a reference to a circle.

SVG PNG

Generic Code Writing Activities

prepend

Activity: Write the prepend method

Listing 124 The prepend method

/**
 * Prepend an item to a linked list (add to beginning).
 * @param <T> The item type.
 * @param head the first-node reference value (null for an empty list)
 * @param item The item to prepend.
 * @return a reference to the first node in the resulting list
 */
public static <T> Node<T> prepend(Node<T> head, T item) {
    throw new UnsupportedOperationException("not implemented");
} // prepend

In your groups, write the code for prepend on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Listing 125 Example code using prepend.

// a, b, c
Node<String> head = null;
head = ListMethods.<String>prepend(head, "c");
head = ListMethods.<String>prepend(head, "b");
head = ListMethods.<String>prepend(head, "a");

Sample Solution: The prepend method (1)

Predict what oldHead refers to after the first call. Does prepending change either field of an existing node?

|< < Prev

Step 1 of 9: PrependExample.java:10

Next > >|

123456789

PrependExample.java

/** Executable PrependExample example for the generics lesson. */
public class PrependExample {

    /**
     * Run the example.
     * @param args unused command-line arguments
     */
    public static void main(String[] args) {
        Node<String> head = new Node<String>("b");
        Node<String> oldHead = head;
        head = ListMethods.<String>prepend(head, "a");
        System.out.println(head.getItem());
        System.out.println(oldHead.getItem());
        System.out.println(head.getNext() == oldHead);
        Node<String> empty = null;
        empty = ListMethods.<String>prepend(empty, "first");
        System.out.println(empty.getItem());
    } // main

} // PrependExample

ListMethods.java

/** Generic operations on finite, acyclic singly linked lists. */
public class ListMethods {

    /**
     * Return with the item reference value at an existing zero-based index.
     * The caller must supply an index at least zero and less than the list length.
     * @param <T> the item type
     * @param head the first-node reference value
     * @param index the position of an existing node
     * @return the item reference value stored in that node, possibly null
     */
    public static <T> T getListItem(Node<T> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

    /**
     * Prepend a node without changing the existing nodes.
     * @param <T> the item type
     * @param head the first-node reference value, or null for an empty list
     * @param item the item reference value to store
     * @return a reference to the new first node
     */
    public static <T> Node<T> prepend(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item, head);
        return newNode;
    } // prepend

    /**
     * Append a node, linking it from the previous last node when one exists.
     * @param <T> the item type
     * @param head the first-node reference value, or null for an empty list
     * @param item the item reference value to store
     * @return a reference to the first node of the resulting list
     */
    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

    /**
     * Store a copy of the supplied item reference value in every node.
     * @param <T> the item type
     * @param head the first-node reference value, or null for an empty list
     * @param item the item reference value to store in every node
     * @return the original first-node reference value, possibly null
     */
    public static <T> Node<T> setAll(Node<T> head, T item) {
        Node<T> current = head;
        while (current != null) {
            current.setItem(item);
            current = current.getNext();
        } // while
        return head;
    } // setAll

} // ListMethods

Node.java

/**
 * A singly linked node storing item and next-node reference values.
 * @param <ItemType> the item type
 */
public class Node<ItemType> {

    private ItemType item;
    private Node<ItemType> next;

    /**
     * Construct a node with a null next-node reference value.
     * @param item the item reference value
     */
    public Node(ItemType item) {
        this(item, null);
    } // Node

    /**
     * Construct a node with the supplied reference values.
     * @param item the item reference value
     * @param next the next-node reference value
     */
    public Node(ItemType item, Node<ItemType> next) {
        this.item = item;
        this.next = next;
    } // Node

    /**
     * Return with the stored item reference value.
     * @return the item reference value, possibly null
     */
    public ItemType getItem() {
        return item;
    } // getItem

    /**
     * Replace the stored item reference value.
     * @param item the new item reference value
     */
    public void setItem(ItemType item) {
        this.item = item;
    } // setItem

    /**
     * Return with the stored next-node reference value.
     * @return the next-node reference value, possibly null
     */
    public Node<ItemType> getNext() {
        return next;
    } // getNext

    /**
     * Replace the stored next-node reference value.
     * @param next the new next-node reference value
     */
    public void setNext(Node<ItemType> next) {
        this.next = next;
    } // setNext

} // Node

    public static void main(String[] args) {
        Node<String> head = new Node<String>("b");
        Node<String> oldHead = head;
        head = ListMethods.<String>prepend(head, "a");
        System.out.println(head.getItem());
        System.out.println(oldHead.getItem());
        System.out.println(head.getNext() == oldHead);
        Node<String> empty = null;
        empty = ListMethods.<String>prepend(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 10 in PrependExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Node<String> head = new Node<String>("b");
        Node<String> oldHead = head;
        head = ListMethods.<String>prepend(head, "a");
        System.out.println(head.getItem());
        System.out.println(oldHead.getItem());
        System.out.println(head.getNext() == oldHead);
        Node<String> empty = null;
        empty = ListMethods.<String>prepend(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 11 in PrependExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> prepend(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item, head);
        return newNode;
    } // prepend

Memory state at the breakpoint on line 27 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> prepend(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item, head);
        return newNode;
    } // prepend

Memory state at the breakpoint on line 28 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Node<String> head = new Node<String>("b");
        Node<String> oldHead = head;
        head = ListMethods.<String>prepend(head, "a");
        System.out.println(head.getItem());
        System.out.println(oldHead.getItem());
        System.out.println(head.getNext() == oldHead);
        Node<String> empty = null;
        empty = ListMethods.<String>prepend(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 12 in PrependExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> prepend(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item, head);
        return newNode;
    } // prepend

Memory state at the breakpoint on line 27 in ListMethods.java. [code listing] [download] [open]

a
b
true

>_ Console Output

    public static <T> Node<T> prepend(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item, head);
        return newNode;
    } // prepend

Memory state at the breakpoint on line 28 in ListMethods.java. [code listing] [download] [open]

a
b
true

>_ Console Output

    public static void main(String[] args) {
        Node<String> head = new Node<String>("b");
        Node<String> oldHead = head;
        head = ListMethods.<String>prepend(head, "a");
        System.out.println(head.getItem());
        System.out.println(oldHead.getItem());
        System.out.println(head.getNext() == oldHead);
        Node<String> empty = null;
        empty = ListMethods.<String>prepend(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 17 in PrependExample.java. [code listing] [download] [open]

a
b
true

>_ Console Output

    public static void main(String[] args) {
        Node<String> head = new Node<String>("b");
        Node<String> oldHead = head;
        head = ListMethods.<String>prepend(head, "a");
        System.out.println(head.getItem());
        System.out.println(oldHead.getItem());
        System.out.println(head.getNext() == oldHead);
        Node<String> empty = null;
        empty = ListMethods.<String>prepend(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 18 in PrependExample.java. [code listing] [download] [open]

a
b
true
first

>_ Console Output

The first new node stores a copy of the previous head reference value. The caller assigns the returned reference value to head; oldHead still refers to the original node. The final call starts with an empty list and returns with a reference to its new first node.

Sample Solution: The prepend method (2)

public static <T> Node<T> prepend(Node<T> head, T item) {
    return new Node<T>(item, head);
} // prepend

append

Activity: Write the append method

Listing 126 The append method.

/**
 * Append an item to a linked list (add to end).
 * @param <T> The item type.
 * @param head the first-node reference value (null for an empty list)
 * @param item The item to append.
 * @return a reference to the first node in the resulting list
 */
public static <T> Node<T> append(Node<T> head, T item) {
    throw new UnsupportedOperationException("not implemented");
} // append

In your groups, write the code for append on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Listing 127 Example code using append.

// c, b, a
Node<String> head = null;
head = ListMethods.<String>append(head, "c");
head = ListMethods.<String>append(head, "b");
head = ListMethods.<String>append(head, "a");

Sample Solution: The append method

Compare the two nonempty-list calls with the final empty-list call. Which operation changes the caller's variable, and which operation changes an existing node?

|< < Prev

Step 1 of 22: AppendExample.java:10

Next > >|

12345678910111213141516171819202122

AppendExample.java

/** Executable AppendExample example for the generics lesson. */
public class AppendExample {

    /**
     * Run the example.
     * @param args unused command-line arguments
     */
    public static void main(String[] args) {
        Node<String> head = new Node<String>("a");
        Node<String> originalHead = head;
        head = ListMethods.<String>append(head, "b");
        head = ListMethods.<String>append(head, "c");
        System.out.println(head == originalHead);
        System.out.println(head.getNext().getNext().getItem());
        Node<String> empty = null;
        empty = ListMethods.<String>append(empty, "first");
        System.out.println(empty.getItem());
    } // main

} // AppendExample

ListMethods.java

/** Generic operations on finite, acyclic singly linked lists. */
public class ListMethods {

    /**
     * Return with the item reference value at an existing zero-based index.
     * The caller must supply an index at least zero and less than the list length.
     * @param <T> the item type
     * @param head the first-node reference value
     * @param index the position of an existing node
     * @return the item reference value stored in that node, possibly null
     */
    public static <T> T getListItem(Node<T> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

    /**
     * Prepend a node without changing the existing nodes.
     * @param <T> the item type
     * @param head the first-node reference value, or null for an empty list
     * @param item the item reference value to store
     * @return a reference to the new first node
     */
    public static <T> Node<T> prepend(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item, head);
        return newNode;
    } // prepend

    /**
     * Append a node, linking it from the previous last node when one exists.
     * @param <T> the item type
     * @param head the first-node reference value, or null for an empty list
     * @param item the item reference value to store
     * @return a reference to the first node of the resulting list
     */
    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

    /**
     * Store a copy of the supplied item reference value in every node.
     * @param <T> the item type
     * @param head the first-node reference value, or null for an empty list
     * @param item the item reference value to store in every node
     * @return the original first-node reference value, possibly null
     */
    public static <T> Node<T> setAll(Node<T> head, T item) {
        Node<T> current = head;
        while (current != null) {
            current.setItem(item);
            current = current.getNext();
        } // while
        return head;
    } // setAll

} // ListMethods

Node.java

/**
 * A singly linked node storing item and next-node reference values.
 * @param <ItemType> the item type
 */
public class Node<ItemType> {

    private ItemType item;
    private Node<ItemType> next;

    /**
     * Construct a node with a null next-node reference value.
     * @param item the item reference value
     */
    public Node(ItemType item) {
        this(item, null);
    } // Node

    /**
     * Construct a node with the supplied reference values.
     * @param item the item reference value
     * @param next the next-node reference value
     */
    public Node(ItemType item, Node<ItemType> next) {
        this.item = item;
        this.next = next;
    } // Node

    /**
     * Return with the stored item reference value.
     * @return the item reference value, possibly null
     */
    public ItemType getItem() {
        return item;
    } // getItem

    /**
     * Replace the stored item reference value.
     * @param item the new item reference value
     */
    public void setItem(ItemType item) {
        this.item = item;
    } // setItem

    /**
     * Return with the stored next-node reference value.
     * @return the next-node reference value, possibly null
     */
    public Node<ItemType> getNext() {
        return next;
    } // getNext

    /**
     * Replace the stored next-node reference value.
     * @param next the new next-node reference value
     */
    public void setNext(Node<ItemType> next) {
        this.next = next;
    } // setNext

} // Node

    public static void main(String[] args) {
        Node<String> head = new Node<String>("a");
        Node<String> originalHead = head;
        head = ListMethods.<String>append(head, "b");
        head = ListMethods.<String>append(head, "c");
        System.out.println(head == originalHead);
        System.out.println(head.getNext().getNext().getItem());
        Node<String> empty = null;
        empty = ListMethods.<String>append(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 10 in AppendExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Node<String> head = new Node<String>("a");
        Node<String> originalHead = head;
        head = ListMethods.<String>append(head, "b");
        head = ListMethods.<String>append(head, "c");
        System.out.println(head == originalHead);
        System.out.println(head.getNext().getNext().getItem());
        Node<String> empty = null;
        empty = ListMethods.<String>append(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 11 in AppendExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 39 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 41 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 44 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 47 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 49 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Node<String> head = new Node<String>("a");
        Node<String> originalHead = head;
        head = ListMethods.<String>append(head, "b");
        head = ListMethods.<String>append(head, "c");
        System.out.println(head == originalHead);
        System.out.println(head.getNext().getNext().getItem());
        Node<String> empty = null;
        empty = ListMethods.<String>append(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 12 in AppendExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 39 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 41 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 44 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 45 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 44 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 47 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 49 in ListMethods.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Node<String> head = new Node<String>("a");
        Node<String> originalHead = head;
        head = ListMethods.<String>append(head, "b");
        head = ListMethods.<String>append(head, "c");
        System.out.println(head == originalHead);
        System.out.println(head.getNext().getNext().getItem());
        Node<String> empty = null;
        empty = ListMethods.<String>append(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 13 in AppendExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 39 in ListMethods.java. [code listing] [download] [open]

true
c

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 41 in ListMethods.java. [code listing] [download] [open]

true
c

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 42 in ListMethods.java. [code listing] [download] [open]

true
c

>_ Console Output

    public static <T> Node<T> append(Node<T> head, T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> current = head;
        if (head == null) {
            head = newNode;
        } else {
            while (current.getNext() != null) {
                current = current.getNext();
            } // while
            current.setNext(newNode);
        } // if
        return head;
    } // append

Memory state at the breakpoint on line 49 in ListMethods.java. [code listing] [download] [open]

true
c

>_ Console Output

    public static void main(String[] args) {
        Node<String> head = new Node<String>("a");
        Node<String> originalHead = head;
        head = ListMethods.<String>append(head, "b");
        head = ListMethods.<String>append(head, "c");
        System.out.println(head == originalHead);
        System.out.println(head.getNext().getNext().getItem());
        Node<String> empty = null;
        empty = ListMethods.<String>append(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 17 in AppendExample.java. [code listing] [download] [open]

true
c

>_ Console Output

    public static void main(String[] args) {
        Node<String> head = new Node<String>("a");
        Node<String> originalHead = head;
        head = ListMethods.<String>append(head, "b");
        head = ListMethods.<String>append(head, "c");
        System.out.println(head == originalHead);
        System.out.println(head.getNext().getNext().getItem());
        Node<String> empty = null;
        empty = ListMethods.<String>append(empty, "first");
        System.out.println(empty.getItem());
    } // main

Memory state at the breakpoint on line 18 in AppendExample.java. [code listing] [download] [open]

true
c
first

>_ Console Output

For an empty list, the caller must retain the new first-node reference value. For a nonempty list, setNext mutates the existing last node; the returned reference value still refers to the original first node.

setAll

Activity: Write the setAll method

Listing 128 The setAll method.

/**
 * Set all the items in a linked list to the specified item value.
 * @param <T> The item type.
 * @param head the first-node reference value (null for an empty list)
 * @param item The item value to set.
 * @return the first-node reference value in the resulting list, possibly null
 */
public static <T> Node<T> setAll(Node<T> head, T item) {
    throw new UnsupportedOperationException("not implemented");
} // setAll

In your groups, write the code for setAll on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Listing 129 Example code using setAll.

// hello, world
Node<String> head = null;
head = ListMethods.<String>append(head, "hello");
head = ListMethods.<String>append(head, "world");

// again, again
head = ListMethods.<String>setAll(head, "again");

Sample Solution: The setAll method

public static <T> Node<T> setAll(Node<T> head, T item) {
    Node<T> current = head;
    while (current != null) {
        current.setItem(item);
        current = current.getNext();
    } // while
    return head;
} // setAll

Predict whether setAll creates a separate person for each node. Then predict both names after shared.setName. The snapshots show the state before setAll, after it, and after the name change.

/** Executable SetAllExample example for the generics lesson. */
public class SetAllExample {

    /**
     * Run the example.
     * @param args unused command-line arguments
     */
    public static void main(String[] args) {
        Node<Person> head = new Node<Person>(new Person("Joe"));
        head.setNext(new Node<Person>(new Person("Sally")));
        Person shared = new Person("Pat");
        head = ListMethods.<Person>setAll(head, shared);
        System.out.println(head.getItem() == head.getNext().getItem());
        shared.setName("Alex");
        System.out.println(head.getItem().getName());
        System.out.println(head.getNext().getItem().getName());
    } // main

} // SetAllExample

Memory state at the breakpoint on line 12 in SetAllExample.java. [code listing] [download] [open]

Memory state at the breakpoint on line 13 in SetAllExample.java. [code listing] [download] [open]

Memory state at the breakpoint on line 15 in SetAllExample.java. [code listing] [download] [open]

The output is true, Alex, and Alex. Each node stores a copy of the same item reference value, so both refer to the same person. setAll changes item fields, not next-node fields, and returns with the original head reference value (or null for an empty list).

max

Activity: Write the max method

Listing 130 The max method.

/**
 * Return with a reference to a maximum element in the linked list.
 * @param <T> The item type.
 * @param head the first-node reference value (null for an empty list)
 * @throws NullPointerException If {@code head} is {@code null}.
 * @return The max value.
 */
public static <T> T max(Node<T> head) {
   throw new UnsupportedOperationException("not implemented");
} // max

In your groups, write the code for max on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Listing 131 Example code using max.

// 7, 10, 8
Node<Integer> head = null;
head = ListMethods.<Integer>append(head, 7);
head = ListMethods.<Integer>append(head, 10);
head = ListMethods.<Integer>append(head, 8);

// prints 10
System.out.println(Driver.<Integer>max(head));

Sample Solution: The max method

No ordering operation is guaranteed. An unconstrained T does not provide a general operation for deciding which of two items is greater. The signature alone is not enough to implement a maximum under each item's natural ordering without additional assumptions or runtime checks.

• What can T be replaced with?

• Given two items of type T, is it possible to:

  • determine whether they are considered equal?

  • determine which one is considered greater?

Part 5: A Generic max method?

Discussion: Upper Bounds

Table 2 Type parameter declarations and upper bounds

Syntax	Explicit	Meaning
<T>	No	T must be compatible with Object
<T extends Object>	Yes	T must be compatible with Object
<T extends Drawable>	Yes	T must be compatible with Drawable
<T extends ClassOrInterface>	Yes	T must be compatible with ClassOrInterface
<T extends ClassOrInterface<T>>	Yes	T must be compatible with ClassOrInterface<T>

Discussion: T is the same as T extends Object

In a type-parameter declaration, <T> gives T an implicit upper bound of Object. Writing <T extends Object> makes that same bound explicit.

Reference types are valid type arguments for T: class types such as String and Integer, interface types such as Drawable, and array types such as String[] and int[]. Another type variable can also be used. Primitive types such as int are not valid type arguments; use Integer instead.

Inside generic code, we can assign a value of type T to an Object variable and call public Object methods such as equals, hashCode, and toString. A value of type T may be null, so calling an instance method still requires a non-null receiver.

The bound does not make T interchangeable with Object or guarantee an ordering operation. We cannot assume compareTo is available on a value of type T; that requires a stronger bound, as in the following max activity.

Discussion: The bounded generic max method

We now switch from a linked list to an array to simplify traversal while we focus on the type bound. The same need for an ordering operation applies to both representations.

What must we guarantee about the array's element type? How can an interface specify the operation we need?

For the following methods, assume the array is non-null and nonempty, and every element is non-null. The implementation relies on these preconditions; it does not check them.

public static <T> T max(T[] items) {
    //
    // ...
    //
} // max

Activity: Write the bounded generic max method

public static <T extends Comparable<T>> T max(T[] items) {
   T maxItem = ________;                       // Line 1
   for (int i = 1; i < items.length; i++) {
       T item = _______;                       // Line 2
       int result = _______;                   // Line 3
       if (result > 0) {
           maxItem = item;
       } // if
   } // for
   return maxItem;
} // max

Write the code for the bounded max method on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Sample Solution: The bounded generic max method

public static <T extends Comparable<T>> T max(T[] items) {
    T maxItem = items[0];
    for (int i = 1; i < items.length; i++) {
        T item = items[i];
        int result = item.compareTo(maxItem);
        if (result > 0) {
            maxItem = item;
        } // if
    } // for
    return maxItem;
} // max

The bound makes compareTo available on values of type T. Predict when maxItem changes for {7, 10, 8}. Does the method create a new maximum object, or return with an existing reference value?

|< < Prev

Step 1 of 22: MaxExample.java:10

Next > >|

12345678910111213141516171819202122

/** Executable MaxExample example for the generics lesson. */
public class MaxExample {

    /**
     * Run the example.
     * @param args unused command-line arguments
     */
    public static void main(String[] args) {
        Integer[] items = new Integer[] {7, 10, 8};
        Integer largest = MaxExample.<Integer>max(items);
        System.out.println(largest);
        System.out.println(largest == items[1]);
        String[] words = new String[] {"pear", "apple", "plum"};
        System.out.println(MaxExample.max(words));
    } // main

    /**
     * Return with a reference to a maximum element under its natural ordering.
     * The array must be non-null and nonempty, and its elements must be non-null.
     * @param <T> the element type, which can compare itself with another T
     * @param items the array reference value
     * @return a reference to the first maximum element encountered
     */
    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

} // MaxExample

    public static void main(String[] args) {
        Integer[] items = new Integer[] {7, 10, 8};
        Integer largest = MaxExample.<Integer>max(items);
        System.out.println(largest);
        System.out.println(largest == items[1]);
        String[] words = new String[] {"pear", "apple", "plum"};
        System.out.println(MaxExample.max(words));
    } // main

Memory state at the breakpoint on line 10 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 25 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 27 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 28 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 29 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 30 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 27 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 28 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 29 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 33 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Integer[] items = new Integer[] {7, 10, 8};
        Integer largest = MaxExample.<Integer>max(items);
        System.out.println(largest);
        System.out.println(largest == items[1]);
        String[] words = new String[] {"pear", "apple", "plum"};
        System.out.println(MaxExample.max(words));
    } // main

Memory state at the breakpoint on line 11 in MaxExample.java. [code listing] [download] [open]

> (no output yet)

>_ Console Output

    public static void main(String[] args) {
        Integer[] items = new Integer[] {7, 10, 8};
        Integer largest = MaxExample.<Integer>max(items);
        System.out.println(largest);
        System.out.println(largest == items[1]);
        String[] words = new String[] {"pear", "apple", "plum"};
        System.out.println(MaxExample.max(words));
    } // main

Memory state at the breakpoint on line 12 in MaxExample.java. [code listing] [download] [open]

10

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 25 in MaxExample.java. [code listing] [download] [open]

10
true

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 27 in MaxExample.java. [code listing] [download] [open]

10
true

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 28 in MaxExample.java. [code listing] [download] [open]

10
true

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 29 in MaxExample.java. [code listing] [download] [open]

10
true

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 27 in MaxExample.java. [code listing] [download] [open]

10
true

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 28 in MaxExample.java. [code listing] [download] [open]

10
true

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 29 in MaxExample.java. [code listing] [download] [open]

10
true

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 30 in MaxExample.java. [code listing] [download] [open]

10
true

>_ Console Output

    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 1; i < items.length; i++) {
            T item = items[i];
            int result = item.compareTo(maxItem);
            if (result > 0) {
                maxItem = item;
            } // if
        } // for
        return maxItem;
    } // max

Memory state at the breakpoint on line 33 in MaxExample.java. [code listing] [download] [open]

10
true

>_ Console Output

    public static void main(String[] args) {
        Integer[] items = new Integer[] {7, 10, 8};
        Integer largest = MaxExample.<Integer>max(items);
        System.out.println(largest);
        System.out.println(largest == items[1]);
        String[] words = new String[] {"pear", "apple", "plum"};
        System.out.println(MaxExample.max(words));
    } // main

Memory state at the breakpoint on line 15 in MaxExample.java. [code listing] [download] [open]

10
true
plum

>_ Console Output

The integer call prints 10 and true. maxItem stores a copy of an array element's reference value. The string call prints plum. When two elements compare as equal, the strict > 0 condition retains the first maximum encountered.

Discussion: Leveraging the bounded generic max method

Can we use the bounded version of the max method to find a max String in a String[]? If so, how will it do the comparisons?

• java.base/java.lang.String

Solution

Yes. String implements Comparable<String> so it is a valid replacement for the type parameter T. The comparisons will be done using String.compareTo, which uses lexicographic order based on character values, rather than string length. The sign of the result matters; a positive result need not equal one.

Discussion: Will max work?

Can we use our bounded version of the max method with Movie and Person? In other words, are Movie and Person valid type replacements for T?

These are the fully qualified oracle model types linked below. That Person is distinct from this lesson's mutable example class.

• cs1302.oracle.model.Movie

• cs1302.oracle.model.Person

Solution

Movie does not implement Comparable<Movie>, so it is not a valid type replacement for T. Person does implement Comparable<Person>, so it is a valid type replacement for T.

Download the executable examples and solutions

The bundle includes the shared classes and all eight example programs. From the extracted directory, run compile.sh to compile all examples and run MaxExample. Supply another driver class name to run that example instead:

$ ./compile.sh
$ ./compile.sh Interpretation

sh -c "$(curl -fsSL https://cs1302book.com/_bundle/cs1302-generics-lesson.sh)"

- downloading cs1302-generics-lesson bundle...
- verifying integrity of downloaded files using sha256sum...
- extracting downloaded archive...
- removing intermediate files...
subdirectory cs1302-generics-lesson successfully created