Question

ADT SORTED LIST

Fill in the missing code in the following code segment.

        

void SortedType::PutItem(ItemType newItem)

{

            NodePtr newNode;                 // pointer to node being inserted

            NodePtr predLoc;                    // trailing pointer

            NodePtr location;                    // traveling pointer

            boolean moreToSearch;

            location = listData;

            predLoc = NULL;

            moreToSearch = (location != NULL);

            length++;

           

// Find insertion point

           

// Prepare node for insertion

           

// Insert node into list

}

Answer 1

Solution:

void SortedType::PutItem(ItemType newItem)

{

            NodePtr newNode;                 // pointer to node being inserted

            NodePtr predLoc;                    // trailing pointer

            NodePtr location;                    // traveling pointer

            boolean moreToSearch;

            location = listData;

            predLoc = NULL;

            moreToSearch = (location != NULL);

             

// Find insertion point.
  while (moreToSearch)
  {
    switch(newItem.ComparedTo(location->info))
    {
      case GREATER: predLoc = location;
                   location = location->next;
                    moreToSearch = (location != NULL);
                    break;
      case LESS:    moreToSearch = false;
                    break;
    }
    
  }

  

// Prepare node for insertion

  newNode = new NodePtr;
  newNode->info = newItem;

// Insert node into list.

  if (predLoc == NULL)         // Insert as first
  {
    newNode->next = listData;
    listData = newNode;
  }
  else
  {
    newNode->next = location;
    predLoc->next = newNode;
  }

   length++;

}

Please give thumbsup, if you like it. Thanks.