The following Java implementation of a class Node is given: private class Node<C
ID: 3790718 • Letter: T
Question
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:
(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
Hi, Please find my implementation.
Please let me know in case of any issue.
public class MySortedSingleList {
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<Comparable> next;
}
Node<Comparable> head;
public MySortedSingleList() {
head = null;
}
boolean contains(Object x){
Node<Comparable> temp = head;
while(temp != null){
if(temp.data.equals(x))
return true;
temp = temp.next;
}
return false;
}
boolean add(Object x ){
if(contains(x))
return false;
Comparable obj = (Comparable)x;
Node<Comparable> newNode = new Node<Comparable>(obj);
if(head == null){
head = newNode;
}else if(head.data.compareTo(obj) > 0){
newNode.next = head;
head= newNode;
}else{
Node<Comparable> temp = head;
while(temp.next != null){
if(temp.next.data.compareTo(obj) > 0){
break;
}
temp = temp.next;
}
newNode.next = temp.next;
temp.next = newNode;
}
return true;
}
boolean remove(Object x){
Comparable obj = (Comparable)x;
if(head == null) // base case, list is null
return false;
if(head.data.compareTo(obj) == 0){ // first element is equal to x
head = head.next;
return true;
}
Node<Comparable> temp = head;
while(temp.next != null){
if(temp.next.data.compareTo(obj) == 0){
temp.next = temp.next.next;
return true;
}
temp = temp.next;
}
return false; // x is not in linked list
}
}