Homework SourseJava problem The following Java implementation of a class No
Java problem. The following Java implementation of a class Node is given:
private class Node<Comparable> { Node() {
this(null, null);
}
Node(Comparable d) { this(d, null);
}
Node(Comparable d, Node n) { data = d;
next = n;
}
Comparable data; 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:
boolean contains( Object x ) - test if a value x is contained in the linked list.
boolean add( Object x ) - add a value x if it is not already contained in the linked list.
boolean remove(Object x) - remove a value x if it is contained in the linked list.
maintaining the singly linked list in sorted order.
Solution
package mysortedsinglelist;
public class MySortedSingleList<Comparable> {
private Node<Comparable> head;
//test if a value x is contained in the linked list.
public boolean contains(Comparable x){
/*Node<Comparable> tmp = head;
while(tmp!=null)
{
if(tmp.data!=x){
tmp = tmp.next;
}
else{
return true;
}
}
return false; */
Node<Comparable> cursor = head;
while(cursor != null)
{
if(cursor.data.equals(x))
{
return true;
}
cursor = cursor.next;
}
return false;
}
public boolean add(Comparable x)
{
Node<Comparable> nd = new Node<Comparable>();
nd.data = x;
//System.out.println(\"Adding: \"+x);
boolean flag = contains(x);
/* check if the list is empty*/
if(head == null){
//since there is only one element, head
head = nd;
return true;
}
if(flag==false)
{
head.next=nd;
return true;
}
else
{
return false;
}
}
public boolean remove(Comparable x)
{
boolean flag = contains(x);
if(flag)
{
if(head == null)
{
System.out.println(\"Underflow...\");
return false;
}
Node<Comparable> tmp = head;
head = tmp.next;
if(head == null){
head.next = null;
}
System.out.println(\"Deleted: \"+tmp.data);
return true;
}
return true;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
MySortedSingleList<Integer> sl = new MySortedSingleList<Integer>();
sl.add(3);
boolean c1= sl.contains(32);
System.out.print(c1);
sl.add(54);
sl.remove(32);
}
}
class Node<Comparable>
{
Node()
{
this(null, null);
}
Node(Comparable d)
{
this(d, null);
}
Node(Comparable d, Node n)
{
data = d;
next = n;
}
Comparable data; Node next;
}
