Previous Section
 < Free Open Study > 
Next Section


7.9 Recursive Versions of InsertItem and DeleteItem

The InsertItem Operation

Inserting an item into a linked implementation of a sorted list requires two pointers: one pointing to the node being examined and one pointing to the node behind it. We need this trailing pointer because by the time we discover where to insert a node, we are beyond the node that needs to be changed. The recursive version is actually simpler because we let the recursive process take care of the trailing pointer. We develop the algorithm here; in the next section, we demonstrate why it works.

Let's begin by looking at an example where the item type is int.

Click To expand

If we insert 11, we begin by comparing 11 to the value in the first node of the list, 7. Eleven is greater than 7, so we look for the insertion point in the list pointed to by the next member of the first node. This new list is one node shorter than the original list. We compare 11 to the value in the first node in this list, 9. Eleven is greater than 9, so we look for the insertion point in the list pointed to by the next member of the first node. This new list is one node shorter than the current list. We compare 11 with the value in the first node of this new list, 13. Eleven is less than 13, so we have found the insertion point. We insert a new node with 11 as the value of the first node in the list we are examining.

What if the value we are inserting is greater than the value in the last node of the list? In this case, the list is empty and we insert the value into the empty list. Insert is not a member function of ListType; it is an auxiliary function called by InsertItem with the pointer to the list as a parameter. We make it a template function.

The function is coded on the next page. Note that the pointer to the list is a reference parameter; that is, the function receives the actual address of the pointer to the current node, not just a copy of the pointer. We show why this must be true in the next sections.

template<class ItemType>
void Insert(NodeType<ItemType>*& listPtr, ItemType item)
{
  if (listPtr == NULL || item < listPtr->info)
  {
    // Save current pointer.
    NodeType<ItemType>* tempPtr = listPtr;
    // Get a new node.
    listPtr = new NodeType<ItemType>;
    listPtr->info = item;
    listPtr->next = tempPtr;
  }
  else Insert(listPtr->next, item);
}

The DeleteItem Operation

The Delete function is a mirror image of the Insert function. In the iterative version, we find the node to delete only after we have gone past the node containing a pointer to it. We solved that problem in the recursive Insert by passing the address of the pointer to the list. Does the same approach work for the deletion operation? Let's delete 13 from the same list.

Click To expand

The precondition to the operation is that the item is in the list, so we compare 13 with the value in the first node in the list, 7. They are not equal, so we look for 13 in the list pointed to by the next member of the first node in the list. We compare 13 with 9; they are not equal, so we look for 13 in the list pointed to by the next member of the first node. We compare 13 with the value in the first node in the list, and they are equal. We save the pointer to the node containing 13 (to deallocate the node later) and set the pointer to the list equal to the next member of the first node.

Once again, the function must receive the address in the structure where the pointer to the current node is stored.

template<class ItemType>
void Delete(NodeType<ItemType>*& listPtr, ItemType item)
(
  if (item == listPtr->info)
  {
    NodeType<ItemType>* tempPtr = listPtr;
    listPtr = listPtr->next;
    delete tempPtr;
  }
  else
    Delete(listPtr->next, item)
}


Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)