Implementation of a Generic Singly Linked List in Java

Question

New to the site. Trying to implement a generic SinglyLinkedList, fetch returns null even though there are nodes inserted and delete method return false, when true is expected. In addition, it functions just fine when I decide to fetch or delete in reverse order. Looking for a set of fresh eyes to see what I am missing. Thanks-in-advance.

public class MainSinglyLinkedList {
 public static void main(String[] args) {
 SinglyLinkedList <Listing> boston = new SinglyLinkedList<Listing>();
 Listing l1 = new Listing("Bill", "1st Avenue", "123 4567");
 Listing l2 = new Listing("Al", "2nd Avenue", "456 3232");
 Listing l3 = new Listing("Mike", "3rd Avenue", "333 3333");
 boston.insert(l1); // test insert
 boston.insert(l2);
 boston.insert(l3);
 boston.showAll();
 System.out.println("***********************************************");
 System.out.println(boston.fetch("Mike").toString());
 //boston.delete("Al"); // test delete of Al
 System.out.println( boston.delete("Bill"));
 //System.out.println( boston.delete("Mike"));
 //System.out.println( boston.delete("Al"));
 //System.out.println( boston.delete("Bill"));
 //System.out.println("-----------------------------------------------");
 boston.showAll();
 //boston.update("Mike", l2); // test update of Mike to Al
 //System.out.println(boston.update("Mike", l2));
 //boston.showAll();
 SinglyLinkedList <StudentListing> Form4East = new SinglyLinkedList<StudentListing>();
 StudentListing bill = new StudentListing("Bill", "2988050", "3.9");
 StudentListing mary = new StudentListing("Mary", "2988051", "3.5");
 StudentListing tom = new StudentListing("Tom", "2988052", "1.7");
 System.out.println(Form4East.insert(bill));
 System.out.println(Form4East.insert(mary));
 System.out.println(Form4East.insert(tom));
 System.out.println(Form4East.fetch("Tom"));
 System.out.println(Form4East.fetch("Bill"));
 System.out.println(Form4East.fetch("Mary"));
 System.out.println(Form4East.fetch("Bill"));
 System.exit(0);
 }
}
public class SinglyLinkedList<T> {
 private Node<T> h; // list header
 public SinglyLinkedList() {
 h = new <T> Node(); // dummy node
 h.l = null;
 h.next = null;
 }
 public boolean insert(T newNode) {
 Node n = new Node();
 GenericNode node = (GenericNode) newNode;
 if (node == null) // out of memory
 {
 return false;
 } else {
 n.next = h.next;
 h.next = n;
 n.l = (T) node.deepCopy();
 return true;
 }
 }
 public GenericNode fetch(Object targetKey) {
 Node p = h.next;
 GenericNode node = (GenericNode) p.l;
 while (p != null && !(node.compareTo(targetKey) == 0)) {
 p = p.next;
 }
 if (p != null) {
 return node.deepCopy();
 } else {
 return null;
 }
 }
 public boolean delete(Object targetKey) {
 Node q = h;
 Node p = h.next;
 GenericNode node = (GenericNode)p.l;
 while (p != null && !(node.compareTo(targetKey) == 0)) {
 q = p;
 p = p.next;
 }
 if (p != null) {
 q.next = p.next;
 return true;
 } else {
 return false;
 }
 }
 public boolean update(Object targetKey, T newNode) {
 if (delete(targetKey) == false) {
 return false;
 } else if (insert(newNode) == false) {
 return false;
 }
 return true;
 }
 public void showAll() {
 Node p = h.next;
 while (p != null) //continue to traverse the list
 {
 System.out.println(p.l.toString());
 p = p.next;
 }
 }
 /**
 *
 * @param <T>
 */
 public class Node <T> {
 private T l;
 private Node <T> next;
 public <T> Node() {
 }
 }// end of inner class Node
}
public class Listing implements GenericNode{
 private String name; // key field
 private String address;
 private String number;
 public Listing(String n, String a, String num) {
 name = n;
 address = a;
 number = num;
 }
 public String toString() {
 return ("Name is " + name
 + "\nAddress is " + address
 + "\nNumber is " + number + "\n");
 }
 public Listing deepCopy() {
 Listing clone = new Listing(name, address, number);
 return clone;
 }
 public int compareTo(Object targetKey) {
 String tKey = (String) targetKey;
 return (name.compareTo(tKey));
 }
 public void setAddress(String a) // coded to demonstrate encapsulation
 {
 address = a;
 }
}
public class StudentListing implements GenericNode {
 // instance variables - replace the example below with your own
 private String name; // keyfield
 private String identification_no;
 private String gpa;
 /**
 * Constructor for objects of class StudentListings
 *
 * @ param n- name of the student
 * @ param id- identification number of the student
 * @ param g- gpa of the student
 */
 public StudentListing(String n, String id, String g) {
 // initialise instance variables
 name = n;
 identification_no = id;
 gpa = g;
 }
 /**
 * toString method annotates the student info for display
 *
 * @ return name - name of the student
 * @ return identification_no - identification number of the student
 * @ return gpa - grade point average of the student
 */
 public String toString() {
 return ("Name is " + name + "\nIdentification Number is " + identification_no
 + "\nGpa is " + gpa + "\n");
 }
 /**
 * deepCopy method copies the content on the StudentListings object that
 * invokes it to a new StudentListings object and returns the clone.
 *
 * @ return clone - copy of the StudentListings that invoked it
 */
 public StudentListing deepCopy() {
 StudentListing clone = new StudentListing(name, identification_no, gpa);
 return clone;
 }
 /**
 * compareTo method compares the targetKey to the keyfield name
 *
 * @ return - 0, if the argument string is equal to this string
 */
 public int compareTo(Object targetKey) {
 String tKey = (String) targetKey;
 return (name.compareTo(tKey));
 }
 /**
 * setName method, sets the name of the student a param n- name of the
 * student
 */
 public void setName(String n) {
 name = n;
 }
 /**
 * setId method, sets the id of the student a param n- name of the student
 */
 public void setId(String id) {
 identification_no = id;
 }
 /**
 * setName method, sets the name of the student a param n- name of the
 * student
 */
 public void setGpa(String g) {
 gpa = g;
 }
 /**
 * input method, allowers for user to input data
 *
 */
 public void input() {
 name = JOptionPane.showInputDialog("Enter a name");
 identification_no = JOptionPane.showInputDialog("Enter an identification number");
 gpa = JOptionPane.showInputDialog("Enter a gpa");
 } //end of inputStudentListings method
}//end of class StudentListings

