Section 2 - A Base List Class

7A.2.1 A General Linked List

Our general List class contains two private members, head and current, both Node pointers.  Head will always point to the front of the list and gives us a way to start traversing it.  Current will be free to point to any Node in the list and typically starts at the head and moves forward one-at-a-time as the client requests.  The client positions current by use of the instance methods resetCurrent(), getCurrent() and iterate(). (Eventually, this functionality is replaced by a separate Iterator object, but there are many ways to do it, and you should see more than one.)

We also include methods insertAfterHead() and removeAfterHead() that are not really needed in actual applications.   They are only used in the first test program so that we can add items to the head of the list (and remove them from the head of the list). If you look at this carefully, you'll see that the inclusion of these two methods makes our List class behave exactly like a generic stack.  (Why?).

Prototype

class List{
private:
  Node *head;
  Node *current;

public:
  List();
  virtual ~List();
  virtual void showList();
  //protected:
  Node *getCurrent();
  Node *getNext();
  void resetCurrent();
  Node *iterate();
  void insertAfterHead(Node *np);
  Node *removeAfterHead();
};

Implementation

// List method definitions --------------------------
List::List()
{
  // an empty list will have one "header" node at the front
  head = new Node;
  current = NULL;
}

List::~List()
{
  // list nodes do not belong to the list class - they belong to the client
  // therefore we cannot delete them in the destructor.

  // but we are responsible for the header node which we created
  delete head;
}

void List::showList()
{
  cout << endl << "_____Here's the List_______" << endl;
  for (current = head; current = iterate(); )
  {
    current->show();   // *** Relies on Virtual **
    cout << " ";
  }
  cout << endl << "_____That's all!_______" <<
  endl << endl;
}

Node *List::getCurrent()
{
  return current;
}

Node *List::getNext()
{
  if (current == NULL)
  return NULL;  // if used correctly, never happens
  return current->next;
}

void List::resetCurrent()
{
  current = head;
}

Node *List::iterate()
{
  if (current)
  current = current->next;
  return current;
}

void List::insertAfterHead(Node *np)
{
  head->insertAfter(np);
}

Node *List::removeAfterHead()  // ---------------
{
  return head->removeAfter();
}

7A.2.2 A Test Client and Run

To test the class we use this main():

#include <iostream>
#include <string>
using namespace std;

// class prototypes omitted

// main method ---------------------------------------
int main()
{
  Node *np;
  List myList;
  int k;

  // build a data-less list by inserting 10 nodes at front
  for (k = 0; k < 10; k++)
  {
    np = new Node();
    myList.insertAfterHead(np);
  }
  myList.showList();

  // remove 5 nodes (and delete them!)
  for (k = 0; k < 5; k++)
  {
    np = myList.removeAfterHead();
    delete np;
  }
  myList.showList();

  // before leaving scope, clean up heap
  while ( np = myList.removeAfterHead() )
    delete np;
  // one header node left in list object - this is deleted by List::~List

  return 0;
}

Which produces this result:

We should discuss the very terse but elegant loop control in showList():

for (current = head; current = iterate(); )

This is a short way to go through a list, but it requires that the list have a header node, that is, a node at the front that does not contain any useful data.

1. We start off the pointer current at head.  That is fine.
2. current = iterate() is not a typo.  We are not testing for equality, we are making an assignment.  As we said before, we are taking a step forward in our list with this kind of assignment. We saw it with p = p->next, which is what iterate() does.  However, in past examples this step occurred in the third section of the for loop. Here it is occurring in the second, test, section.  How can that be?  After the assignment we are left with a value.  In C++ false is the same as 0 or NULL.  So, by testing this value for non-zero, we are asking "have we reached the end of the list (remember the list ends with a NULL).  Therefore, this statement takes a step forward and then tests for NULL.
3. Because the iteration is done in the second section there is no need to have anything in the iteration (third) section of the for loop control. That's why it is blank.

Again, we take a step first before we test, which is why we must have a header node in the list.  If there was none, we would be skipping the first data node.

Memory Considerations

A careful study of the class and client reveals that we are making some decisions about memory allocation and de-allocation.  The first decision is that we have chosen to link client-nodes directly into the list rather than making local copies owned by the list.  This is a choice - we are saying that in this class it is important (for some reason) that nodes which are linked in be the originals.  This may be a dangerous decision, but it is a judgment call that the class designer is making.

• Dangerous:  The client has access to the nodes that are in the list.  That means the client might be able to pillage our list.  We reduce the possibility by modifying the Node::getNext() method as using const, or better yet, removing it entirely (it was just used for testing in the last section). Also, we have commented out a protected: qualifier for testing.  Once we have compiled and run the test main() in the next section, we can un-comment that out.  Protected: means that only classes derived from List will be able to access the methods of that section.  It's fine to let the derived List classes invoke these protected functions because they are created by "tinkerer", not end user, programmers.  But the real client class that will ultimately use the finished product will not be able to get at these dangerous methods (dangerous because they return node pointers which could potentially be used to damage the list).  There might be other measures that need to be taken, but we have made our point. 

• Useful: We may want the data (i.e., non-next) portion of derived Node objects to be mutable after they are put into the list.  This would result in the list always being up-to-date with each node's most recent changes.  This is what I am calling  "hot-linked" (not to be confused with the excellent lunch you can get at Top Dog near UC Berkeley).  That is, in turn, why we want originals and not copies to be in the list.

Also, we are creating a header node that will always be in the list, even when it is empty.  Header nodes provide a way to make moving through the list easier with fewer special cases (i.e., we never have to test for empty lists).

Because the client's nodes are being added to the list, the List class methods may not delete them, not even in the List destructor.  The List destructor does, however, have to delete the header node as this was created internally, and not by the client.