Custom Generic Data Structure: Linked List

Let’s revisit the main method of our simple linked list exercise.

public static void main(String[] args){

LinkedList list = new LinkedList();

list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);
list.add(11);
list.add(12);

list.print();
}

Since all elements of the collection were stored in ListNodes that had a data member of type
object we could place any object into the collection. For example, the following version of the
main method would compile and run without error.

public static void main(String[] args){

LinkedList list = new LinkedList();

list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(“cat”);
list.add(10);
list.add(11);
list.add(“dog”);

list.print();
}

The Object data type is often a preferred storage target because everything in Java “is-an”
Object. This increases the usefulness of the data structure because it can be used for any group
of data types. However this approach also makes the data structure prone to error. Consider
this: We add the following method to our LinkedList:

public Object getCurrent()

and a call to getCurrent():

Integer x = (Integer)(list.getCurrent());

Based on the revised main method, getCurrent will produce an error when it tries to cast “cat” to
an Integer.

So far our typical solution to this problem has been to anticipate the error, and create and handle
an exception to catch the error. While this approach can be effective it has a major limitation in
that the error is handled at run time. It would be preferable to prevent the error at compile time.

This is what generic data structures try to achieve. They are often called “type-safe” data
structures.

Let’s revise our simplest linked list so it uses generics. We’ll start with the list node:

class ListNode<T>{
private T data;
public ListNode<T> nextNode;

public ListNode(T item){

data=item;
}

public T getData(){
return data;
}
}

When a list node is created, it must provide a data type for T, all occurrences of T in this code
would be replaced with that data type. Our list class therefore would need to look like this:

public class LinkedList<T>{

private ListNode<T> items;

private ListNode<T> current;

public void add(T item){

if(items==null){
items = new ListNode(item);
current=items;
}
else{
current.nextNode=new ListNode(item);
current = current.nextNode;
}
}

 
public void print(){

ListNode<T> temp=items;

while(temp!= null){
System.out.println(temp.getData());
temp=temp.nextNode;
}
}

When the linked list is created, a data type for the list is specified. T is then used to create the
type of the nodes, the type of the parameters, and the return types as required. Any attempt from
a driver program to place a non T type into the data structure will result in a compile error.
Consider this main method:

public static void main(String[] args){

LinkedList<Integer> list = new LinkedList<Integer>();

list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(“cat”);
list.add(10);
list.add(11);
list.add(12);

list.print();
}
The line that tries to add the “cat” will cause a compile error, since the linked list was declared to
hold only Integers. The Linked List can still be used to hold any type, however we must specify
the type at run time.

Since we do this, a method the get’s current only returns the correct type:

public T getCurrent()
{
return current.getData();
}

This method can be called in main, without the need for a cast:

Integer x = list.getCurrent();

Polymorphism in Generic Data Structures

We may of course want to limit the data structure to some base type, or an object the implements
a common interface (often Comparable). We can limit the types that a data structure can hold
with the following notation:

public class LinkedList<T extends Comparable>

and

public class ListNode<T extends Comparable>

Now we can only instantiate data structures that implement the Comparable interface.

This would allow us to add a find max method to our list, and not require any exception
handling.

In fact the comparison in the findMax() method would look like this:

if( max.compareTo( temp.getData() )<0 )

max = temp.getData();

This main method would work:

public static void main(String[] args){

LinkedList<Integer> list = new LinkedList<Integer>();

 list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(50);
list.add(11);
list.add(12);

list.print();

Integer x = list.getMax();
System.out.println(x);

Again, no casting is required since the data structure was designed to only accept Comparables
and throws a compile error if an incorrect type is placed into the collection.

Exercise:
Create the generic linked list above so that it implements the getCurrent method and the findMax
method. Demonstrate their use in a simple driver program.