Wildcard in Generics

Generics is confusing (in fact one of the most confusing concepts of Java); and on top of it, wildcards (bounds) is even more confusing. That explains, the reason for this dedicated post :)

In the Generics post; I discussed that subtyping doesn't work with Generics. So, If Apple extends Fruit; list of Apple is not a subtype of list of Fruit. Does it mean that Generics can't be generic and you can't write a method which work for subtype? Luckily, wildcard helps you make Generics really generic.

Bounded Wildcard

Generics uses a wildcard character (?) to work with subtype. Let's go in detail on each.

upper-bounded wildcard: uses wildcard(?), followed by extends keyword, followed by its upper bound. 

List<? extends Number> will work for List of Number and list of its subtype (Integer, Double and Float).

List<Integer> li = new ArrayList<Integer>();

List<? extends Number> list = li;

lower-bounded wildcard: uses wildcard, followed by super keyword, followed by its lower bound. 

List<? super Integer> will work for list of Integer, list of Number and list of Object.

List<Number> ln = new ArrayList<Number>();

List<? super Integer> list1=ln;

Unbounded Wildcard

Using just the wildcard i.e. ? makes it unbounded. It means anything, so equivalent to using raw type. 

<?> says that; i wrote code keeping in mind Generics, but it can hold any type. 

List<?> is a non raw list of some specific type but we don't know what the type is. You can't pass any type. So the type is unknown but it doesn't mean that it can take any shit!

List<Integer> li2 = new ArrayList<Integer>();
List<?> l3 = li2;

 

Code Talk

Time to walk the talk through a simple example.

import java.util.ArrayList;
import java.util.List;

/**
 * Defines Base class Fruit and sub classes Apple and FujiApple. 
 * Uses BoundsGenericsTest for testing wildcard.
 * Save it as BoundsGenericsTest.java
 * 
 * @author Siddheshwar
 * 
 */
class Fruit {
 protected String name;

 public Fruit(String name) {
  super();
  this.name = name;
 }

 public String toString() {
  return name;
 }
}

class Apple extends Fruit {
 public Apple(String name) {
  super(name);
 }
}

class FujiApple extends Apple {
 public FujiApple(String name) {
  super(name);
 }
}

public class BoundsGenericsTest {
 List<? extends Fruit> list;

 public void add(List<? extends Fruit> f) {
  list = f;
 }

 public static void main(String[] args) {
  BoundsGenericsTest obj = new BoundsGenericsTest();

  List<Apple> apples = new ArrayList<Apple>();
  apples.add(new Apple("apple1"));
  apples.add(new Apple("apple2"));

  obj.add(apples);
  System.out.println(" list of Apples: " + obj.list);

  List<FujiApple> fujiApples = new ArrayList<FujiApple>();
  fujiApples.add(new FujiApple("fujiapple1"));
  fujiApples.add(new FujiApple("fujiapple2"));
  obj.add(fujiApples);
  System.out.println(" list of FujiApples : " + obj.list);

  List<? super FujiApple> another = 

                            (List<? super FujiApple>) obj.list;
  System.out.println(" val :" + another);
  List<? super FujiApple> another1 = fujiApples;
  System.out.println(" val :" + another);

  //unbounded wildcard
  List<?> fruits = apples;
  System.out.println("Fruits:" + fruits);
 }
}

Output:
 list of Apples: [apple1, apple2]
 list of FujiApples : [fujiapple1, fujiapple2]
 val :[fujiapple1, fujiapple2]
 val :[fujiapple1, fujiapple2]
Fruits:[apple1, apple2]

Related Post : Java Generics

Implementing Single Linked List in Java

Before I start, let me caution you that this post is not about LinkedList [Java Doc] API of Java. LinkedList API of Java is a specialized implementation of doubly linked list. This post talks in general about linked data structures (i.e. linked list) and implementation of single linked list in Java.

Definition

Linked data structures are composed of distinct chunks of memory; and these chunks are bounded/linked through pointers. These memory chunks are referred as nodes. As nodes are not stored in contiguous memory so adding or removing individual nodes is quite easier (unlike an array). But one drawback is that random access to node is not possible. 

typedef struct node {
         item_type item;  //data stored in node
         struct list *next;  //points to successor 
}node;

In C language; *p denotes the item that is pointed to by pointer p, and &x denotes the address (i.e. pointer) of a particular variable x. A special null value is used to denote the termination of the list. 

C pointers are similar to Java references; as both of them point to something.

Let's cover them in detail

C pointers:
    int var = 20; 
    int *ip;   //pointer to an integer
    ip = &var;  //store address of var in pointer ip

Java references:
     Integer x = new Integer(20);  //x is reference to Integer

Usually, Java references are implemented as pointers in C; but specification doesn't say it explicitly. Java reference should be just an abstraction on C pointers (i.e. references in Java will be implemented using C pointers). I am not going to stress if both are same or not; it's debatable!

Implementation

Below is custom single linked list implementation in Java. I have just provided add and print method.

