In Section 7.7 we implement a recursive version of the list insert operation, fo
ID: 667466 • Letter: I
Question
In Section 7.7 we implement a recursive version of the list insert operation, for sorted linked lists. Using that as a model, design and implement a recursive ver- sion of the list delete operation, for sorted linked lists. Note that the code for our recursive insert method is included in the SortedLinkedList2 class.
The model of the 7.7 of insert is below.
private ListNode recursiveInsert(ListNode subList, Listable item) {
if (subList == null || item.compareTo(subList.info) < 0) {
// Insert new node at the front of this sublist
ListNode newNode = new ListNode(); newNode.info = item; newNode.next = subList;
// Return reference to new node
return newNode; }
else {
// Recursively insert item into list referenced by next // field of current sublist subList.next = recursiveInsert(subList.next, item);
// Return reference to this sublist
return subList; }
}
public void insert(Listable item)
// Adds a copy of item to list
{ list = recursiveInsert(list, item);
}
Explanation / Answer
private ListNode recursivedelete(nodeT **listP, elementT value)
{
nodeT *currP, *prevP;
/* For 1st node, indicate there is no previous. */
prevP = NULL;
/*
* Visit each node, maintaining a pointer to
* the previous node we just visited.
*/
for (currP = *listP;
currP != NULL;
prevP = currP, currP = currP->next) {
if (currP->element == value) { /* Found it. */
if (prevP == NULL) {
/* Fix beginning pointer. */
*listP = currP->next;
} else {
/*
* Fix previous node's next to
* skip over the removed node.
*/
prevP->next = currP->next;
}
/* Deallocate the node. */
free(currP);
/* Done searching. */
return;
}
}
}
public void delete(Listable item)
{ list = recursivedelete(list, item);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.