*****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( ).
Explanation / Answer
public class ListNode { private String data; private ListNode next; private static ListNode first; // a class variable that points to the first node in the list private static ListNode last; // points to the last node in the list private static int numberOfNodes = ; public ListNode() { this.data = null; this.next = null; return; } // Remove all occurrences of nodes with data equal to key. // Return if no such nodes are found; // otherwise return the number of nodes found public static ListNode findAndRemove(ListNode list, String key) { int foundNodes = ; ListNode tempNode = list; ListNode previous = list; for (int i = ; 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 ListNode initializeList() { for (int i = ; i < ; i++, numberOfNodes++) { if (i == ) { //the first node first = new ListNode(); last = first; } else { last.next = new ListNode(); last = last.next; } //last.data = new Integer(i).toString(); switch (i % ) { case : last.data = "Adam"; break; case : last.data = "Eve"; break; case : last.data = "John"; break; default: last.data = "Peter"; } last.next = null; } return first; } // Add value as a new ListNode and insert it into the right spot // so the data are at ascending order /* public ListNode addSorted(String name) { // case: name should be at front if(numberOfNodes == ) { first = new ListNode(); // ListNode constructor first.data = name; // name assigned to first.data first.next = null; // null assigned to first.next } else if(first.data.compareTo(name) > ) { // save reference to previous first node ListNode temp = first; // create new first node first = new ListNode(); // ListNode constructor first.data = name; // name assigned to first.data // update reference to next node first.next = temp; } else { ListNode curr = first; // loop until the right place is found // stop when either there is no next node, or the next node's data is greater than name while(curr.next != null && curr.next.data.compareTo(name) < ) curr = curr.next; // create new node after curr ListNode temp = new ListNode(); // method call temp.data = name; // assign name to temp.data // insert temp between curr and curr.next temp.next = curr.next; curr.next = temp; } numberOfNodes++; // increment numberOfNodes return first; } // addSorted() */ public ListNode addSortedRecursive (ListNode list, int value ) { /*if the current node’s value is > 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;*/ if ( Listnode.list > value ) { first = new ListNode(); // ListNode constructor first.data = name; } else return addSortedRecursive ( list.next, value ); //add the value to the linked list after the current node*/ } public void displayAllNodesRecur (int nodeNumber) { ListNode tempNode = this; System.out.println("Node " + nodeNumber + ": " + tempNode.data); if (tempNode.next != null) tempNode.next.displayAllNodesRecur(nodeNumber+1); } public static void main(String args[]) { ListNode list = new ListNode(); System.out.println("Creating a linked list using the addSorted( ) method ..."); list = list.addSortedRecursive(list, ); list = list.addSortedRecursive("Eve"); list = list.addSortedRecursive("April"); list = list.addSortedRecursive("Don"); list = list.addSortedRecursive("Syd"); list = list.addSortedRecursive("Mary"); list = list.addSortedRecursive("Peter"); list = list.addSortedRecursive("April"); list.displayAllNodesRecur(); findAndRemove(list, "April"); System.out.println("After removing "April" ..."); list.displayAllNodesRecur(); } //main } // class: ListNodeRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.