Data structures problem. Please, write a clear solution and comments to easy und
ID: 3790709 • Letter: D
Question
Data structures problem. Please, write a clear solution and comments to easy understand the solution.
The following Java implementation of a class Node is given: private class Node {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 MySortedSinglelList 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.Explanation / Answer
public class MySortedSingleList<Comparable> {
//Let head be the header node of the linked list
Node<Comparable> head;
boolean contains(Object x) {
Comparable data = (Comparable) x;//Convert x into data datatype
Node<Comparable> current = head; //current pointing to head
while(current!= null) {//traverse the list
if(current.data == data)// Object x is present in the list
return true;
if(current.data > data) //As link is sorted, if we get data higher than the value then the object not present
return false;
current = current.next;
}
}
boolean add(Object x) {
Comparable data = (Comparable) x;//Convert x into data datatype
Node<Comparable> current = head; //current pointing to head
Node<Comparable> previous = null;
while(current!= null) {//traverse the list
if(current.data == data) //data is present in the list
return true;
if(current.data < data) {
previous = current;
current = current.next; //Move the pointer to next
continue;
}
if(current.data > data) {
Node<Comparable> newNode = Node(data, current) //Create a new node which next points to current node.
prev.next = newNode; // previous next points to newNode
return true;
}
}
}
boolean remove(Object x) {
Comparable data = (Comparable) x;//Convert x into data datatype
Node<Comparable> current = head; //current pointing to head
Node<Comparable> previous = null;
while(current!= null) {//traverse the list
if ( current.data = data) {
prev.next = current.next; //remove current node from list
free(current) //free the current memory
return true;
}
previous = current;
current = current.next;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.