package algo;  
   
 /**  
  * Generic single linked list implementation with generics  
  *   
  * @author Siddheshwar   
  */  
 public class SingleLinkedList<E> {  
      Node<E> start; // points to the head or first node  
   
      /**  
       * Node class    
       */  
      private class Node<E> {  
           E data;  
           Node<E> next;  
   
           public Node(E data, Node<E> next) {  
                this.data = data;  
                this.next = next;  
           }  
   
           public E getData() {  
                return data;  
           }  
   
           public Node<E> getNext() {  
                return next;  
           }  
   
           public void setNext(Node<E> next) {  
                this.next = next;  
           }  
      }  
   
      public void add(E d) { // add at the end of list  
           if (start == null) {  
                start = new Node<E>(d, null);  
           } else {  
                Node<E> tmp = start;  
                while (tmp.next != null) {  
                     tmp = tmp.next;  
                }  
                tmp.setNext(new Node<E>(d, null));  
           }  
      }  
   
      public void print() {  
           Node<E> current = start;  
           System.out.print(" values in link-list are :");  
           while (current != null) {  
                System.out.print(current.getData() + "--> ");  
                current = current.getNext();  
           }  
           System.out.println("null");  
      }  
   
      public static void main(String[] args) {  
           SingleLinkedList<String> sll = new SingleLinkedList<>();  
           sll.add("abc");  
           sll.add("def");  
           sll.print();  
      }  
 } 

Output : 
values in link-list are :abc--> def--> null

Complexity of common operations 

1.  Insert/Update/delete at end of list: O(n) . Need to traverse whole list.  
2.  Insert at the beginning/head of the list : O(1)
3.  Find the size of list : O(n). But it can be achieved in O(1) if you keep track of the count in a separate attribute (increment its value on each addition and decrement on each deletion).

References from Java

1. LinkedList  [Java Doc] : Doubly linked list implementation of the List and Deque interfaces.
2. LinkedHashMap [Java Doc] : Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. Linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map.
3. LinkedHashSet [Java Doc] : Hash table and linked list implementation of the Set interface, with predictable iteration order.

Related Post :Implementing Doubly linked list in Java

Generics in Java

Generics implement the Parameterized Type concept in Java and it's one of the major changes of Java 5 (Java SE5). This is derived from a concept known as template of C++ and initial motivation behind this feature was to allow creation of parameterized containers.

      List list = new ArrayList();    //Before Java  SE 1.5 or Without Generics
     List<Type> list = new ArrayList<Type>();  //  With Generics

Let's take some of the important aspects of Generics:

Primitive type parameters NOT allowed in Generics

This is one of the limitation of Generics; compiler doesn't allows you to use primitives as type parameter. Instead of primitives you need to use corresponding boxed type as shown below:

        List<int> c1 = new ArrayList<int>();   //Not allowed; doesn't compile
        List<Integer> c2 = new ArrayList<Integer>();  //perfect

So you can't declare containers of primitive but does it mean you can't even store/retrieve primitives ? Certainly NOT.  Another Java SE5 feature comes to rescue.  Through autoboxing and autounboxing; you can easily add/retrieve primitive types.

         c2.get(0);   //add int

         int i = c2.get(i):  //retrieve value to primitive type
 

Why Generics ?

Before Generics came into picture; Containers were used without type parameter. So you could put any data type in the list. But you need to cast when you retrieve data from container/collection (as shown below) :

public static void main(String[] args) {
        List list = new ArrayList();
        list.add("abc");
        list.add(420);
        list.add("NaN");
       
        String s = (String) list.get(0);
        int i = (Integer)list.get(1);
       
        System.out.println(s + "  "+ i);
       
        //Integer nan = (Integer)list.get(2);  throws ClassCastException
    } 

Above code compiles properly but if you try to read data to an incompatible type; a runtime ClassCastException is thrown. Ideally it's better to get error as early as possible; preferably at compile time. So Generics got introduced to provide compile time (type) safety and eliminate the need for cast.

 

Generics Implementation

Before Generics introduction to the language, lots of code existed with raw type i.e. no type parameter. Challenge before designers was to add Generics feature in such a way that existing code remains legal and interoperable with the new changes. 

     List list = new ArrayList();   //before Java 5
     List<E> list = new ArrayList<E>();  // Java 5+

So first case still compiles on Java SE5+; though you will get warning.
Obvious questions are :  how is it possible ?  And how both can co-exist ?                                                                              

This is possible because Generics are implemented by erasure. This means that type constraint is enforced only at compile time and at run time the type information is erased or discarded. The .class file which gets generated as outcome of compiling will have same byte code for above 2 cases (i.e with raw and generics). 

To verify same; analyze the content of .class file for above 2 lines inside a main method.  javap utility inside bin directory can be used to analyze content of compiled file.

 

Generics vs Array

Generics and Array vary in couple of way. First, arrays are covariant but Generics by contrast are invariant. This point is shown in below diagram. Integer extends Number class so do the corresponding array classes; but the same is not true in case of Generics. 

Another important difference is that arrays are reified (knows type at runtime) but Generics are implemented by erasure( type information erased at run time).

Let's see an example to understand the same:

  public static void main(String[] args) {      
        Number[] array = new Integer[5];
        array[0] = 5;
        array[1] = 6.5;  //Runtime Exception
          
        List<Number> list = new ArrayList<Integer>();  //Doesn't compile
    }

 Above code has 2 problems:

1. array object allows addition of a Number (6.5) at compile time but at run time it throws java.lang.ArrayStoreException. This is because run time type of array object is Integer[] not Number[] or Double[].
2. list object doesn't allow declaration as arraylist of Integer. It gives compilation error Type mismatch: cannot convert from ArrayList<Integer> to List<Number> 

 So Array objects preserve the rules about the type of object they contain. So you can't abuse them. On the other hand Generics moves such error detection to compile time.    

 

Bounds/Wildcards

Advanced generics concepts are discussed in this separate post, here.

---
do post your feedback !!!