Question

CSCI-2467 Lab 11 – Refactor LinkedList Application to use Generics

Background

The code consists of three files that implement and use a simple linked list. The code was written in early Java-style using the Object class in order to allow the linked list to be a list of objects of any type. While the code works, it is not type-safe. Refactor the code to use Java Generics. You will need to change the Main class to create a linked list of Strings in the list1() method and a linked list of Integers in the list2() method. You’ll then need to make appropriate modifications to the other two Java files so that they use Java Generics. Do NOT use the built-in Java LinkedList class.

package edu.cscc;
public class Main {
    public static void main(String[] args) {
        list1();
        list2();
    }

    // Use linked list with Strings
    public static void list1() {
        LinkedList llist = new LinkedList();
        llist.addFirst("one");
        llist.addLast("two");
        llist.addLast("three");
        llist.addFirst("zero");
        llist.addLast("xxxx");
        llist.addFirst("yyyyy");
        llist.deleateLast();
        llist.deleteFirst();
        System.out.println(llist);
        llist.deleteFirst();
        llist.deleateLast();
        llist.deleteFirst();
        llist.deleateLast();
        System.out.println(llist);
    }

    // Use linked list with Integers
    public static void list2() {
        LinkedList llist = new LinkedList();
        llist.addFirst(1);
        llist.addLast(2);
        llist.addLast(3);
        llist.addFirst(0);
        llist.addLast(142);
        llist.addFirst(-97);
        llist.deleateLast();
        llist.deleteFirst();
        System.out.println(llist);
        llist.deleteFirst();
        llist.deleateLast();
        llist.deleteFirst();
        llist.deleateLast();
        System.out.println(llist);
    }
}

}

package edu.cscc;
public class LinkedList {
    private Node head;

    public LinkedList() {
        head = null;
    }

    public void addFirst(Object content) {
        Node ptr = head;
        head = new Node(content,ptr);
    }

    public void addLast(Object content) {
        Node last = new Node(content,null);
        if (head == null) {
            head = last;
        } else {
            Node ptr = head;
            while(ptr.getNext() != null) {
                ptr = ptr.getNext();
            }
            ptr.setNext(last);
        }
    }

    public boolean deleteFirst() {
        if (head == null) {
            return false;
        } else {
            head = head.getNext();
            return true;
        }
    }

    public boolean deleateLast() {
        if (head == null) {
            return false;
        }
        else if (head.getNext() == null) {
            head = null;
            return true;
        } else {
            Node ptr = head;
            while (ptr.getNext().getNext() != null) {
                ptr = ptr.getNext();
            }
            ptr.setNext(null);
            return true;
        }
    }

    public Node getHead() {
        return head;
    }

    public String toString() {
        String str;
        if (head == null) {
            str = "<empty>";
        } else {
            Node ptr = head;
            str = "("+ptr.getContent().toString()+")";
            while(ptr.getNext() != null) {
                str = str + "->";
                ptr = ptr.getNext();
                str = str + "(" + ptr.getContent().toString() + ")";
            }
        }
        return str;
    }
}

packageedu.cscc;

public class Node {
    private Object content;
    private Node next;

    public Node(Object content, Node next) {
        this.content = content;
        this.next = next;
    }

    public Object getContent() {
        return content;
    }

    public void setContent(Object content) {
        this.content = content;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

Answer 1

// Node.java : Generic Node class representing the node of the linked list
packageedu.cscc;

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

public Node(T content, Node<T> next) {
this.content = content;
this.next = next;
}

public T getContent() {
return content;
}

public void setContent(T content) {
this.content = content;
}

public Node<T> getNext() {
return next;
}

public void setNext(Node<T> next) {
this.next = next;
}
}
//end of Node.java

// LinkedList.java : Generic Linked List class to represent linked list of generic elements stored in Node

package edu.cscc;

public class LinkedList<T> {
private Node<T> head;

public LinkedList() {
head = null;
}

public void addFirst(T content) {
Node<T> ptr = head;
head = new Node<T>(content,ptr);
}

public void addLast(T content) {
Node<T> last = new Node<T>(content,null);
if (head == null) {
head = last;
} else {
Node<T> ptr = head;
while(ptr.getNext() != null) {
ptr = ptr.getNext();
}
ptr.setNext(last);
}
}

public boolean deleteFirst() {
if (head == null) {
return false;
} else {
head = head.getNext();
return true;
}
}

public boolean deleateLast() {
if (head == null) {
return false;
}
else if (head.getNext() == null) {
head = null;
return true;
} else {
Node<T> ptr = head;
while (ptr.getNext().getNext() != null) {
ptr = ptr.getNext();
}
ptr.setNext(null);
return true;
}
}

public Node<T> getHead() {
return head;
}

public String toString() {
String str;
if (head == null) {
str = "<empty>";
} else {
Node<T> ptr = head;
str = "("+ptr.getContent().toString()+")";
while(ptr.getNext() != null) {
str = str + "->";
ptr = ptr.getNext();
str = str + "(" + ptr.getContent().toString() + ")";
}
}
return str;
}
}
//end of LinkedList.java

// Main.java : Driver program to test the generic LinkedList class created using String and Integer types
package edu.cscc;

public class Main {

   public static void main(String[] args) {

       list1();
      list2();

   }
  
   // Use linked list with Strings
public static void list1() {
LinkedList<String> llist = new LinkedList<String>();
llist.addFirst("one");
llist.addLast("two");
llist.addLast("three");
llist.addFirst("zero");
llist.addLast("xxxx");
llist.addFirst("yyyyy");
llist.deleateLast();
llist.deleteFirst();
System.out.println(llist);
llist.deleteFirst();
llist.deleateLast();
llist.deleteFirst();
llist.deleateLast();
System.out.println(llist);
}
  
// Use linked list with Integers
public static void list2() {
LinkedList<Integer> llist = new LinkedList<Integer>();
llist.addFirst(1);
llist.addLast(2);
llist.addLast(3);
llist.addFirst(0);
llist.addLast(142);
llist.addFirst(-97);
llist.deleateLast();
llist.deleteFirst();
System.out.println(llist);
llist.deleteFirst();
llist.deleateLast();
llist.deleteFirst();
llist.deleateLast();
System.out.println(llist);
}

}

//end of Main.java

Output: