*****Even if time expires on this, I will still award the karma points for the c
ID: 3631447 • Letter: #
Question
*****Even if time expires on this, I will still award the karma points for the correct answer.*****
Question: Write a recursive method addSortedRecursive( ). Instead of using a loop to determine where to add the new node, this method adds the new value into the list by recursively calling itself. The outline below shows a sketch of the method.
Method Outline:
public ListNode2 addSortedRecursive (ListNode2 list, int value ) {
if the current node’s value is > value
create a new node and add value into it;
add the new node in front of the current node;
return the new node;
else
return addSortedRecursive ( list.next, value ); //add the value to the linked list after the current node
}
The above outline needs to replace the addSorted() method in the code shown below. Replace all the calls of addSorted( ) to addSortedRecursive( ):
public class ListNode2 {
private String data;
private ListNode2 next;
private static ListNode2 first; // a class variable that points to the first node in the list
private static ListNode2 last; // points to the last node in the list
private static int numberOfNodes = 0;
public ListNode2() {
this.data = null;
this.next = null;
return;
}
// Remove all occurrences of nodes with data equal to key.
// Return 0 if no such nodes are found;
// otherwise return the number of nodes found
public static ListNode2 findAndRemove(ListNode2 list, String key) {
int foundNodes = 0;
ListNode2 tempNode = list;
ListNode2 previous = list;
for (int i = 0; tempNode != null; tempNode = tempNode.next, i++) {
if (tempNode.data.equals(key)) { // found
foundNodes++; // one such node is found
if (tempNode == previous) { // first node
list = tempNode.next; // discard the original first
} else if (tempNode == last) { //last node
last = previous; //discard the original last
last.next = null;
} else { // somewhere in the middle
previous.next = tempNode.next; //bypass the current node
}
numberOfNodes--;
} else { // not found in this node
previous = tempNode; //previous advances only when no node was found and deleted
}
} //for
System.out.println("Found " + foundNodes + " nodes with data being " + key);
return list;
}
public static ListNode2 initializeList() {
for (int i = 1; i < 5; i++, numberOfNodes++) {
if (i == 1) { //the first node
first = new ListNode2();
last = first;
} else {
last.next = new ListNode2();
last = last.next;
}
//last.data = new Integer(i).toString();
switch (i % 3) {
case 0:
last.data = "Adam";
break;
case 1:
last.data = "Eve";
break;
case 2:
last.data = "John";
break;
default:
last.data = "Peter";
}
last.next = null;
}
return first;
}
public ListNode2 addSorted(String name) {
if(numberOfNodes == 0) {
first = new ListNode2();
first.data = name;
first.next = null;
} else if(first.data.compareTo(name) > 0) {
ListNode2 temp = first;
// create new first node
first = new ListNode2();
first.data = name;
// update reference to next node
first.next = temp;
} else {
ListNode2 curr = first;
// loop until the right place is found
while(curr.next != null && curr.next.data.compareTo(name) < 0)
curr = curr.next;
// create new node after curr
ListNode2 temp = new ListNode2();
temp.data = name;
// insert temp between curr and curr.next
temp.next = curr.next;
curr.next = temp;
}
numberOfNodes++;
return first;
} // addSorted()
public void displayAllNodes() {
ListNode2 tempNode = this;
for (int i = 1; tempNode != null; tempNode = tempNode.next, i++) {
System.out.println("Node " + i + ": " + tempNode.data);
}
//System.out.println("Leaving displayAllNodes ");
}
public static void main(String args[]) {
ListNode2 list = new ListNode2();
System.out.println("Creating a linked list using the addSorted( ) method ...");
list = list.addSorted("Adam");
list = list.addSorted("Eve");
list = list.addSorted("April");
list = list.addSorted("Don");
list = list.addSorted("Syd");
list = list.addSorted("Mary");
list = list.addSorted("Peter");
list = list.addSorted("April");
list.displayAllNodes();
findAndRemove(list, "April");
System.out.println("After removing "April" ...");
list.displayAllNodes();
} //main
} // class: ListNode2
replace all the calls of addSorted( ) to addSortedRecursive( ).