Section 4 - A Full List of Floats

7A.4.1 A Sorted List of Floats

We now show how a fully general linked-list can be derived from the generic base class List.  We assume you have the FloatNodes defined and working.  We are going to derive a class from List called FloatList.   The class prototype says it all:

class FloatList : public List
{
public:
  void insert(float x);  // insert in increasing numerical order
  bool remove(float f);  // remove the first occurrence from list
};

This is very nice if you think about it.  We can create a FloatList, then start inserting (and or removing) floats into/from it.  Every time we call myList.insert(some_float) the float some_float will be inserted into the list in its correct numerical location, that is, as we build the list it will always be in increasing order.    There are no Nodes, FloatNodes or other techno-babbly data types for our client to deal with.  The client just inserts floats into the list, and removes them whenever he wants to.  The list deals with finding the correct place for the floats.

Here is a graphic illustration of how insert() should work.  Let's say the state of the list at some point in time is:

     

0 → 3.5 → 93.2 → 153 → 200 → 300 → 400 → 436.1 → null 

Then we call myList.insert (250).  The list becomes:

     

0 → 3.5 → 93.2 → 153 → 200 → 250 → 300 → 400  → 436.1 → null 

After calling myList.Delete(200), the list should be:

     

0 → 3.5 → 93.2 → 153 → 250 → 300 → 400 → 436.1 → null 

7A.4.2 Implementation of FloatList::insert() and FloatList::remove()

insert(float x) is a tricky method.  We have to

1. Create a new FloatNode to house the float x.
2. Enter a loop that starts at the head of the list and compares the data for each node in the list with x
3. If x >= the current node's data, then we move forward one node
4. If x < the current node's data, we have found the place in the list to insert x (before the current node).
5. If we reach the end of the list before item 4 above, then we place x at the end of the list (it was larger than all the items.)

The thing that makes this tricky is item 4.  Notice if x is less than the current node's data we have to place x BEFORE that node.  But there is no method to insert a new node BEFORE a node in a list.  There is only insertAfter(), no InsertBefore().  This is not a matter of semantics.  With only one next pointer included in each Node it is impossible to write an InsertBefore() method even if we wanted to do so.  To solve this dilemma, we stand back one node (like holding a dog on a long leash) and test the node two in front of our current position.  That way, when we find the correct place to insert the float x, we are still far enough behind it to do an insertAfter() on the correct node.

Despite my considerable skill at explaining things, you'll just have to read the logic and use a pencil and paper, drawing arrows and crossing out values, as you read the code.  If you trace through the logic you will see how it works.

Here is the implementation of FloatList::insert():

void FloatList::insert(float x)
{
  FloatNode *fp;
  // create a new FloatNode
  FloatNode *newfp = new FloatNode(x);

  // always stay one node behind the node you are testing
  for (resetCurrent(); getCurrent() ; iterate() )
  {
    if (getNext() == NULL)
      break; // pointing to last node in list

    // if x > current then we continue to search
    fp = (FloatNode*)(getNext());
    if ( x <= fp->getData() )
      break;   // found the exact place for this float
  }
  getCurrent()->insertAfter(newfp);
}

As you read this, remember that resetCurrent() is inherited from the List class, and it sets current = head.  Also, iterate() takes a step forward in the list by the simple statement current = current->next.  Remember that we have a header node at the front of the list which has no meaningful float data in it, yet it is absolutely essential to the logic here, so don't ignore it.

Finally, because getNext() returns a simple Node, we have to type cast to FloatNode* so we can access the float, data.

I'll rephrase the confusing part again, this time in the language of the above code.  Our comparison is between the float passed in, x, and current->next->data.  That way if x IS LESS THAN current->next->data, we know that x goes BEFORE current->next.  That means x goes BETWEEN current and current->next.  So we can call getCurrent()->insertAfter() and place the new float before current->next, as desired.  We use getData() accessor to get the data member, since it is private.

Once you understand insert(), it will be easy to understand remove().  Here it is:

bool FloatList::remove(float f)
{
  FloatNode *fp;

  // always stay one node behind the node you are testing
  for (resetCurrent(); getCurrent() ; iterate() )
  {
    if (getNext() == NULL)
      return false; // end of list and not found

    // if f == current then we found match
    fp = (FloatNode*)(getNext());
    if ( f == fp->getData() )
    {
      Node *doneWithNode = getCurrent()->removeAfter();
      delete doneWithNode;
      return true;   // we found, we removed, we return
    }
  }
  return false;
}

This is the complete implementation of FloatList which is derived from List.  Because this same logic works for any data type, it is essential that you understand it.  To make sure you do, I'll want you to create a StringNode (or even CardNode) and StringList (CardList) class, so that you will have the methods that will insert strings (or Cards) in a list in increasing order.  It should be easy to copy the code above and make the minor changes.

The next page has a sample run and the full listing.