Give a pseudo-code for a recursive node delete in the SLList::recDelete(int key)

Question

Give a pseudo-code for a recursive node delete in the SLList::recDelete(int key), where key is the integer value of the node to be deleted. Here is a simple .h file for the SLList to use:

class SLLNode( public: SLLNode () [ next 0 ; SLLNode (int el, LLNode *ptr - data = el; next = ptr; int data; SLLNode *next; class SLList public: SLList) head = tail = 0 SLList (); int isEmpty (); void addToHead (int); void addToTail(int); int deleteFromHead (); int deleteFromTail (); //delete n de with data = int void deleteNode (int) ; void printAll () const void shuffleList(); private SLLNode *head, *tail;

Explanation / Answer

Remember that for a recursive function (i.e., a function that calls itself), we need to decide:

Base case(s): when to stop recursing.
Recursive part(s): how function will call itself to solve the problem.
The base cases are fairly easy, since we need to stop recursing when:

We find the matching value.
We search the whole list and don't find a matching value.
To determine what should be the recursive part of the function, we should consider 2 tasks required of this function:

Finding the one to remove.
How will we search the list for the element? Well, the list will be passed as a pointer to a node (recall the prototype--here we've named the pointer currP):

Node *delRec(Node *currP, int item);  
So, if we decide that the node pointed to by currP is not the right node, then we just recurse to examine the next node:

delRec(currP->next, item);
and so on, until all nodes have been examined.
Relink the list.
When we remove a node, the previous node has to skip over the removed node. A way to achieve this with recursion is through pointer reassignment.

bool SLList::deleteRecur(int item)
{
if (!search(item))
    return false;
head = delRec(head, item);
return true;
}

SLLNode *SLList::delRec(SLLNode *currP, int item)
{
/* See if we are at end of list. */
if (currP == NULL)
    return NULL;

/*
   * Check to see if current node is one
   * to be deleted.
   */
if (currP->data == item) {
    SLLNode *tempNextP;
  
    /* Save the next pointer in the node. */
    tempNextP = currP->next;
  
    /* Deallocate the node. */
    delete currP;
  
    /*
     * Return the NEW pointer to where we
     * were called from. I.e., the pointer
     * the previous call will use to "skip
     * over" the removed node.
     */
    return tempNextP;
}

/*
   * Check the rest of the list, fixing the next
   * pointer in case the next node is the one
   * removed.
   */
currP->next = delRec(currP->next, item);

/*
   * Return the pointer to where we were called
   * from. Since we did not remove this node it
   * will be the same.
   */
return currP;
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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