Using the generic capabilities of Java 5.0, modify the implementation of the str
ID: 3866750 • Letter: U
Question
Using the generic capabilities of Java 5.0, modify the implementation of the structure SinglyLinkedList presented in Figure 4.15 to make it fully generic. Include a driver program that demonstrates the functionality of the class with two homogeneous SinglyLinkedList objects that store two different kinds of nodes.
This is the code of Figure 4.15:
public class SinglyLinkedList
{ private Node h; // list header
public SinglyLinkedList()
{ h = new Node(); // dummy node
h.l = null;
h.next = null;
}
public boolean insert(Listing newListing)
{ Node n = new Node();
if(n == null) // out of memory
return false;
else
{ n.next = h.next;
h.next = n;
n.l = newListing.deepCopy();
return true;
}
}
public Listing fetch(String targetKey)
{ Node p = h.next;
while (p != null && !(p.l.compareTo(targetKey) == 0))
{ p = p.next;
}
if(p != null)
return p.l.deepCopy();
else
return null;
}
public boolean delete(String targetKey)
{ Node q = h;
Node p = h.next;
while (p != null && !(p.l.compareTo(targetKey) == 0))
{ q = p;
p = p.next;
}
if(p != null)
{ q.next = p.next;
return true;
}
else
return false;
}
public boolean update(String targetKey, Listing newListing)
{ if(delete(targetKey) == false)
return false;
else if(insert(newListing) == 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;
}
}
public class Node
{ private Listing l;
private Node next;
public Node()
{
}
}// end of inner class Node
}//end SinglyLinkedList outer class
Explanation / Answer
Here is the Source code, please go through it thoroughly:
public class SinglyLinkedListImpl<T> {
private Node<T> head;
private Node<T> tail;
public void add(T element){
Node<T> nd = new Node<T>();
nd.setValue(element);
System.out.println("Adding: "+element);
if(head == null){
head = nd;
tail = nd;
} else {
tail.setNextRef(nd);
}
tail = nd;
}
}
public void adding_After(T element, T after){
Node<T> tmp = head;
Node<T> refNode = null;
System.out.println("Traversing to all nodes..");
while(true){
if(tmp == null){
break;
}
if(tmp.compareTo(after) == 0){
refNode = tmp;
break;
}
tmp = tmp.getNextRef();
}
if(refNode != null){
Node<T> nd = new Node<T>();
nd.setValue(element);
nd.setNextRef(tmp.getNextRef());
if(tmp == tail){
tail = nd;
}
tmp.setNextRef(nd);
} else {
System.out.println("Unable to find the given element...");
}
}
public void delete_Front(){
if(head == null){
System.out.println("Underflow...");
}
Node<T> tmp = head;
head = tmp.getNextRef();
if(head == null){
tail = null;
}
System.out.println("Deleted: "+tmp.getValue());
}
public void deleteAfter(T after){
Node<T> tmp = head;
Node<T> refNode = null;
System.out.println("Traversing to all nodes..");
while(true){
if(tmp == null){
break;
}
if(tmp.compareTo(after) == 0){
refNode = tmp;
break;
}
tmp = tmp.getNextRef();
}
if(refNode != null){
tmp = refNode.getNextRef();
refNode.setNextRef(tmp.getNextRef());
if(refNode.getNextRef() == null){
tail = refNode;
}
System.out.println("Deleted: "+tmp.getValue());
} else {
System.out.println("Unable to find the given element...");
}
}
public void traverse(){
Node<T> tmp = head;
while(true){
if(tmp == null){
break;
}
System.out.println(tmp.getValue());
tmp = tmp.getNextRef();
}
}
public static void main(String a[]){
SinglyLinkedListImpl<Integer> sl = new SinglyLinkedListImpl<Integer>();
sl.add(3);
sl.add(32);
sl.add(54);
sl.add(89);
sl.adding_After(76, 54);
sl.delete_Front();
sl.deleteAfter(76);
sl.traverse();
}
}
class Node<T> implements Comparable<T> {
private T value;
private Node<T> nextRef;
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public Node<T> getNextRef() {
return nextRef;
}
public void setNextRef(Node<T> ref) {
this.nextRef = ref;
}
public int compareTo(T arg) {
if(arg == this.value){
return 0;
} else {
return 1;
}
}
}
This program helps to implement the concept of single linked list.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.