The following Java implementation of a class Node is given: private class Node<
ID: 3791009 • Letter: T
Question
The following Java implementation of a class Node is given:
private class Node<Comparable> { Node() {
data = d;
next = n; }
Node next; }
Assume that a singly linked list is implemented with a header node, but no tail node, and that it maintains only a reference to the header node.
Using the class Node described above, write a MySortedSingleList class in Java includes methods to:
(a) boolean contains( Object x ) - test if a value x is contained in the linked list.
(b) boolean add( Object x ) - add a value x if it is not already contained in the linked list.
(c) boolean remove(Object x) - remove a value x if it is contained in the linked list.
maintaining the singly linked list in sorted order.
Explanation / Answer
public class MySortedSingleList {
Node<Object> first;
boolean contains( Object x ) {
Node temp = first;
while (temp != null)
if (temp.data.equals(x))
return true;
else if (compare(first.data,x) < 0)
temp = temp.next;
else
return false;
return false;
}
boolean add( Object x ) {
Node newNode = new Node<>(x);
Node temp = first;
if (compare(x,temp.data) < 0) { //new node is the first node
temp.next = first;
first = temp;
return true;
}
while (compare(temp.next.data,x) < 0){
temp = temp.next;
if (temp.next == null)
break;
}
if (compare(temp.next.data,x) == 0) // data already present
return false;
newNode.next = temp.next;
temp.next = newNode;
return true;
}
boolean remove(Object x) {
Node temp = first;
if (compare(x,temp.data) < 0) // x is less than first so it cannot be there in the list
return false;
if (compare(first.data, x)==0) { // first node is deleted
first = first.next;
return true;
}
while (compare(temp.next.data,x) > 0){ // temp points to the previous node that should be deleted
temp = temp.next;
if (temp.next == null)
break;
}
if (compare(temp.next.data,x) == 0) {
temp.next = temp.next.next;
return true;
}
return false; // node not found
}
private int compare(Object data1, Object data2) {
//TODO implememt compare function such that it returns 0 if data1 and data2 have same value and returns +ve value if data1 is more than data2 else returns -ve value
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}
}
The java code is self explanatory. Do not forget to click thumbs up button if this helps you! cheers!