• Peilonrayz: Welcome to Code Review! Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. Please see what you may and may not do after receiving answers .
• Engr_Ondigo: Duly noted. Pardon my novices

Answer 1

Your code seems pretty inconsistent, you cast T to GenericNode a few times, I can't see the code of your Node class, but it should be a generic class I asume, so why are you creating Node objects without the generic type? You should use better variable names, not just p.l, I suggest at least n.data (why l?).

Why are you not using Node.equals(otherNode) to compare the list items instead of compareTo with a string!?

In general a List of type T should also save its data as T and not Object or String or cast it around and assume the type if not necessary.

Usually the Node class of a List is always the same and only internally used to link the data together, that's why the List class is a generic so data type is variable, and not the Node type itself. The Node should hold a reference to the data.

Your fetch method seems logically correct, but I would write it differently to understand the logic better when reading it, e.g.

public Node<T> fetch(T targetKey) {
 Node<T> n = h.next;
 while (n != null) {
 if (n.data != null && n.data.equals(targetKey)) // n.data is of type T
 return n.deepCopy();
 n = n.next;
 }
 // not found
 return null;
}

• Engr_Ondigo: Thank you so much Xander for answering! I tried your given example and i have an issue of cannot find symbol since an interface is being used too. Am editing the code for betteer understanding.
• xander: I just provided an example that is not meant as a replacement for your code. I suggest that you play around with the default provided List and LinkedList by the Java framework and how they behave and then think about how you implement your own version of it (I guess that is just a lesson for you since Java already has good implementations of what you want).
• Engr_Ondigo: My biggest issue is, why does it fetch the last inserted item just fine, but if I try to fetch the first or second item, it returns null even though the nodes are there.
• xander: In that case I'd use a debugger and step throught the code of your fetch method to see what's going on, maybe it's not even the fetch method itself but the data in your list is corrupted from another operation and it fails because of that, so the debugger is your friend in cases like this. :)