Question: Write a recursive method addSortedRecursive( ). Instead of using a loo

Question

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 below code is the original addSorted() method:

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()

Explanation / Answer

Dear... public ListNode2()
{ this.data = null; this.next = null; return;
} 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))
{
foundNodes++; if (tempNode == previous)
{
list = tempNode.next;
}
else if (tempNode == last)
{ last = previous; last.next = null;
}
else {
previous.next = tempNode.next;
} numberOfNodes--;
}
else {
previous = tempNode;
}
}
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)
{ first = new ListNode2(); last = first;
}
else
{ last.next = new ListNode2(); last = last.next;
} 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 addSortedRecursive (ListNode2 list, int value )
{ if ( Listnode2.list > value )
{ first = new ListNode2(); first.data = name;
} else return addSortedRecursive ( list.next, value );
} public void displayAllNodesRecur (int nodeNumber)
{
ListNode2 tempNode = this;
System.out.println("Node " + nodeNumber + ": " + tempNode.data); if (tempNode.next != null)
tempNode.next.displayAllNodesRecur(nodeNumber+1);
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.