Generics

Polymorphisms in Java

• Overloading
• Overwriting
• Subtype polymorphism (Object)
• Parametric polymorphism

Parametric polymorphism

• Generics
  • Parametrically polymorphic functions are called generic functions
  • Parametrically polymorphic data types are called generic data types
• Enables code reuse and flexibility
• Code works independently of the types of values it operates on

In other words, a function or type can be written without depending on knowing the specific types.

Writing class with generic type

• add a <> after your class name with whatever name you want, convention is to use Type or T
• use that name when creating instance variables and as return types

public class MyType<Type> {
    private Type data;
    
    public MyType(Type d) {
        data = d;
    }
    
    public Type getData() {
        return data;
    }

}

Using our generic data type

Now, when calling our class we need to specify the actual type inside the <>

MyType<String> name = new MyType<String>("Adriana");
System.out.println(name.getData());

Multiple types

public class MyType<O, T> {
    private O one;
    private T two;
    
    public MyType(O one, T two) {
        this.one = one;
        this.two = two;
    }
    
    public O getOne() {
        return one;
    }
    
    public T getTwo() {
        return two;
    }

}

Multiple types use

MyType<Object, Object> name = new MyType<>("Adriana", 43);
System.out.println(name.getOne());
System.out.println(name.getTwo());

Generic functions

Add <Something> before return type, use the generic name for the argument type

public static <T> String getMyString(T element) {
        return element.getClass().getName() + " = " + element;
    }

Call:

System.out.println(getMyString(12));

Quiz 4

current time

Practice with generics: linked lists

Recall what linked lists are? Discuss with your table mates:

• What are the properties of linked lists?
• When do we use linked lists?

Linked lists

• dynamic structure, can grow and shrink as needed
  
• elements are arranged in a linear sequence
• implemented through nodes – each node has a reference to the next node

Nodes

To create a linked list:

• a class of self-referential objects
• each object of the class contains a reference to an object of the same class
• convention is to name the class Node

Write a class in Java called Node that has two instance variables: data (any type), and a reference to another node.

Write the constructor method, and getters

Node solution

public class Node<T> {
    private T data;
    private Node<T> next;

    public Node(T d) {
        data = d;
        next = null;
    }
    
    public Node<T> getNext() {
        return next;
    }
    
    public void setNext(Node<T> next) {
        this.next = next;
    }
    
    public T getData() {
        return data;
    }

}

LinkedList class

• What methods do you need to implement?
• What instance variables do you need?

Implement MyList class

• A linked list has a node as its head/root, which should be initialized as null
• The insert method should check if the head/root is null (what’s the easiest implementation?)
• Create a toString() method to test your code (get each element in list)
• Write JUnit tests to test your code

MyList class

public class MyLinkedList<T> {
    private Node<T> root;
    
    public MyLinkedList() {
        root = null;
    }
    
    public Node<T> getRoot() {
        return root;
        
    }
    
    public void insert(Node<T> newNode) {
        if (root == null) {
            root = newNode;
        } else {
            newNode.setNext(root);
            root = newNode;
        }
    }
    
    public String toString() {
        String message = "";
        Node<T> currentNode = root;
        while (currentNode != null) {
            message += currentNode.getData() + " ";
            currentNode = currentNode.getNext();
        }
        return message.trim();
    }

}

JUnit tests

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class MyLinkedListTest {

    @Test
    void testNodeNull() {
        Node<Integer> myNode = new Node<>(10);
        Assertions.assertNull(myNode.getNext());
    }
    
    @Test
    void testNodeValue() {
        Node<Integer> myNode = new Node<>(10);
        Assertions.assertEquals(10, myNode.getData());
    }
    
    @Test
    void testListNull() {
        MyLinkedList<String> myList = new MyLinkedList<>();
        Assertions.assertNull(myList.getRoot());
    }
    
    @Test
    void testListInsert() {
        MyLinkedList<Object> myList = new MyLinkedList<>();
        myList.insert(new Node<>(10));
        Assertions.assertEquals(10, myList.getRoot().getData());
    }
    
    @Test
    void testListToString() {
        MyLinkedList<Object> myList = new MyLinkedList<>();
        myList.insert(new Node<>(10));
        myList.insert(new Node<>(5));
        myList.insert(new Node<>(8));
        String expected = "8 5 10";
        Assertions.assertEquals(expected, myList.toString());
    }

}

search method

• Similar to toString()
• Return false if value not in list, true otherwise

search solution

public boolean search(T value) {
        if (root == null) return false;
        else {
            Node<T> currentNode = root;
            while (currentNode != null) {
                if (currentNode.getData().equals(value)) return true;
                currentNode = currentNode.getNext();
            }
        }
        return false;
    }

JUnit test

  @Test
    void testSearch() {
        MyLinkedList<Object> myList = new MyLinkedList<>();
        myList.insert(new Node<>(10));
        myList.insert(new Node<>(5));
        myList.insert(new Node<>("something"));
        Assertions.assertTrue(myList.search("something"));
        Assertions.assertFalse(myList.search(8));
    }

Delete node

Removing a node takes a few more steps:

• Find the node to remove (if present), look ahead for the next node, adjust reference for the previous node
• How to remove first element?

delete method

public void delete(T value) {
        if (root.getData().equals(value)) {
            root = root.getNext();
        } else {
            Node<T> currentNode = root;
            Node<T> previousNode = null;
            Boolean found = false;
            while (currentNode != null && !found) {
                if (currentNode.getData().equals(value) ) {
                    found = true;
                    if (previousNode != null) {
                        previousNode.setNext(currentNode.getNext());
                    }
                } // if found node to delete
                previousNode = currentNode; // for next iteration make current previous
                currentNode = currentNode.getNext(); // get next node for current
            } // while 
        }
        
    }

JUnit test

    @Test
    void testDeletion() {
        MyLinkedList<Object> myList = new MyLinkedList<>();
        myList.insert(new Node<>(10));
        myList.insert(new Node<>(5.5));
        myList.insert(new Node<>("abc"));
        myList.insert(new Node<>("hello"));
        myList.delete(5.5);
        String expected = "hello abc 10";
        Assertions.assertEquals(expected, myList.toString());   
    }